Project Euler 42: Count how many 'triangle words' a list of common English words contain
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?
Remember Problems 44 & 45? The same logic applies except for triangle numbers. Whenever the equation ( √(1+8n) – 1 ) / 2 evaluates to an integer the number, n, is a triangle number. The mod 1 trick is a quick way to tell if the expression resolved as an integer.
In a nutshell: We connect to the file, strip quotes and separate by commas into a list. We define two functions: one to check a number for triangularity and the other to calculate a word score. Finally, we count the number of scores that are triangular.
Project Euler 42 SolutionRuns < 0.001 seconds in Python 2.7.
from math import sqrt from urllib2 import urlopen file_url = 'http://projecteuler.net/project/words.txt' words = [x[1:-1] for x in urlopen(file_url).read().split(',')] def is_tn(n): return not bool(((sqrt(1 + 8*n) - 1) / 2) % 1) def score(word): return sum(abs(64 - ord(letter)) for letter in word) print "Project Euler 42 Solution =", sum(is_tn(score(word)) for word in words)Use this link to get the Project Euler 42 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- See also, Project Euler 22 Solution: Calculate the total of all the name scores in the file of first names.
- See also, Project Euler 44 Solution: Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.
- See also, Project Euler 45 Solution: Find the next triangle number that is also pentagonal and hexagonal after 40755
- Backup copy of words.txt file from Project Euler site.