Project Euler Problem 42 Solution

Question

The n^{th} term of the sequence of triangle numbers is given by, t_n = \frac{1}{2}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 = t_{10}. 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?

Haskell

parse :: String -> [String]
parse = words . map replaceComma . filter notQuote where
    replaceComma ',' = ' '
    replaceComma c = c
    notQuote = (/= '"')

alphaIndex :: Char -> Int
alphaIndex c = fromEnum c - 64

alphaScore :: String -> Int
alphaScore = sum . map alphaIndex

triangle :: String -> Bool
triangle str = floor t == ceiling t
    where s = alphaScore str
          t = (sqrt (fromIntegral (1 + 8*s)) - 1) / 2

main :: IO ()
main = do
    str <- readFile "/home/zach/code/euler/042/words.txt"
    print $ length $ filter triangle $ parse str

$ ghc -O2 -o triangle-words triangle-words.hs
$ time ./triangle-words
real   0m0.003s
user   0m0.000s
sys    0m0.003s

Python

#!/usr/bin/env python
import os
from string import ascii_uppercase

def letter_value(letter):
    return ascii_uppercase.index(letter.upper())+1

def word_value(word):
    return sum(letter_value(letter) for letter in word)

def triangle(n):
    return int((0.5) * n * (n+1))

def main():
    triangle_numbers = [triangle(n) for n in range(1, 100)]
    words = [word.strip('"') for word in open(os.path.join(os.path.dirname(__file__), 'words.txt')).read().split(',')]
    total = 0
    for word in words:
        if word_value(word) in triangle_numbers:
            total += 1
    print(total)

if __name__ == "__main__":
    main()

$ time python3 triangle-words.py
real   0m0.036s
user   0m0.028s
sys    0m0.007s

Ruby

#!/usr/bin/env ruby
triangles = (1..1000).map { |n| (n*(n+1))/2 }.to_a
puts File.read(File.dirname(__FILE__) + '/words.txt').scan(/\w+/).select { |word|
  triangles.include? word.each_byte.reduce(0) {|s,v| s+(v-64) }
}.count

$ time ruby triangle-words.rb
real   0m0.048s
user   0m0.048s
sys    0m0.000s