Project Euler Problem 5 #mitori_clj

problem_5.clj

(ns tnoda.projecteuler.problem-5
  (:import org.apache.commons.math.util.MathUtils) ; [org.apache.commons/commons-math "2.2"]
  (:use clojure.test))

(defn- solver*
  [n]
  (reduce (fn [^long x ^long y] (MathUtils/lcm x y)) (range 1 (inc n))))

(def solver (partial solver* 20))

(is (= 2520 (solver* 10)))

問題文を和訳すると「1 から 20 までの数の最小公倍数を求めよ」となります．最小公倍数を求めるのには Apache Commons Math を使いました．MathUtil クラスの lcm メソッドは 2 引数メソッドなので，1 から 20 までの 20 個の数の最小公倍数を求めるのに LCM(a, b, c) = LCM(LCM(a, b), c) という性質を利用しています．

二引数の lcm で (reduce lcm coll) は模範解と思います.
多引数の lcm を直接実装する別解を誰か御願いします :-)

Apache Commons Math 覚えておきます.
contrib.math の gcd と lcm はどこへいったんでしょう?

拙解

(use 'clojure.test)
(defn pep005 [e]
  (letfn [(gcd [a b] (loop [a a b b] (if (zero? b) a (recur b (mod a b)))))
          (lcm [a b] (* b (quot a (gcd a b))))]
    (reduce lcm (range 2 (inc e)))))
(is (= (pep005 10) 2520))
(pep005 20)

同じく二引数の lcm で reduce してます.
簡単のため, 型とか値の範囲のケアは, この問題に適用する限り, ということで省略して,
gcd とそれを使った lcm を中に書いてしまいました.
1 も省略.

@tnoda 型の指定、存在すら忘れていました。チューニングするときに必須ですよね。覚えます。Apache Commons Mathも初めて知りました。
@kohyama 多引数lcm、ちょっと考えてみようとしたのですが、方針が決まっていません。2引数の場合と違って、多引数gcd作って全部の積を割るとかだとうまくいかないですよね。
あと 1 の対応ですが、(reduce lcm 1 (range 2 (inc e))) だけでできてそうな感じがします。できても大してうれしくありませんが...w

更新しました→ 2b1917d93e0852d6ecbe875a187e772dc912c258

• 元の solver 関数をテスト用の solver* と，解答用の solver とに分けました．
• solver を気持ち悪い方法で作りました．
  • (solver) で答えが出ます．

---

Apache Commons のような既存の Java ライブラリを使ってコーディングの量を減らせるのも，Clojure の長所の一つだと考えています．Maven リポジトリと Leiningen が無ければ Clojure 使っていなかったかもしれないくらい，便利です．

---

@kohyama ユークリッドの互除法ありがとうございます．contrib.math に昔 gcd/lcm あったんですか? 私 1.4 から使い始めたので contrib のことはよくわからないんです．ごめんなさい．探せば，便利なライブラリがたくさんあるんでしょうね．

---

@plaster *warn-on-reflection* って使っていますか? 私は貧乏性なので，コーディング中は常に true です．

@plaster 多引数むちゃぶりすいません. ^^; 私も考えてみます.

@tnoda
それ以上引数無いのに partial. なるほど〜. 面白いです. 今度どっかで使おっと.
*warn-on-reflection* 知らなかったです.
「多次元配列の見えないリフレクションに注意」 読みました.
今まで型ヒント軽視し過ぎだったかも...
配列がっつり使ってるコードがあるから明日ちょっと見直してみよう.

Where Did Clojure.Contrib Go に詳しいんですが, 1.2 の時は結構いろんな物が clojure.contrib という一つのライブラリに入っていたんですけど, 1.3 をきっかけにそれぞれ独立したライブラリとしてメンテナンスされるようになったようです. 応用的なライブラリほど後が追いやすいんですけど, primes とか, gcd とか単機能なものはどこ行ったか見当たらないんですよねぇ〜.
あると便利なんだけど (Project Euler 解くときとか. ね.)

clojure.math.numeric-tower というものを使ったことがあります(lcm 関数があるw)。

1.2までは、いろいろな有用なライブラリがまとまった、clojure-contrib っていうのを使ってますが、1.3で分解されました。最近あまり参照しなくなりましたが、そのとき、いろいろ混乱して、みんなが「あれはどこにいったーーー」って騒いでいたので、こんなページが作られています。

http://dev.clojure.org/display/design/Where+Did+Clojure.Contrib+Go

どんなライブラリがあるかについての情報元としても使えますね。

mathは、上で指摘のとおりnumeric-towerに行ってます。
clojure.contrib.math
Migrated to clojure.math.numeric-tower - lead Mark Engelberg.

人のをちゃんと読んでなくて、かぶってしまった。 すみません。

gcdはnumeric-towerにありますね。

primesなんてあったんですねぇ。調べてみると、ここにありました。 このlazy-seqsライブラリは、継続されなかったみたいですね。 これくらい自分で作れってことでしょうか。

型ヒントは普段使わないですが、よくよく考えると、リフレクションを使用して型を判別するのって結構コストがかかりますね。
Project Euler だと型ヒントの恩恵を受ける機会が多そうなので、次の問題あたりで試してみます。

---

@kohyama @ypsilon-takai
おお、clojure.contrib は 1.3 からそれぞれ独立したライブラリとしてメンテナンスされるようになっていたのですね。全く知らなかったです。
リンク先の情報、とても助かります。

Apache Commons のような既存の Java ライブラリを使ってコーディングの量を減らせるのも，Clojure の長所の一つだと考えています．Maven リポジトリと Leiningen が無ければ Clojure 使っていなかったかもしれないくらい，便利です．

Maven リポジトリ + Leininge で、既存ライブラリを手軽に使えているというのは、ぼくも強く感じています。また、Clojars を使えば、自作ライブラリを公開するのも簡単です。

*warn-on-reflection* ぼくも試してみます。