Problem 42 - 三角数

Scheme

段々翻訳されてない所に入ってきた。英語力が無い僕には辛くなりそう。

Problem 42 - Project Euler

The n^th 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?

要約すると、words.txtから単語のポイントを取って、三角数な単語の数答えよ。と。


三角数は、f(1) = 1, f(n) = n + f(n - 1)の漸化式で表せて、

1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55

となる。

三角数を二倍すると面白くなる。

1 3 6 10 15 21 28 36 45 55
2 6 12 20 30 42 56 72 90 110
1*2 2*3 3*4 4*5 5*6 6*7 7*8 8*9 9*10 10*11

パスカルの三角形を書くといろんなところに三角数が現れて楽しい。

また、三角数は一般式でf(n) = n(n + 1)/2とも書ける。


で、今回は単語のポイントが、三角数かどうかを判断しなければならないので、単語のポイントをxと置いといて、

x = n(n + 1)/2

展開して、

n^2 + n - 2x = 0

xが決まれば、nの解が出るので、解の公式から、

n = (-1 ± √(1 + 8x))/ 2

nは正の整数なので、プラス側を見ればいい。

n = (-1 + √(1 + 8x))/ 2

nが整数になった時三角数であると言える。


三角数かどうか判断出来るようになったので、コーディング。

(define (problem42 data)
  (let ((A (- (char->integer #\A) 1))
        (triangle? (lambda (n)
                     (integer? (/ (- (sqrt (+ 1 (* 8 n))) 1) 2)))))
       (length
         (filter (lambda (s)
                   (triangle?
                     (fold (lambda (c acc) (+ acc
                                              (- (char->integer c) A)))
                           0
                           (string->list s))))
                 data))))

(problem42 *data42*) ; 162

words.txtをあらかじめリストに変換しといてから解いた。

数学的に解けたのは始めてかも。