patternpythonMinor
Project Euler #42 - Triangle Numbers
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:
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
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 loopI'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
It's much easier to understand what it is doing. And it's probably safer and faster.
You define
You can put
You can also re-arange
-
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.
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.