Project Euler Problem 18, 67 - 思いついたら書く日記 Ex

問題18: 数字で構成される三角形を頂点から最下段まで移動する。経路の合計がもっとも大きくなる時の値を求めよ。[=>問題文]

問題18の解答

「経路の総当りをする」という発想がむしろ出ませんでした。

;; Emacs Lisp
(require 'cl)

(defun problem018 (data)
  (let ((prev '(0 0)) ; 一段上のリスト
        (next))       ; 次に処理する段のリスト
    (dolist (next data)
      (let ((tmp '(0)))
        (while (consp next)
          (push
           (+ (pop next)
              (max (first prev) (second prev)))
           tmp)
          (pop prev))
        (setq prev (reverse (cons 0 tmp)))))
    (apply #'max prev)))

(let ((data
       '((75)
         (95 64)
         (17 47 82)
         (18 35 87 10)
         (20 04 82 47 65)
         (19 01 23 75 03 34)
         (88 02 77 73 07 63 67)
         (99 65 04 28 06 16 70 92)
         (41 41 26 56 83 40 80 70 33)
         (41 48 72 33 47 32 37 16 94 29)
         (53 71 44 65 25 43 91 52 97 51 14)
         (70 11 33 28 77 73 17 78 39 68 17 57)
         (91 71 52 38 17 14 91 43 58 50 27 29 48)
         (63 66 04 68 89 53 67 30 73 16 69 87 40 31)
         (04 62 98 27 23 09 70 98 73 93 38 53 60 04 23))))
  (problem018 data))

　上の段の値を次の段の値に加算する。それを上から順に繰り返して雪崩のように三角形を更新してゆきます。三角形内部の任意の数字は、加算候補が右上・左上の 2 つあるので、値の大きいほうを選んで加えて行けば可能な限り大きな数字が最後の段にリストアップされます。最終段の max をとればそれが求める答えとなります。
　各段の端の数字も他と同じロジックで扱えるように　リストの前後に 0 を追加しながら処理をしています。

別解・逆さバージョン

　投稿してから気づきましたが、三角形を逆さまにして処理すればリストに 0 を追加する必要もないし、最後は頂点に収束するから max をとる必要もありませんね。

(defun problem018-2 (data)
  (let* ((rdata (reverse data))
         (prev (car rdata))
         (next))
    (dolist (next (cdr rdata) (car prev))
      (let ((tmp))
        (while (consp next)
          (push
           (+ (pop next)
              (max (first prev) (second prev)))
           tmp)
          (pop prev))
        (setq prev (reverse tmp))))))

問題67の解答

　やることは一緒なので同じ関数を使ってついでにやってしまいます。こちらはファイルで用意されている100段の数値で構成される三角形が対象となります。[=>問題文]

;;problem 67 (Emacs Lisp)
(let* ((str (let ((str)  ;;ファイルからデータ取得
                  (buf (find-file "triangle.txt")))
              (setq str (buffer-string))
              (kill-buffer buf)
              str))
       (lis (mapcar      ;;読み込んだデータを数値のリストへ変換
             #'(lambda (line)
                 (mapcar #'string-to-number
                         (split-string line)))
             (split-string str "\n"))))

  ;; 末尾のゴミを除去
  (setq lis (reverse (cdr (reverse lis))))

  (problem018-2 lis))

　Emacs Lisp ではファイルから直接データを取得することはできず、バッファにデータを読み込んで、そこからデータを切り出すしかないようです。 read 関数を使えばバッファ内の数字列を数値として読み込むことができますがそれだと改行位置がわからなくなるため文字列として取得 (buffer-string) して自前でパースしています。ここに来て初めて Emacs Lisp ならではといえるコードになりました。
　ファイル末尾に改行だけの行があり、これを読み込んで三角形の最後に空リストが入ってしまうため処理する前にゴミ取りが必要です。