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:
    words = next(csv.reader(csvfile))
In [3]:
words[:10]
Out[3]:
['A',
 'ABILITY',
 'ABLE',
 'ABOUT',
 'ABOVE',
 'ABSENCE',
 'ABSOLUTELY',
 'ACADEMIC',
 '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,
 'ABOUT': 59,
 'ABOVE': 45,
 'ABSENCE': 49,
 'ABSOLUTELY': 132,
 'ACADEMIC': 39,
 '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)
        triangle_set.add(t)
    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)
            polygonal_set.add(p)
        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

Version 3 - Reduce Triangle number test to Square number test

In [26]:
# TODO

Comments

Comments powered by Disqus