Skip to content

Instantly share code, notes, and snippets.

@bouzuya
Created December 22, 2012 01:48
Show Gist options
  • Save bouzuya/4356980 to your computer and use it in GitHub Desktop.
Save bouzuya/4356980 to your computer and use it in GitHub Desktop.
;;; 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)))
@ypsilon-takai
Copy link

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

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

@plaster
Copy link

plaster commented Jan 3, 2013

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

@emanon001
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment