Arantium Maestum

プログラミング、囲碁、読書の話題

Clojure入門 - Project Eulerを解いてみる 問31 続

前回からの続き。

戦略をちょっと変えてみる。

前回は「ある金額nに合計するコインの組み合わせを求めるために、x=1, 2, 5 ... 200の各コインでn-xに合計するコインの組み合わせにもう一枚xを加える形で、コインの組み合わせのリストを作成し、重複したものを取り除く」という方式だった。

今回は「すでに計算してある金額nに合計するコインの組み合わせから、コインを一枚追加することで作成できる組み合わせをn+xの金額の組み合わせリストに加える。ただし重複を避けるため、xより小さいコインがすでに含まれる組み合わせは除外する」という方式にする。0に合計する空のコインリストから始めて順次n=199までやっていけばn=200の組み合わせのリストが漏れ・重複なく出来上がる。

まずコインの種類と最終的なnの定義。

(def coin-list [0 1 2 5 10 20 50 100 200])
(def coin-total 200)

データ構造をhash-mapからただのvectorにする。coin-pileは整数の要素9のvectorで、coin-repはcoin-pileのリストが201あるvector

空のcoin-pileと、それをn=0にセットしたstarting-coin-repを作成。

(def no-coin-pile 
  (into [] 
    (for [x coin-list] 0)))

(def starting-coin-rep 
  (into [[no-coin-pile]]
    (for [i (range coin-total)] [])))

coin-pileから合計金額を計算する関数。

(defn get-sum [coin-pile]
  (->> coin-pile
       (map vector coin-list)
       (map #(apply * %))
       (apply +)))

次が肝で、あるcoin-pileに一つコインを加えることで到達できるcoin-pileのリストを返す関数。前述の通り、重複を避けるためすでに含まれている最小のコインより大きいコインは加えないという制約をつけている。

その関数を使って複数のcoin-pileからの到達可能coin-pileのリストを返す関数も定義しておく。

(defn pile->reachables [coin-pile]
  (for [i (range 1 9)
        :let [last-coin-count (nth coin-pile (dec i))]
        :while (zero? last-coin-count)]
    (update-in coin-pile [i] inc)))

(defn piles->reachables [coin-piles]
  (apply concat (map pile->reachables coin-piles)))

到達できるcoin-pileをcoin-repの正しい額に登録する関数。

(defn merge-into [coin-rep coin-pile]
  (let [coin-sum (get-sum coin-pile)]
    (if (>= coin-sum (count coin-rep))
      coin-rep
      (update-in coin-rep 
                 [coin-sum] 
                 #(cons coin-pile %)))))

実はこれを(try _ (catch java.lang.NullPointerException ex coin-rep))でもやってみたのだが何故か間違った答えが出る。要研究である。

あとはこれを踏まえてcoin-repを一段階進める関数、n段階進める関数、coin-repのすべてを埋める関数。

(defn expand-rep [coin-rep i]
  (let [coin-piles  (nth coin-rep i)
        reachables  (piles->reachables coin-piles)]
    (reduce merge-into coin-rep reachables)))
  
(defn expand-upto-n [coin-rep n]
  (reduce expand-rep coin-rep (range n)))
  
(defn fill-coin-rep [coin-rep]
  (expand-upto-n coin-rep (dec (count coin-rep))))

初期設定のcoin-repを埋めて、最後(n=200)のvectorに含まれる要素数が200pに合計するコインの組み合わせの数。

(-> starting-coin-rep
    fill-coin-rep
    last
    count)

これで20秒ほど。約3倍の高速化で、このノート上で並列化するのとまあ大体同じレベルのスピードアップ。ここで終わってもいい気がするが、さらに高速化できそうなので続く。

ちなみに今回はまず紙と鉛筆でコードを書いてみたのだが、そうすると名前が変だったりloop/recurな再帰だらけだったりと酷いことになった。それをコンピュータ上に移してから鬼のようにrefactorして、名前を短めに統一させたりloop/recurをreduceにできるよう関数を分割・引数整理した。手で書いてやるのは難しそうなのだが、カード時代から連綿と受け継がれてきた机上refactoringのテクニックとかあるんだろうか。

続きに飛ぶ