mu chance or much chance ?

日々の戯れ言

Project Euler 42

  • 問題

Problem 42:Coded triangle numbers
The nth term of the sequence of triangle numbers is given by, tn = ½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 = t10. 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?

  • 解答例
def listTriNum(num):
    list = [1]
    i = 2
    while i * (i + 1) // 2 <= num:
        list.append(i * (i + 1) // 2)
        i += 1
    return list

num = { "A":1,
        "B":2,
        "C":3,
        "D":4,
        "E":5,
        "F":6,
        "G":7,
        "H":8,
        "I":9,
        "J":10,
        "K":11,
        "L":12,
        "M":13,
        "N":14,
        "O":15,
        "P":16,
        "Q":17,
        "R":18,
        "S":19,
        "T":20,
        "U":21,
        "V":22,
        "W":23,
        "X":24,
        "Y":25,
        "Z":26}

f = open("p042_words.txt", "r")

name = []
for line in f:
    text = line.replace('\n', '')
    text = text.replace('\r', '')
    text = text.replace('"', '')
    name = text.split(",")
f.close()

maxLen = 0
for n in name:
    if maxLen < len(n):
        maxLen = len(n)

triangleNum = listTriNum(maxLen * 26)

count = 0
for n in name:
    score = 0
    temp = list(n)
    for x in temp:
        score += num[x]
    if score in triangleNum:
        count += 1
        print(n, score)

print(count)
  • 用意したファイル(p042_words.txt)

https://projecteuler.net/project/resources/p042_words.txt