Project euler 15 retry

pe_15_retry.md

##解説

去年最初に解いたときもそうしたのですが、今見るとかなりごてごてしたコードになっているので、ちょっとすっきりさせてみました。

スピードは速くなってます。 "Elapsed time: 21.310858 msecs"

##方式

前のルートからの合計を足していく方法です。動的計画法なんでしょうかね？ このサイトの問題2で説明されている方法と同じです。

prev-points

ある点の前の点のリストを出します。 The Joy of Clojure にあった処理からヒントを得ています。

calc-score

前にあるポイントからそのポイントの値を計算します。

その2

下のァイルは、今回のやりなおしで最初にできたものです。斜めにスキャンしようとしているので、ごたごたしています。手作業だとこの手順ですが、面倒な方式ですね。

pe_15_retry_1.clj

(require '[clojure.test :as test])

;; Find previous points
(defn prev-points 
  ([xy] (prev-points [[-1 0] [0 -1]] xy))
  ([deltas xy]
     (filter (fn [new-xy]
               (every? #(< 0 %) new-xy))
             (map #(mapv + xy %) deltas))))

(test/is (= (prev-points [4 4])
            '([3 4] [4 3])))
(test/is (= (prev-points [1 3])
            '([1 2])))

;; Calc value form previous points.
(defn calc-score [grid point]
  (if (find @grid point)
    (get @grid point)
    (let [sum-parent-points (->> (prev-points point)
                                 (map #(get @grid %) ,,)
                                 (reduce + ,,))]
      (do (swap! grid assoc point sum-parent-points)
          sum-parent-points))))

(test/is (= (calc-score (atom {[3 1] 3 [2 2] 5}) [3 2])
            8))

;; solve
(let [grid (atom {[1 1] 1})
      size-x 20
      size-y 20]
  (->> (for [y (range 1 (+ 2 size-y))
             x (range 1 (+ 2 size-x))]
         [x y])
       (map #(calc-score grid %) ,,)
       (last ,,)))

pe_15_retry_2.clj

;; 
(defn prev-points 
  ([xy] (prev-points [[-1 0] [0 -1]] xy))
  ([deltas xy]
     (filter (fn [new-xy]
               (every? #(< 0 %) new-xy))
             (map #(mapv + xy %) deltas))))

(test/is (= (prev-points [4 4])
            '([3 4] [4 3])))
(test/is (= (prev-points [1 3])
            '([1 2])))


(defn scan-rectangle [x-size y-size]
  (concat (map vector (concat (range 1 (inc x-size))) (repeat 1))
          (map vector (repeat x-size) (range 2 (inc y-size)))))

(test/is (= (scan-rectangle 4 4)
            '([1 1] [2 1] [3 1] [4 1] [4 2] [4 3] [4 4])))

(defn scan-diagonal [[start-x start-y]]
  (map vector (range start-x 0 -1)
       (range start-y (inc start-x))))

(test/is (= (scan-diagonal [4 1])
            '([4 1] [3 2] [2 3] [1 4])))

(defn calc-score [grid point]
  (if (find @grid point)
    (get @grid point)
    (let [sum-parent-points (->> (prev-points point)
                                 (map #(get @grid %) ,,)
                                 (reduce + ,,))]
      (do (swap! grid assoc point sum-parent-points)
          sum-parent-points))))

(test/is (= (calc-score (atom {[3 1] 3 [2 2] 5}) [3 2])
            8))

(let [grid (atom {[1 1] 1})
      size-x 20
      size-y 20]
  (last (->> (scan-rectangle (inc size-x) (inc size-y))
             (mapcat scan-diagonal ,,)
             (map #(calc-score grid %) ,,))))