problem-15.clj

;;; Project Euler #15
;;; http://projecteuler.net/problem=15
;;; http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

(require '[clojure.test :refer [deftest is]])

(defn fact
  [n]
  (loop [n n r 1]
    (if (zero? n)
      r
      (recur (dec n) (*' r n)))))

(defn problem-15
  ([] (problem-15 20 20))
  ([m n] (/ (fact (+ m n)) (*' (fact m) (fact n)))))

(deftest fact-test
  (is (= (fact 0) 1))
  (is (= (fact 1) 1))
  (is (= (fact 4) 24))
  (is (= (fact 20) 2432902008176640000))
  (is (= (fact 40) 815915283247897734345611269596115894272000000000N)))

(deftest problem-15-test
  (is (= (problem-15 1 1) 2))
  (is (= (problem-15 1 2) 3))
  (is (= (problem-15 2 2) 6))
  (is (= (problem-15) 137846528820N)))

解説

Clojure らしい何かをやりたかったのですが、思い浮かばないので普通に。

• * を使ってしまうと integer overflow するので *'
• loop と recur の素直な末尾再帰
• @kohyama にならって最低限のものを require ( https://gist.github.com/4335755 )
• deftest つけてみた ( VimClojure の \rt は deftest がないとダメぽいので )

遊びの少ないコードで申し訳ない。

Clojure らしい何かをやりたかったのですが、思い浮かばないので普通に。

(n+m)Cm を階乗 (fact) を使って計算する教科書どおりの解法ですね．Clojure の特徴を前面に押し出すとか，Clojure によくあるパターンを使うとかという意味では，この問題の難易度は高いと思います．

• を使ってしまうと integer overflow するので *'

*' を使って BigInt に自動昇進させているあたりは Clojure っぽいですね．

しかし，この問題の答えを見てみると long の範囲なので *' を使わなくても計算できるはず，と考えて作ったのがこの回答です．Ratio を整数に戻したときに BigInt になるので一緒といわれれば一緒なのですが，ネタ解答まで．

(defn combination
  [n m]
  (->> (concat (range 1 (inc n)) (range 1 (inc m)))
       (map / (range 1 (+ n m 1)))
       (reduce *)))

違う方式で解いてみました。 動的計画法でしょうかね？

https://gist.github.com/4360329

中学生とかのときに習った方法です。 この方法だと、途中の道が通れなかったりしたときにも対応できるので、好きな方法です。

違う方式で解いてみました。 動的計画法でしょうかね？

https://gist.github.com/4360329

動的計画法 (DP; Dynamic Programming) 私は苦手です．@ypsilon-takai の解答はメモ化テーブルに atom を使っていたり，通れない点があっても計算できたりと一般化できるので参考になりました．ただし，この問題に限れば，ある点への経路数を計算するのに左の点への経路数とと上の点への経路数だけあれば十分なので，

(defn dp
  [n m]
  (-> (iterate #(reductions + %) (repeat 1))
      (nth n)
      (nth m)))

で DP できてしまいます．自分で書いていて何だか嘘っぽいプログラムだと思っていたのですが，実行してみたら正解を出せました．しかも，nm 個のオブジェクト生成と nm 回の加算だけなので実行時間は <1ms です．

これで「Clojure すごい」と言いたいところなのですが，私が DP を苦手としているせいもあって，Clojure では DP をうまく書けません．私が DP するときには多重ループを回して配列を更新していくように書くのですが，Clojure では Java や C++ と比較して配列計算を短く書けないのでいつも難儀しています．DP に限っては Clojure より Java のほうが書き易いです．Immutable なデータ構造を使って速い DP を書ければよいのですが，その方法の見当すらつきません．

---

というわけで，

緩募

Immutable なデータ構造とか遅延評価を用いて DP する方法を解説した本とか論文とか，何か文書があれば誰か教えてください．Clojure で使えるテクニックだったら嬉しいです．

@bouzuya
無駄無く簡潔で理想的な解答と思います.

@tnoda, @bouzuya
2nCn ですから, 先に約分して,

(defn problem-15
  ([] (problem-15 20N))
  ([n]
    (let [p (inc n) q (inc (* 2 n))]
      (/ (apply * (range p q))
         (apply * (range 2 p))))))

でも良いかも知れません.
何処で BigInt に昇格させるのが良いのかは悩みます.

@ypsilon-takai, @tnoda
動的計画法かっこいいですね.
時間があるときに調べてみたいです.

@tnoda の dp のソースは、かなり衝撃です。 こんなん書けるようになりたいですねぇ。

この式の意味するところを理解できていないんですが、全てが遅延シーケンスでできているあたりは、すごくclojureっぽいですね。

私も解いてみました。
組み合わせについての知識を使わずに(というか式が立てられると思ってませんでした……)、再帰してます。
同じ計算を何度もすることになるので、別の問題で紹介されていたmemoizeを使ってみました。

(def solve
  (memoize
    (fn [w h]
      (if (or (zero? w)
              (zero? h))
        1
        (+ (solve (dec w) h)
           (solve w (dec h)))
        ))))

(solve 20 20) と使います。

僕も解いてみました。
@bouzuya と殆ど同じですが、階乗の処理は recur による明示的な再帰ではなく、計算に必要な数列を予め用意しています。

(defn factorial
  [n]
  (apply *' (range 1 (inc n))))

(defn combination
  [n m]
  (/ (factorial n)
     (*' (factorial m)
         (factorial (- n m)))))

(defn solve
  [n m]
  (combination (+ n m) n))

(solve 20 20)

---

deftest は何に対するテストなのかが明確になるのでいいですね。ネストすることも可能なので重宝しています。