Euler : Problem 81

Posted by YpsilonTAKAI On 2012年5月2日水曜日 0 コメント
四角に並んだ数の角から角まで行くときの最小コストの計算

これは動的計画法ですね。
67の問題とほぼ同じなので、同じやりかたで解いてます。







この問題は三角にならんでないですけど、無いところは適当な数を入れます。
問題は、最小になるルートなので、1000000を入れてます。
nilとかにして、計算対象外にしようかとも思ったのですが、面倒なのでやめ。

コードも67とほとんど同じ。

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 81 : 2012/4/26
;;"Elapsed time: 96.125842 msecs"
(defn get-nth-line [mat n]
(map #(get-in mat % 1000000)
(map vector
(range 0 (inc n))
(range n -1 -1))))
(defn change-form [m]
(let [size (count m)]
(map #(get-nth-line m %)
(range 0 (+ size size -1)))))
(defn pe-80 [input-list]
(apply min
(reduce (fn [root new]
(let [rt-r (cons 1000000 (vec root))
rt-l (conj (vec root) 1000000)]
(map #(min (+ %1 %2) (+ %1 %3))
new rt-l rt-r)))
(change-form input-list))))
;; Support func to read data from the file.
(require '[clojure.java.io :as io])
(defn pe-80-with-file [input-file]
(with-open [in-file (io/reader input-file)]
(pe-80
(vec (map (fn [line-dat]
(vec (map (fn [s] (Integer. s))
(.split line-dat ","))))
(line-seq in-file))))))
;; sample data
(def dat1
[[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]])
;; form changed
((131)
(673 201)
(234 96 630)
(103 342 803 537)
(18 965 746 699 805)
(1000000 150 422 497 732 1000000)
(1000000 1000000 111 121 524 1000000 1000000)
(1000000 1000000 1000000 956 37 1000000 1000000 1000000)
(1000000 1000000 1000000 1000000 331 1000000 1000000 1000000 1000000))
view raw pe_81.clj hosted with ❤ by GitHub


・ get-nth-line
 今回の問題は、四角にならんでますが、斜めに見ていくので、n番目の列を取る関数。

0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9

4番目は4のところが取れるわけです。
で、データの無いところでは、1000000 が出てきます。

・ change-form
 三角形になるように順にデータを取ってくる関数。
 問題文の内容を食わせると、一番下のようになります。

・pe-80
 できた三角形を上から下にたどっていって、最大値を残してリストを生成します。

・pe-80-with-file
 ファイルから読んだデータで計算する。




ラベル: ,

0 コメント:

コメントを投稿