Euler : Problem 18

Posted by TAKAIY On 2011年5月4日水曜日 0 コメント

あとから巨大版が出てくるから、ここで工夫をしないとだめだよみたいなことが書いてある。
これも動的計画法って感じでしょうか。一応、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)))))

;;

0 コメント:

コメントを投稿