整数トライアングルの和の最大値を求める問題。
苦手だった問題。こういう考え方 で実装すれば楽だ。見方を変えるのは大切だし、データ構造はもっと大切。
(ql:quickload :split-sequence)
(defun read-triangle ()
(reverse
(with-open-file (s "/Users/yappy/lisp/p067_triangle.txt")
(loop for line = (read-line s nil 'eof)
until (eq line 'eof)
collect (mapcar #'parse-integer (split-sequence:split-sequence #\space line))))))
(defun max-line (lst)
(mapcar #'(lambda (x) (apply #'max x))
(reverse (cdr (reverse
(maplist (lambda (x) (list (car x) (cadr x)))
lst))))))
(defun combine-line (top bottom)
(mapcar #'+ top (max-line bottom)))
(defun euler-067 ()
(labels ((f (triangle)
(if (= (length (car triangle)) 1)
(caar triangle)
(let ((new-line (combine-line (cadr triangle)
(car triangle))))
(f (cons new-line (cddr triangle)))))))
(f (read-triangle))))
解答よんでたら、reduce 使ってたのがあったので、こっちのほうが何やってるかわかりやすいかも。
(defun max-line-reduce (lst)
(loop for i from 0 to (- (length lst) 2)
collect
(reduce #'max (car *sample-triangle*) :start i :end (+ i 2))))
これはかっこよすぎる。
(defun collapse-row (longest smallest)
(map 'list #'(lambda (l1 l2 s) (+ s (max l1 l2)))
longest (rest longest) smallest))
(defun collapse-all (triang)
(reduce #'collapse-row (reverse triang)))