25 August 2010

Project Euler : How many triangle words does the list of common English words contain?

Problem 42

The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½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?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
puts "The total number of words is #{count}"

Hover here to see the solution


No comments: