Project Euler Problem 17

問題17: 1 から 1000 までの数字をすべて英単語で書くと全部で何文字になるか。[=>問題文]

問題17の解答

　数詞の法則が奇妙な国って意外に多いです。ゼロの発明以前から人類が「数」を使っていた証でしょうか。

;; Emacs Lisp
(require 'cl)
(defun problem017 ()
  (let ((name-table (make-hash-table)))
    (puthash 1 "one" name-table)
    (puthash 2 "two" name-table)
    (puthash 3 "three" name-table)
    (puthash 4 "four" name-table)
    (puthash 5 "five" name-table)
    (puthash 6 "six" name-table)
    (puthash 7 "seven" name-table)
    (puthash 8 "eight" name-table)
    (puthash 9 "nine" name-table)
    (puthash 10 "ten" name-table)
    (puthash 11 "eleven" name-table)
    (puthash 12 "twelve" name-table)
    (puthash 13 "thirteen" name-table)
    (puthash 14 "fourteen" name-table)
    (puthash 15 "fifteen" name-table)
    (puthash 16 "sixteen" name-table)
    (puthash 17 "seventeen" name-table)
    (puthash 18 "eighteen" name-table)
    (puthash 19 "nineteen" name-table)
    (puthash 20 "twenty" name-table)
    (puthash 30 "thirty" name-table)
    (puthash 40 "forty" name-table)
    (puthash 50 "fifty" name-table)
    (puthash 60 "sixty" name-table)
    (puthash 70 "seventy" name-table)
    (puthash 80 "eighty" name-table)
    (puthash 90 "ninety" name-table)
    (puthash 100 "hundred" name-table)
    (puthash 1000 "thousand" name-table)
    (let ((work-vect (make-vector 1001 nil)))
      (labels
          ((set-vect (i lis) (aset work-vect i lis))
           (ref-vect (i) (aref work-vect i))
           (ref-table (i) (list (gethash i name-table))))
        ;; 1 - 20
        (do ((i 1 (1+ i)))
            ((< 20 i))
          (set-vect i (ref-table i)))
        ;; 21 - 99
        (do ((i 20 (+ i 10)))
            ((< 90 i))
          (let ((lis (ref-table i)))
            (set-vect i lis)
            (do ((j 0 (1+ j)))
                ((< 9 j))
              (set-vect (+ i j) (append lis (ref-vect j))))))
        ;; 100 - 999
        (do ((i 1 (1+ i)) (name100 (ref-table 100)))
            ((< 9 i))
          (let* ((j (* i 100))
                 (lis (append (ref-vect i) name100)))
            (set-vect j lis)
            (do ((k 1 (1+ k)))
                ((< 99 k))
              (set-vect (+ j k)
                        (append lis (cons "and" (ref-vect k)))))))
        ;; 1000
        (set-vect 1000 (append (ref-vect 1) (ref-table 1000)))

        ;; 全文字列を連結して長さを返す
        (length (apply #'concat
                       (mapcar #'(lambda (lis)
                                   (apply #'concat lis))
                               work-vect)))))))
(problem017)

　たとえば 256 なら ("two" "hundred" "and" "fifty" "six") というリストを作って work-vect のインデックス 256 の位置に保存します。そうやって 1000 までリストを作成して、最後に全文字列を連結して長さを取得しています。必要なのは文字列長だけなので、実際に文字列を作る必要は無く 文字列の長さだけ記録していけばいいんですが、デバッグすることを考えるとそれはちょっと避けたいですね。
　100 以降の下二桁は既に作成済みの 99 までの数詞を参照することで少しだけ処理を省略できます。
　あ、そうそう。今回ループに do を使ってます。ちょっと括弧の対応がややこしくて今まで敬遠してきたけど一念発起。ループ式の中で let を使わずレキシカル変数が作れるってのは便利ですね。