The n-term of a triangular number is given by tn = ½n (n + 1). The first 10 terms are
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Is.
The sum is taken after converting the alphabet in the word to a number. We call this sum the "word value". For example, SKY is 19 + 11 + 25 = 55 = t10. The word value is a triangular number. At one point, the word is called a triangular word.
Approximately 2000 English words are written in the 16K text file words.txt. How many triangular words are there? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
The response policy is as follows.
def main():
words = file2list('p042_words.txt')
MAX = max_length(words) * 26
tri = tri_dict(MAX)
ans = 0
for word in words:
if word2num(word) in tri:
ans += 1
print ans
file2list is a function that opens a file and lists the read strings. If you pass a function to the list, it seems to be more versatile, but it's annoying, so it's not supported.
def file2list(filename):
file = open(filename)
ret = file.read().replace('"','').split(',')
file.close()
return ret
A function that calculates the number of characters in a word list words to determine the maximum value for creating a set of triangular numbers.
def max_length(words):
max_len = 0
for word in words:
if len(word) > max_len:
max_len = len(word)
return max_len
A function that returns a dictionary-type object that stores a triangular number that is less than or equal to the specified maximum value.
def f(n):
return n * (n+1) / 2
def tri_dict(max):
n=1
tri = {}
while f(n)<=max:
tri[f(n)] = True
n+=1
return tri
Functions that digitize words, etc. I should have used reduce. Note that ord is a built-in function that returns the integer representing the Unicode code point if the string is a unicode object, and the value of that byte if the string is an 8-bit string, for a given string of length 1. In alfa2num, the value of the byte of'A'is 65, so the value obtained by subtracting 64 is returned.
def alfa2num(s):
return ord(s) - 64
def word2num(word):
return sum([alfa2num(s) for s in word])
Recommended Posts