Euler : Problem 15

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

碁盤の目の通路の問題です。
まあ、普通にやるんだったら、組み合わせで解くんだけれども、やってみたら、すごく時間がかかる。

んで、交差点ごとの数を数えあげる方法を実装してみた。
動的計画法にあたるかな?

3x3だと

1 1 1
1 2 3
1 3 6

てな感じ。

実際の計算で使っているのは update-child と 最後のループのところだけ。
あとは、データ作成のためのもの。

;;
;; Problem 15 : 2011/4/22
;;"Elapsed time: 32.748855 msecs"

;; too long time
(use 'clojure.contrib.combinatorics)
(count (combinations (range 40) 20))

;; grid parameter
(def *grid-x-max* 21)
(def *grid-y-max* 21)

;; data structure
;; [x y] {:val :next-node }
(defstruct grid-node
:val :next-node)

;; create child node list
(defn get-grid-child [x y]
(filter #(not (nil? %))
(vector (if (< x (dec *grid-x-max*))
[(inc x) y])
(if (< y (dec *grid-y-max*))
[x (inc y)]))))

;; create new *nodes* table
(def *nodes*
(loop [val-list (for [i (range *grid-x-max*) j (range *grid-y-max*)]
(let [data (struct grid-node (atom 0)(get-grid-child i j))]
[[i j] data]))
res-map {}]
(if (empty? val-list)
res-map
(recur (rest val-list)
(assoc reset!
(first (first val-list))
(second (first val-list)))))))

;; display *nodes* :val data
(defn disp-node-table [table]
(partition *grid-x-max*
(for [i (range *grid-x-max*) j (range *grid-y-max*)]
@(:val (table [i j])))))

;; update child
(defn update-child [parent-val child-list]
(if (not (empty? child-list))
(let [target-child (first child-list)]
(do
(swap! (:val (*nodes* target-child)) #(+ parent-val %))
(update-child parent-val (rest child-list))))))


;; set initial val
(reset! (:val (*nodes* [0 0])) 1)

;; calc all nodes
(loop [nodes-in-my-hand [[0 0]]]
(if (not (empty? nodes-in-my-hand))
(let [target (first nodes-in-my-hand)
child-node (:next-node (*nodes* target))]
(do
(update-child @(:val (*nodes* target)) child-node)
(recur (distinct (into (apply vector (rest nodes-in-my-hand)) child-node)))))))

;;

0 コメント:

コメントを投稿