Project Euler Problem 4

problem-4-1.clj

;;;A palindromic number reads the same both ways.
;;;The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
;;;Find the largest palindrome made from the product of two 3-digit numbers.

;;;左右どちらから読んでも同じ値になる数を回文数という。 2桁の数の積で表される回文数のうち、
;;;最大のものは 9009 = 91 × 99 である。
;;;では、3桁の数の積で表される回文数のうち最大のものはいくらになるか。

(ns projecteuler.problem-4
  (:require [clojure.string :as str])
  (:use clojure.test))

(defn palindromic?
  "回文判定をする。"
  [s] (= s (str/reverse s)))

(defn nseq
  "n桁の数値シーケンスを作る。"
  [n]
  (let [seq-min (int (Math/pow 10 (dec n)))
        seq-max (* seq-min 10)]
    (range seq-min seq-max)))

(defn problem-4
  "n桁×n桁の結果が回文数となる値を求める。"
  ([] (problem-4 3))
  ([n] (let [dig-seq (nseq n)]
         (->> (for [x dig-seq y dig-seq] (* x y))
              (filter (comp palindromic? str))
              (apply max)))))

(time (problem-4))
;=> ???
;=> "Elapsed time: 255.488 msecs"

(time (problem-4 4))
;=> "Elapsed time: 24204.772 msecs"
;=> 99000099

;;; 回文判定のテスト
(are [x y] (= y (palindromic? x))
     "abc" false
     "aba" true
     "aaba" false
     "aabaa" true
     "a" true
     "" true)

;;; nseqのテスト
(is (= (nseq 1) (range 1 10)))
(is (= (nseq 2) (range 10 100)))
(is (= (nseq 3) (range 100 1000)))

考え方とか感想とか

• 回文判定は、文字列を reverse したものと等しいかどうかで判断しています。
• 関数型プログラミング入門 っぽく書きたかったので、とりあえず効率は無視して何でもかんでもシーケンスと関数で扱うように書いてみました。
• n桁の数値のシーケンスを作って、それを二重ループで直積を作ってその積のシーケンスを作り max をとる、といった、愚直なやり方です。
• 問題は 3桁の数の積で最大 、ですが、4桁でもう苦しくなってます。アルゴリズム入門編としては問題ありなので要改善、です(という燃料を今投下しましたw 自分でも考えてみますが...)。
• 問題ありとはいうものの、Clojure は range, comp, filter, apply, ... 等々便利な道具がいっぱい揃っているので、プログラミング自体は楽しいですね(初めて ruby を知ったときのような感触)。

👍 解法としては, 素直な流れだと思います.

二点ほど.

x と y の順序は関係ないので, (seq-min と seq-max は let 済みとして)

(for [x (range seq-min seq-max) y (range x seq-max) ...] ... )

のようにすると, 同じ二数の積の計算を省けます.

for には :let 節や :when 節があり

(->>
  (for [x dig-seq y dig-seq] (* x y))
  (filter (comp palindromic? str)))

の部分を for だけで

(for [x dig-seq y dig-seq :let [prod (* x y)] :when (palindromic? (str prod))] prod)

のように書けます.

kohyama さん

• ご指摘ありがとうございました。１点目、自分がやりたかったのはまさにこれでした(for で出来ちゃうとは思ってもみなかったので...)。
• for の :when はfilterの代わりに時折使ったりしますが、:let は使ったことがなかったです。参考になります。
• で、丸パクリしたのが以下のソースになります。

(defn problem-4-2
  "n桁×n桁の結果が回文数となる値を求める。"
  ([] (problem-4-2 3))
  ([n] (let [seq-min (int (Math/pow 10 (dec n)))
             seq-max (* seq-min 10)]
         (->> (for [x (range seq-min seq-max) y (range x seq-max)
                    :let [prod (* x y)]
                    :when (palindromic? (str prod))] prod)
              (apply max)))))

(time (problem-4-2))
;=> ???
;=> "Elapsed time: 196.862 msecs"

(time (problem-4-2 4))
;=> "Elapsed time: 10923.413 msecs"
;=> 99000099

感謝、感謝!!!

総当たりな力技で問題を解くの大好きです．Clojure だと力技でも簡単にかつ美しく書けるのでいいです．この問題だと palindromic? が速いので総当たりしても 1 秒切るんですよね．解答を実行してみて予想以上に速かったので驚きました．やはり Clojure は速い．

問題は 3桁の数の積で最大 、ですが、4桁でもう苦しくなってます。アルゴリズム入門編としては問題ありなので要改善、です(という燃料を今投下しましたw 自分でも考えてみますが...)。

解き方の考え方は同じでアルゴリズム的な進歩は何も無いのですが，

• 91 × 99 と 99 × 91 は同じだから 91 × 99 のときだけ考える (探索空間 1/2) ... @kohyama 提案済み
• 最大の数は 9 で始まるだろうから 9** × 9** 場合だけ考える (探索空間 1/10 × 1/10 = 1/100)

という手抜きで，1/(1/2 × 1/100) = 200 倍高速化してみました．

(defn- solver*
  [n]
  (let [u (apply * (repeat n 10))
        l (long (* 9/10 u))]
    (apply max (for [a (range l u)
                     b (range a u)
                     :let [m (* a b)]
                     :when (parindromic? m)]
                 m))))

https://gist.github.com/4304116#file-problem-4-clj

tnoda.projecteuler.problem-4> (time (solver* 3))
"Elapsed time: 1.409 msecs"

tnoda.projecteuler.problem-4> (time (solver* 4))
"Elapsed time: 161.117 msecs"

4 桁でも 1 秒以内で解けました．Clojure 速い（2 回目）．

しかし，この解き方だと一桁増えるごとに実行時間が 100 倍になっていきます． 5 桁で 20 秒弱，6 桁で 30 分強．桁が増えていくと苦しくなっていくので，誰かうまい方法を実装してください．

_tnoda さん

• コメントありがとうございます。 「最大の数は 9 で始まるだろうから」 こういう効率化、自分でも漠然と考えていたのですが、自分の中でうまく理由付けができず却下して力技にしてしまいました。Project Euler って、こういうことを真面目に考える場でもあると、個人的には思っています(データ構造とかアルゴリズムとか大事)。

この解き方だと一桁増えるごとに実行時間が 100 倍になっていきます． 5 桁で 20 秒弱，6 桁で 30 分強．桁が増えていくと苦しくなっていくので，誰かうまい方法を実装してください．

2数の積を大きい順に生成するアルゴリズムができればOKですよね。
探索するしかないような気がするので、それ方面で考えてみようかな。

16:55
思いつきを式にしてみました。
検証してません。 ごめんなさい。 帰ってから時間があれば、検証と説明を書きます。

https://gist.github.com/4316509

私は(apply str (reverse s)) したのですが、clojure.string/reverseで直接できるのですね。関数もっと探すようにしてみます。

@plaster

私は(apply str (reverse s)) したのですが、clojure.string/reverseで直接できるのですね。関数もっと探すようにしてみます。

私も最初に思いつくのはは (apply str (reverse s)) です．さらに，clojure.string/reverse は require するのが面倒なのと，require しない場合は clojure.string/reverse のほうが長くなるので，(apply str (reverse s)) のまま放置することが多いです．複数人が参加するプロジェクトでは気をつけようと思います．

---

ところで，6 桁の parindromic numbers を大きい順に並べた lazy seq は，

(defn- mirror
  [x]
  (Long/parseLong (str x (str/reverse (str x)))))

のような関数 mirror を使うと，

(map mirror (range 999 99 -1))

のように書けるので，あとは，ある数が 3 桁数の積になっているかどうかを判定する述語関数 f があれば，

(first (filter f (map mirror (range 999 99 -1))))

で速く答えを出せそうな気がするのですが，その先の f で挫折しています．

で速く答えを出せそうな気がするのですが，その先の f で挫折しています

僕も最初に解いた時にやってみたのですが、999、998...で割っていく方法しか思いつかなくて、時間がかかりすぎてあきらめました。

いい方法あるんでしょうか？

Clojure は range, comp, filter, apply, ... 等々便利な道具がいっぱい揃っているので、プログラミング自体は楽しいですね(初めて ruby を知ったときのような感触)。

clojure.core の関数やマクロって、ちょうど良いくらいに世話を焼いてくれるなーと思います。
単独ではそれほど複雑な処理ができないけれど、各自を組み合わせることで力を発揮するようなものが多い。
「ここはあの関数でああして……」というように試行錯誤そのものが楽しいです。

clojure.core の関数やマクロって、ちょうど良いくらいに世話を焼いてくれるなーと思います。

「ちょうど良い」って，私も同じように感じています．

ぼくは @ponkore と同様のアルゴリズムで作って、高速化しようと @tnoda の f で挫折しました。たぶん、この問題での典型なのだと思います。

clojure.core はパズルのようだと感じています。 4Clojure を通じて、何度 clojure.core に驚かされることか。