오일러 프로젝트 42

n번째 삼각수는 t_n = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다.

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

어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, …, Z=26)를 모두 더한 값을 ‘단어값’이라 부르기로 합니다. 예를 들어 ‘SKY’의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t₁₀과 같습니다. 이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 ‘삼각단어’라 부르기로 합니다.

약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다. 이 중에서 삼각단어는 모두 몇 개입니까?  

http://euler.synap.co.kr/prob_detail.php?id=42

접근

영어 단어의 각 철자의 순번을 더하여 ‘단어 값’을 구한 후 이 값이 삼각수에 해당하는지 보면 된다. 삼각수는 1~N사이의 자연수들의 누적합이다. 따라서 루프를 돌면서 누적합이 주어진 값과 같아지는지를 검사하면 되는데, 굳이 루프를 돌지 않고 등차수열의 합 공식을 변형하여 사용할 수 있다. 삼각수 공식을 아래와 같이 변형하여 누적합으로부터 n을 계산할 수 있다.

\begin{array}{lll}
s &= \frac{1}{2}n(n+1) \\
n^2 + n + \frac{1}{4} &= 2s + \frac{1}{4} \\
(n + \frac{1}{2})^2 &= 2s + \frac{1}{4} \\
n &= \sqrt{2s + \frac{1}{4}} - \frac{1}{2}

\end{array}

좀 다른 방식을 취할 수도 있는데, 특정 범위의 삼각수를 구해두고 계산된 단어값이 그 집합 내에 있는지를 검사할 수도 있다. 어떤 식으로 처리하든 성능상의 큰 차이는 없을 것 같다.

데이터 자체가 양이 많기 때문에 HTTP를 통해서 데이터를 받아와서 분석하도록 한다.

from urllib.request import urlopen

ts = set( n * (n + 1) // 2 for n in range(1, 1400))

with urlopen('https://euler.synap.co.kr/files/words.txt') as f:
  words = (w.strip('"') for w in f.read().decode().split(',')
  scores = [sum(ord(c) - 64 for c in word) for word in words]
  print(sum(1 for x in scores if x in ts))