Project Euler 67

2016-05-21 07:07:36

整数トライアングルの和の最大値を求める問題。

苦手だった問題。こういう考え方 で実装すれば楽だ。見方を変えるのは大切だし、データ構造はもっと大切。

(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)))