Home › Blogs › garrett's blog ›

Project Euler Problem 42

garrett // Aug 31, 2010
//

Project Euler Problem 42 involved some text parsing -- a nice change of pace. I went on a bit of a binge last night and solved 6 problems, but they were all erpa-derpa-factor-erpa-derpa-sieve, so I didn't bother posting.. as, we'll, they're boring. This one gave me an excuse to write some perverse perl, though, so here goes; I have no shame.

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

  1. #!/usr/bin/perl -w
  2.  
  3. use strict;
  4.  
  5. # clean up our input and create a hash of the form {55=>[sky]}
  6. # to track association between numerical values and words
  7. my $words;
  8. while(<STDIN>) {
  9.     $_ =~ s/\"//g;
  10.     my @row = split(",", $_);
  11.     foreach my $word (@row) {
  12.         push(@{$words->{word_value($word)}}, $word);
  13.     }
  14. }
  15.  
  16. # from the above hash, find the maximum possible numerical value.
  17. # calculate triangle numbers up to that point, and keep track
  18. # of how many words are associated with their values.
  19. my $max_value   = (sort {$b<=>$a} keys %$words)[0];
  20. my $cur_value   = 0;
  21. my $words_found = 0;
  22. for(my $i = 0; $cur_value < $max_value; $i++) {
  23.     $cur_value = ($i*($i+1)/2);
  24.     $words_found += @{$words->{$cur_value}} if($words->{$cur_value});
  25. }
  26.  
  27. print "Found $words_found triangle words\n";
  28.  
  29. # calculate a given word's numerical value.
  30. sub word_value {
  31.     my $word = lc(shift);
  32.     return eval(join("+", map {ord($_)-96} split(//, $word)));
  33. }