Project Euler Problem 9 solution in Clojure (#mitori_clj)

pe-9.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])

pe-9_2.clj

;; ピタゴラス数チェック
(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])

解説

naiveなgenerate and testです。

全体の構成として、書きやすさ重視で和が一定の組みをgenerateしてピタゴラス数かどうかのチェックをしましたが、
もしかすると、逆の方が高速に見つけられるのかも? しれません。

pythagorean?

testの方です。

candidates

generateの方です。
練習も兼ねてforマクロで実現しています。
複数の変数を動かしたときの結果を平坦なリストで生成するのはこれがとてもやりやすいと思います。
cが小さすぎるときにbを回してるのが無駄なのと、
小さすぎるbが対象になり得るrangeも無駄なので、
このあたりを削るようにすると少し速くなりそうですが
どのくらいかは試していません。オーダーは変わらないかも？

👍

参考まで, 候補となる a, b, c の列挙部分の別解です.
a < b < c も a + b + c = n も条件として入れてしまい,

(for [a (range 1 (quot n 3))
      b (range (inc a) (quot (inc (- n a)) 2))
      :let [c (- n a b)]
      ...]
  ...)

と書けます.
ただしコンピュータに解かせているというより自分が解いてるみたいで嬉しくないです.
ピタゴラス数のチェックは同じ for の中に :when で入れてしまっていいかもしれません.

👍 十分速い (<100ms) のでこれで答えがでたら，私なら満足してしまいます． @kohyama のコメントはいつも参考になります．

@tnoda 確かにこの問題を解くにはこれで十分なのですが、たとえば10倍にすると結構重くなるのですよね。
ところでこのコードで :warn-on-reflection true 設定して lein run したところ、

Reflection warning, NO_SOURCE_PATH:1 - call to invokeStaticMethod can't be resolved.

と言われてしまい、そしてどこなのかが見当ついていません。こういうときどうやって探すのがよいのでしょう？

@kohyama 最初から絞り込んでみました(pe-9_2.clj candidates2)。書き方的にはあんまり嬉しくないですが、結構効きますね。
あと、ピタゴラス数チェック、一緒に書くようにして反映しました。
最初はfilterで書いてたのを、こっちもforでいいやとしてみた流れだったのですが、ちょっと詰めが甘かったようです。

リスト内包表記を有効に使用している良い例だと思います。
普段はあまりリスト内包表記を使用しないので、とても参考になります。(:let とか見たことなかった)

---

別解として、clojure.contrib.combinatorics/combinations を用いて (a, b, c) の組合せを作成するものを載せておきます。
効率化を全く行なっていないので、ひどく遅いです。

(ns projecteuler-answers.problem-009
  (:use clojure.contrib.combinatorics))

(defn pythagorean?
  ([[a b c]] (pythagorean? a b c))
  ([a b c]
   (= (* c c) (+ (* a a) (* b b)))))

(defn candidates
  [n]
  ((comp (partial filter (every-pred #(= n (apply + %)) pythagorean?))
         (partial map sort)
         #(combinations % 3))
     (range 1 (inc n))))

(defn solve
  [n]
  (map (juxt identity (partial apply *))
       (candidates n)))

(time (solve 1000)) ; "Elapsed time: 0.85 msecs" とか出るが、どう考えても 5分くらいかかっている。

@plaster

@tnoda 確かにこの問題を解くにはこれで十分なのですが、たとえば10倍にすると結構重くなるのですよね。
ところでこのコードで :warn-on-reflection true 設定して lein run したところ、

Reflection warning, NO_SOURCE_PATH:1 - call to invokeStaticMethod can't be resolved.

と言われてしまい、そしてどこなのかが見当ついていません。こういうときどうやって探すのがよいのでしょう？

invokeStaticMethod can't be resolved と出たときには絶望的にどこか分からないので，私ならあきらめます．しかし，おそらくは，この場合に限っては無視してよいと思います．というのも，コードを見る限りそんなところはなく，-main が出しているのでなければ，lein run が出している可能性が高いからです．

invokeStaticMethod can't be resolved でない一般的な警告の場合，警告文にメソッド名が含まれます．たとえば，

user> #(Character/digit % 10)
Reflection warning, NO_SOURCE_FILE:1 - call to digit can't be resolved.
#<user$eval1958$fn__1959 user$eval1958$fn__1959@7e41986c>

の場合は，digit というメソッド名が明記されています．私の経験でいれば，*warn-on-refrection* true で怒られるときは，コンパイルの際に Java のメソッド呼び出しの箇所で型推論に失敗している場合がほとんどですので，見当をつけるために，警告に含まれる Java のメソッドを使っている defn/def を，SLIME/REPL を使って片っ端から eval っていきます．これで大体見つかります．

あまりに数が多くて面倒なら，:gen-class して，AOT コンパイルでチェックします．

@emanon001

(time (solve 1000)) ; "Elapsed time: 0.85 msecs" とか出るが、どう考えても 5分くらいかかっている。

solve 関数が LazySeq を返しているからだと思います．試しに REPL で

• (type (first (solve 1000)))
• (type (solve 1000))

を実行して結果を確認してみたらどうなりますか?

clojure.lang.LazySeq なら，まだ計算は実行されていません．LazySeq の中身には (fn [] (solve 1000)) が入っていて，first されてはじめて，その fn が実行されて (solve 1000) が計算される，というのが私のイメージです．

@tnoda
あー、そうか。LazySeq を返していて、それに対して何の操作も行なっていないなら、そりゃ計算は実行されないですね……。
REPL で評価結果を表示するなど、LazySeq から値を取得する必要が生じて初めて計算が実行される、というわけですね。
ああ、この辺り理解したつもりになっていたけど、まだ勉強が足りていない……。

@tnoda これを質問するなら -main も貼っておくべきでした。失礼しました。

(defn -main
  [& args]
  (println (solve 1000))
  )

これだったのですが、中身を 0 とかにしても同じReflection warning が出たので、確かにleiningenの中っぽいです。
頂いた例 #(Character/digit % 10) をソースにいれてみたところ

Reflection warning, pe_9/core.clj:54 - call to digit can't be resolved.

のように、ちゃんと出てきました。ありがとうございます。

あと、今までどうも勘違いしていたのですが、「reflectionを使うようにコンパイルされる場合に（コンパイル時に）警告」ではなく、「reflectionを使ったら（ランタイムに）警告」なのですね。

@plaster

あと、今までどうも勘違いしていたのですが、「reflectionを使うようにコンパイルされる場合に（コンパイル時に）警告」ではなく、「reflectionを使ったら（ランタイムに）警告」なのですね。

私の書き方がまぎらわしくて誤解させていたのならごめんなさい．警告はコンパイル時に出ていると思います．ここでいうコンパイルとは，

.clj → コンパイル → バイトコード (.class) → 実行

という手順に出てくるコンパイルという意味です．

ためしに，リフレクションを使うような defn を REPL で eval ってみてください．defn で定義される関数を実行しなくても（= リフレクションを使わなくても），警告されると思います．

確かに、実行時ではなかったです。ありがとうございます。

pe-9.core=> (defn f [x] (Math/abs x))
Reflection warning, NO_SOURCE_PATH:1 - call to abs can't be resolved.
#'pe-9.core/f

では警告が1度だけ出るのに、中身を使う

pe-9.core=> (apply list (map f [1 -2.2 3.33 -4.444]))
(1 2.2 3.33 4.444)

では一度も出ませんでした。

オーバーロードの解決ができないときにreflectionが使われるみたいですね。Mathは特に速いことが望まれる場面多そうですし、一方で long と double のオーバーロードだらけなので、注意が要りそうです。

私が「コンパイル時に警告」でないと思ったのは lein compile で警告が出なかったためだったのですが、
rm -r target; lein compile したところ、期待どおり

Compiling pe-9.core
Reflection warning, pe_9/core.clj:54 - call to abs can't be resolved.

の警告メッセージを得ることができました。
しかも、最初に私が悩んだ

Reflection warning, NO_SOURCE_PATH:1 - call to invokeStaticMethod can't be resolved.

は出ていないので、こちらは私が書いた部分のコードには直接関係ない警告メッセージだったというのも確定ですね。
いろいろすっきりしました、本当にありがとうございます。

@plaster

オーバーロードの解決ができないときにreflectionが使われるみたいですね。Mathは特に速いことが望まれる場面多そうですし、一方で long と double のオーバーロードだらけなので、注意が要りそうです。

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

user> (defn str* [x] (.toString x))
Reflection warning, NO_SOURCE_FILE:1 - reference to field toString can't be resolved.
#'user/str*

で，これも，

user> (defn date->str [^java.util.Date x] (.toString x))
#'user/date->str

のように型ヒントをつけてあげると怒られなくなりますね．

@tnoda

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

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