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

第三十一問

合計で200p（２００ペンス＝２ポンド）になるコインの組み合わせが何通りあるかを計算する。

まずはコインの定義。

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

次に、コインの集まりをcoin-pileと呼び、coin-listに含まれるコインの値とそのコインがいくつあるか、のhash-mapとして表現する。とりあえず、すべてのコインの数が0のno-coin-pileを作成。

(def no-coin-pile 
  (apply hash-map (interleave coin-list (repeat 0))))

次に、coin-repというデータ構造を定義。ある金額と、その金額に合計するコインの組み合わせ全部のvectorのhash-map。

(def starting-coin-rep
  {0 [no-coin-pile]})

最初は0と、0pに合計する唯一のcoin-pileであるno-coin-pileのみ含まれたvectorとのhash-map。

このhash-mapに、順次1p, 2p... 200pと追加していく。

まず、(n-1)pまでの金額が入力されているcoin-repを受け取り、金額nの分のコインの組み合わせを加えた新たなcoin-repを返す関数。

(defn update-coin-rep [coin-sum current-coin-rep]
  (let [coins-to-add        
          (filter #(<= % coin-sum) coin-list)
        coin-piles-to-add-to     
          (map #(get current-coin-rep (- coin-sum %))
               coins-to-add)
        add-coin-to-coin-pile
          (fn [coin coin-pile] 
            (update-in coin-pile [coin] inc))
        add-coin-to-coin-piles  
          (fn [coin coin-piles] 
            (map #(add-coin-to-coin-pile coin %) 
                 coin-piles))]  
    (->> (map add-coin-to-coin-piles 
              coins-to-add coin-piles-to-add-to)
         (apply concat)
         distinct
         (assoc current-coin-rep coin-sum))))

ここの名前付けを含めて以下に読みやすくするかが一番時間のかかる部分だった。

次に、1からnまで再帰的にcoin-repを更新していく関数。

(defn update-to-n [n]
  (loop [coin-sum         1 
         current-coin-rep starting-coin-rep]
    (if (> coin-sum n)
        current-coin-rep            
        (recur (inc coin-sum) 
               (update-coin-rep coin-sum current-coin-rep)))))

あとは組み合わせるだけ。

(defn count-coin-sum [n]
  (-> (update-to-n n)
      (get n)
      count))

(count-coin-sum 200)

これだと答えが出るのに大体１分強かかる。もっと早くできるはず。

ぱっと見、個々の計算が過去の結果に強く依存するので並列化はあまりうまくいかなそう。

しかし、そもそもupdate-coin-repの中でdistinctを使っているので、かなり無駄にcoin-pileを生成しては消していることになる。そこを減らせば並列化せずともかなり効率化が図れる。

ということで続く。