Clojure入門 - Project Eulerを解いてみる 問３１ 続々

前回からの続き。

さて、前回で大体3倍ほど高速化できたのだが、見直してみると大量にcoin-pileを作成し続けている。最初の解き方よりは減っているのだが、そもそもいらないんじゃないか？

つまり、coin-pileとして組み合わせ自体を作成するのではなく、あくまで1..n-1までの組み合わせの数だけでnの組み合わせの数を決定することができるのではないだろうか。

一回目の解法だとcoin-pileの重複をdistinctを使って取り除いていたので実際のcoinの集まりをモデル化する必要があった。

「『現在使われている最大のコインと同じかそれより大きな値のコインしか追加しない』という制約をかけると重複が避けられる」という点を利用すれば、そもそもコインの組み合わせを作成して数えるのではなく、組み合わせかたの数を数値として直接扱うことができる。

まずは基本的なデータを用意：

(def coins [1 2 5 10 20 50 100 200])
(def null
  (into {} (map vector coins (repeat 0))))
(def data [(assoc-in null [1] 1)])

お馴染みのコインのvectorを作り、それを使って他のデータを定義。

とりあえず全部の値が0に初期化されているnullというmapを用意。

mapは使っている最大のコインをkeyとして、ある金額に合計するコインの集まりが何通りあるかを記録する。

dataというvectorに金額ごとにmapを一つ入れていく。便宜上、0は最大のコインが1pの集まりで作る方法が一通りだけある、と定義しておく。

次に、金額n-1まで埋まっているdataに金額nのmapを追加する関数：

(defn update-data [data n]
  (letfn [(f [target coin]
             (->> (get data (- n coin) {})
                  (filter #(>= coin (key %)))
                  (map second)
                  (apply +)
                  (assoc-in target [coin])))]
    (conj data (reduce f null coins))))

値xのコインを追加するとnになる金額(n-x)を、x以下の値のコインしか使わずに作る組み合わせの数を求める。それら組み合わせにコインxを加えれば、最大のコインがxという制約の中で金額nを作る方法の数が求められる。

reduceを使い、コイン全種で順次計算してnull mapを更新し、dataに加える。

それを1~nまで順番に更新していく関数：

(defn update-data-to [n]
  (->> (range n)
       (map inc)
       (reduce update-data data)))

n=200で計算し、最後のmapの値の合計が200pに合計するコインの組み合わせの総数となる。

(->> (update-data-to 200) last vals (apply +))

これを走らせてみると、約8ms。前回の20秒に比べて2500倍。あと、よく見るとO(n)のようだ。