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)))

@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 は何に対するテストなのかが明確になるのでいいですね。ネストすることも可能なので重宝しています。