Project Euler Problem 042 - つまみ食う

http://projecteuler.net/index.php?section=problems&id=42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042

三角数のn項は t(n) = n(n+1) / 2 で与えられる. 最初の10項は

  1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 

例えば SKY は 19 + 11 + 25 = 55 = t(10)である. 
単語の値が三角数であるとき, その単語を三角語と呼ぶ.

16Kのテキストファイル words.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか?

問題文にあるとおり三角数のn項は
$x = \frac{1}{2}n(n + 1)$
で求められる。

これを、nについて解くと
$x^2 + n - 2x = 0$

解の公式を使って、
$n=\frac{-1\pm\sqrt{1+8x}}{2}$

nは正の整数なので、
$n=\frac{-1+\sqrt{1+8x}}{2}$

だけを評価すればよい、この n が整数であれば x はn項の三角数であることがわかる。

import math
import datetime


def is_triangle_number(x):
    n = (math.sqrt(8 * x + 1) - 1) / 2.0
    return int(n) == n


def euler042():
    words = [ s[1:-1] for s in open('words.txt').read().split(',') ]

    cnt = 0
    for word in words:
        x = sum(ord(i) - 64 for i in word)
        if is_triangle_number(x):
            cnt += 1

    print cnt
    

begin = datetime.datetime.now()
euler042()
end = datetime.datetime.now()
print end - begin

答え: 162
実行時間: 0.007682秒くらい