HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Project Euler #42 - Triangle Numbers

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
triangleprojecteulernumbers

Problem

Here is the Euler problem referenced, it says:


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?

My solution is as follows:

import re
import string

#generate a key to map the letters in our strings to
letters = string.ascii_uppercase
letters_map = {letter: idx for idx, letter in enumerate(string.ascii_uppercase, start=1)}

#open the file and parse on quoted values  
with open('words.txt') as f:
    words = sorted(re.findall(r'"(.*?)"', f.read()))

#max word score can only be Z*len(n), recall 'Z' : 26 in letters_map    
max_word_score = len(max(words, key=len))*26

#generate a list of triangle_numbers to search for using max_score as upper bound
n = 1
triangle_numbers = []
while 1/2.0*n*(n+1) <= max_word_score:
    triangle_numbers.append(1/2.0*n*(n+1))
    n += 1

#finally use a nested for loop to return number of triangle numbers in our now summed words
count = 0
for word in words:
    if sum(letters_map[char] for char in word) in triangle_numbers:
        count += 1

%%timeit
100 loops, best of 3: 3.67 ms per loop


I'm curious if there are any ways I can rewrite this with similar or better performance so that it is more pythonic. I'm curious about a few things more specifically:

1) Is it possible to rewrite this better using itertools.ifilter and itertools.imap using letters_map and the filter being the list of triangle_numbers, to greater affect than

Solution

Your should use csv to read the file.

import csv
with open('words.txt', 'rb') as csvfile:
    words = [
        word
        for line in csv.reader(csvfile, delimiter=',', quotechar='"')
        for word in line
    ]


It's much easier to understand what it is doing. And it's probably safer and faster.

You define letters, however you use string.ascii_uppercase instead.

You can put max_word_score in the same 'block' as the while loop below it.
You can also re-arange 1/2.0n(n+1)

-
It's not 'Pythonic' as the maths you use isn't. However personally I think a greedy
for` is better, (hence why my maths is an over estimate).

-
If you wrapped them in a main that would be good. Wrapping them into functions, is always better than having no functions.
But as this can be done with 3 constants, and 1 generator, I would say one function is fine.

-
I would say following PEP8 is your best bet for that.

Code Snippets

import csv
with open('words.txt', 'rb') as csvfile:
    words = [
        word
        for line in csv.reader(csvfile, delimiter=',', quotechar='"')
        for word in line
    ]
max_word_score = len(max(words, key=len)) * 26
triangle_numbers = [
    0.5 * n * (n + 1)
    for n in xrange(int((2 * max_word_score + max_word_score)**0.5))
]

count = sum(
    1
    for word in words
    if sum(letters_map[char] for char in word) in triangle_numbers
)
import csv
import string

MAX_TRIANGLE = 30 * 26
LETTERS_MAP = {letter: idx for idx, letter in enumerate(string.ascii_uppercase, start=1)}
TRIANGLE_NUMBERS = [
    0.5 * n * (n + 1)
    for n in xrange(int((2 * MAX_TRIANGLE) ** 0.5))
]

with open('words.txt', 'rb') as csvfile:
    count = sum(
        1
        for line in csv.reader(csvfile, delimiter=',', quotechar='"')
        for word in line
        if sum(LETTERS_MAP[char] for char in word) in TRIANGLE_NUMBERS
    )

Context

StackExchange Code Review Q#107515, answer score: 4

Revisions (0)

No revisions yet.