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)))

この解き方だと一桁増えるごとに実行時間が 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 に驚かされることか。