# Project Euler Problem 42: Coded triangle numbers

The nth term of the sequence of triangle numbers is given by, $T_n = \frac{n(n+1)}{2}$; 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?

In [1]:
import csv

from six.moves import filter
In [2]:
with open('../../files/p042_words.txt', 'r') as csvfile:
In [3]:
words[:10]
Out[3]:
['A',
'ABILITY',
'ABLE',
'ABOVE',
'ABSENCE',
'ABSOLUTELY',
'ACCEPT',
'ACCESS']
##### Alphabetical Order of Character¶
In [4]:
alpha_ord = lambda c: ord(c.lower()) - ord('a') + 1
In [5]:
alpha_ord('a')
Out[5]:
1
In [6]:
alpha_ord('A')
Out[6]:
1
In [7]:
alpha_ord('F')
Out[7]:
6
In [8]:
alpha_ord('z')
Out[8]:
26
##### Numerical Value of String¶
In [9]:
str_val = lambda s: sum(map(alpha_ord, s))
In [10]:
str_val('SKY')
Out[10]:
55
##### Get numerical values of all words¶
In [11]:
list(map(str_val, words))[:10]
Out[11]:
[1, 78, 20, 59, 45, 49, 132, 39, 48, 50]
In [12]:
dict(zip(words, map(str_val, words[:10])))
Out[12]:
{'A': 1,
'ABILITY': 78,
'ABLE': 20,
'ABOVE': 45,
'ABSENCE': 49,
'ABSOLUTELY': 132,
'ACCEPT': 48,
'ACCESS': 50}

#### Version 1¶

In [13]:
def polygonal(s):
c = s - 2
a = b = 1
while True:
yield a
b += c
a += b
In [14]:
t = 0
count = 0
triangle_set = set()
triangle = polygonal(3)
for num in map(str_val, words):
while t <= num:
t = next(triangle)
if num in triangle_set:
count += 1
In [15]:
count
Out[15]:
162
In [16]:
def count_polygonal(s, lst):
p = 0
count = 0
polygonal_set = set()
it = polygonal(s)
for num in lst:
while p <= num:
p = next(it)
count += (num in polygonal_set)
return count
In [17]:
count_polygonal(3, map(str_val, words))
Out[17]:
162
In [18]:
count_polygonal(5, map(str_val, words))
Out[18]:
92

#### Version 2 - Terse but less efficient / readable¶

In [19]:
word_vals = map(str_val, words)
In [20]:
max_word_val = max(word_vals); max_word_val
Out[20]:
192
In [21]:
from itertools import takewhile
In [22]:
triangle_set = set(takewhile(lambda n: n <= max_word_val, polygonal(3))); triangle_set
Out[22]:
{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190}
In [23]:
len(list(filter(lambda word: word in triangle_set, word_vals)))
Out[23]:
0
In [24]:
count_polygonal = lambda s, lst: len(list(filter(lambda wd: wd in set(takewhile(lambda n: n <= max_word_val, polygonal(s))), lst)))
In [25]:
count_polygonal(5, map(str_val, words))
Out[25]:
92

In [26]:
# TODO