ホーム - Project Euler

Problem 42¶

Coded Triangle Numbers¶

The $n$^th term of the sequence of triangle numbers is given by, $t_n = \frac12n(n+1)$; so the first ten triangle numbers are:

$$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

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 = t_{10}$. 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?

符号化三角数¶

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

$$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t₁₀である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.

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

(import (scheme base)
        (gauche base)
        (scheme file))

(define words (string-split
                (call-with-output-string
                  (^[string-port]
                    (format string-port
                            "~a"
                            (call-with-input-file
                              "words.txt"
                              (^[file-port]
                                (read-line file-port))
                              :element-type :character))))
                #[","] 'suffix #f 1))

(define (words-num words)
  (map (^s
         (fold (^[c n]
                 (+ n
                    (- (char->integer c)
                       (char->integer #\A)
                       -1)))

               0
               (string->list s)))
       words))

(define (triangle-num num)
  (let loop ([index 1] [lis '()])
    (let ([current (/ (* index
                         (+ index 1))
                      2)])
      (if (< num current)
        (reverse lis)
        (loop (+ index 1) (cons current lis))))))

(define (match-triangle-num words)
  (let* ([words-num-list (words-num words)]
         [triangle-num-list (triangle-num
                              (apply max words-num-list))])
    (filter (^n
              (find (cut = n <>)
                    triangle-num-list))
            words-num-list)))

(define answer-42
  (length (match-triangle-num words)))

(format #t "42: ~d~%" answer-42)