Y箱

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

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

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

;;