Skip to content

Instantly share code, notes, and snippets.

@plaster
Created December 15, 2012 07:21
Show Gist options
  • Save plaster/4291907 to your computer and use it in GitHub Desktop.
Save plaster/4291907 to your computer and use it in GitHub Desktop.
Project Euler Problem 9 solution in Clojure (#mitori_clj)
(use 'clojure.test)
;; ピタゴラス数チェック
(defn pythagorean?
[a b c]
(= (* c c) (+ (* a a) (* b b))))
(is (pythagorean? 3 4 5))
;; 合計が a+b+c かつ 0 < a < b < c になるような組の列挙
;; もう少し効率的に枝刈りできるかもしれない
(defn candidates
[a+b+c]
(for [c (range (+ a+b+c 1))
:let [a+b (- a+b+c c)]
b (range (+ a+b 1))
:let [a (- a+b b)]
:when (< 0 a b c)
]
[ a b c ]
))
(is (every? #(= 1000 (apply + %)) (candidates 1000)))
;; "(a,b,c)の組および解答フォーム入力用の積"
(defn solve [n]
(for [abc (candidates n)
:when (apply pythagorean? abc) ]
[ abc (apply * abc) ]))
;; (solve 1000) => ([[200 375 425] 31875000])
;; ピタゴラス数チェック
(defn pythagorean?
[a b c]
(= (* c c) (+ (* a a) (* b b))))
(is (pythagorean? 3 4 5))
;; 合計が a+b+c かつ 0 < a < b < c になるような組の列挙
;; もう少し効率的に枝刈りできるかもしれない
(defn candidates
[a+b+c]
(for [c (range (+ a+b+c 1))
:let [a+b (- a+b+c c)]
b (range (+ a+b 1))
:let [a (- a+b b)]
:when (and (< 0 a b c) (pythagorean? a b c))
]
[ a b c ]
))
(is (every? #(= 1000 (apply + %)) (candidates 1000)))
;; pe-9.core=> (time (apply list (candidates 10000)))
;; "Elapsed time: 6183.66497 msecs"
;; @kohyamaさんアドバイス版
(defn candidates2
[a+b+c]
(for [a (range 1 (quot (inc a+b+c) 3))
:let [b+c (- a+b+c a)]
b (range (inc a) (quot (inc b+c) 2))
:let [c (- b+c b)]
:when (and (< 0 a b c) (pythagorean? a b c))
]
[ a b c ]
))
;; pe-9.core=> (time (apply list (candidates2 10000)))
;; "Elapsed time: 1469.798884 msecs"
;; ([2000 3750 4250])
;; "(a,b,c)の組および解答フォーム入力用の積"
(defn solve [n]
(for [abc (candidates n) ]
[ abc (apply * abc) ]))
;; (solve 1000) => ([[200 375 425] 31875000])
@plaster
Copy link
Author

plaster commented Dec 22, 2012

@tnoda

もう一つ付け加えると,メソッド呼び出しのレシーバのクラスを型推論できないときも reflection を使うみたいです.

16を解いているときにちょうど疑問に思っていた内容で、大変参考になりました。ありがとうございます。
詳しくはあちらに書きます(が、URL未アナウンスです……)。

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