Euler : Problem 82

Posted by YpsilonTAKAI On 2012年5月2日水曜日 0 コメント
数字の入った盤面を移動するコストの問題その2

今回は右と上下のどちらにでも移動できます。







5行の盤面のあるとなりあう2列A、Bを考えます。

A1 B1
A2 B2
A3 B3
A4 B4
A5 B6

このとき、A列のそれぞれのマスまでの最小のコストが判明しているとすれば、B列の最小のコストが計算できます。

たとえば、任意のA列からB2へのルートは、法則に従えば、
 - A1 B1 B2
 - A2 B2
 - A3 B3 B2
 - A4 B4 B3 B2
 - A5 B5 B4 B3 B2
の5通りになります。
A列ではそこまでの最小コスト、B列ではそのマスのコストを採ると、それぞれのルートを通ったときのコストが計算でき、B2までの最小コストが計算できます。
そして、一番左の列の最小コストはその列そのもののコストなので、2列目から順に全ての最小コストを計算していけば、答が出ます。


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 82 : 2012/5/1
;;"Elapsed time: 16901.444026 msecs"
(defn allnums-between [a b]
(if (> a b)
(range b (inc a))
(range a (inc b))))
(defn sum-of-col [m col row1 row2]
(reduce + (map #(get-in m [% col]) (allnums-between row1 row2))))
(defn cost-of [start end [cell-dat cost-dat]]
(+ (get-in @cost-dat start 0)
(sum-of-col cell-dat (second end) (first start) (first end))))
(defn minimum-cost [yx dat]
(let [size-row (count @(second dat))
prev-col-list (map #(vector % (dec (second yx)))(range size-row)) ]
(apply min
(map (fn [start]
(cost-of start yx dat))
prev-col-list))))
(defn calc-all-min-cost [node-dat cost-dat]
(let [size-row (count node-dat)
size-col (count (first node-dat))]
(doseq [col (range size-col), row (range size-row)]
(swap! cost-dat assoc-in [row col] (minimum-cost [row col] [node-dat cost-dat])))))
(require '[clojure.java.io :as io])
(defn pe-82-with-file [input-file]
(with-open [in-file (io/reader input-file)]
(let [node-dat (vec (map (fn [line-dat]
(vec (map (fn [s] (Integer. s))
(.split line-dat ","))))
(line-seq in-file)))
cost-dat (atom (vec (repeat (count node-dat) [])))]
(do (calc-all-min-cost node-dat cost-dat)
(apply min (map last @cost-dat))))))
;; test data
(def cell-dat [[131 673 234 103 18]
[201 96 342 965 150]
[630 803 746 422 111]
[537 699 497 121 956]
[805 732 524 37 331]])
(def cost-dat (atom [[][][][][]]))
view raw pe_82.clj hosted with ❤ by GitHub



・ allnums-between
 aとbの間の数を返す関数。 2 と 5 なら 2 3 4 5が返ります。

・ sum-of-col
 指定の列のn行目からm行目のコストを加算する。

・ cost-of
 となりあった2列の指定の場所から指定の場所までの総コストを計算します。
 上の説明のルートの計算です。

・ minimum-cost
 指定のマスのコストを計算します。
 1つ前の列の最小コストが計算されていることが前提です。
 1つ前の列の全てのマスからそのマスまでの全てのコストを計算して、最小値をそのマスのコストとします。

・ calc-all-min-coste
 いちばん左の列から順に、最小コストを計算します。
 0列めは計算対象外なのですが、ガードに0が出るようにすることで、計算に含めてしまっています。時間的にはロスですね。

・ pe-82-with-file
 ファイルからデータを読んで、計算する関数に渡して、最後に最小の値を取ります。


ラベル: ,

0 コメント:

コメントを投稿