Y箱

あとから巨大版が出てくるから、ここで工夫をしないとだめだよみたいなことが書いてある。
これも動的計画法って感じでしょうか。一応、O(n)だし。

;;
;; Problem 18  : 2011/4/27
;; "Elapsed time: 9.528585 msecs"
(def org-data '((75)
               (95 64)
               (17 47 82)
               (18 35 87 10)
               (20  4 82 47 65)
               (19  1 23 75  3 34)
               (88  2 77 73  7 63 67)
               (99 65  4 28  6 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  4 68 89 53 67 30 73 16 69 87 40 31)
               ( 4 62 98 27 23  9 70 98 73 93 38 53 60  4 23)))


(defstruct grid-node
  :weight :val)

(defn make-line-data [node-list target-list res-map]
  (if (empty? node-list)
    res-map
    (let [node (first node-list) target-data (first target-list)]
      (recur (rest node-list) (rest target-list)
             (assoc res-map node (struct grid-node target-data (atom target-data)))))))

(defn create-node-data [n]
  (for [i (range n)]
    [i (dec (- n i))]))

(def *nodes*
     (loop [grid-data org-data
            res-map {}]
       (if (empty? grid-data)
         res-map
         (let [target-list (first grid-data)
               node-data (create-node-data (count target-list))]
           (recur (rest grid-data) (make-line-data node-data target-list res-map))))))

(defn show-data []
  (loop [stage (range (count org-data) 0 -1)
        res-list ()]
    (if (empty? stage)
      res-list
      (recur
       (rest stage)
       (cons (map #(deref (:val (*nodes* %))) (create-node-data (first stage))) res-list)))))
;;

ここまでがデータ定義

上の列から順に合計を作っていく、作った合計が小ければ書きこまないので大きいのが残ると。

;;

(defn update-child [point]
     (let [value @(:val (*nodes* point))
           child-1 [(inc (first point)) (second point)]
           ch-1-weight (:weight (*nodes* child-1))
           child-2 [(first point) (inc (second point))]
           ch-2-weight (:weight (*nodes* child-2))
           ]
       (do
        (swap! (:val (*nodes* child-1)) #(max (+ value %2) %1) ch-1-weight)
        (swap! (:val (*nodes* child-2)) #(max (+ value %2) %1) ch-2-weight))))

                        
(loop [stage (range 1 15)]
  (if (empty? stage)
    nil
    (do
      (dorun (for [target (create-node-data (first stage))]
               (update-child target)))
      (recur (rest stage)))))

;;