Project euler 4

pe_4_other.clj

;;ざっと思い付いたものを実装してみました。
;; 合っているかどうかも未検証 (12/17)

;;(12/17 21:00)
;; やっぱり考慮がまったく足りていなかったので、基本は変えずに全面みなおし。

(defn palindromic?  [s]
  (= (seq s) (reverse s)))


(defn diagonal-line [ulimit llimit]
  (mapcat #(list [% %]
                 [% (dec %)]) (range ulimit  llimit -1)))

(defn shicho [[l r] ulimit llimit]
  (map vector (range l (inc ulimit)) (range r (dec llimit) -1)))

(defn find-bigger [max-data new-pair ulimit llimit]
  (loop [pair-list (shicho new-pair ulimit llimit)]
    (let [new-num (reduce * (first pair-list))]
      (cond (empty? pair-list)
            ,,max-data
            (< new-num (first max-data))
            ,,max-data
            (parindromic? new-num)
            ,,[new-num (first pair-list)]
            :t
            ,,(recur (next pair-list))))))

(defn pe4 [n]
  (let [ulimit (dec (reduce * (repeat n 10)))
        llimit (reduce * (repeat (dec n) 10))]
    (loop [[max pair :as max-data] [0 [0 0]]
           diagonal-list (diagonal-line ulimit llimit)]
      (if(> max (reduce * (first diagonal-list)))
        max-data
        (let [new-max (find-bigger max-data
                                   (first diagonal-list)
                                   ulimit
                                   llimit)]
          (recur new-max (next diagonal-list)))))))

方針

大きい方から順に調べていく方式。 途中で計算を打ち切ることで速度を上げてます。
文字だけだと上手く説明できないので、考えるときに使ったエクセルのキャプチャ画像を用意しました。
ここには貼れないみたいなので、ブログに貼ります。

エクセルでざっと表を作って眺めてみると、表の対角線右下から左上にのDagonalの方向に、数値が減少しています。また、Diagonalのあるマスから左下へのShicho方向にも数値が減少しています。ということで、Diagonalを左上に進みながら、Shicho方向を探索していきます。ただ、Shicho方向をそれぞれ見ていくと、ある段の列は途中から、次の段より小さくなってしまいます。

結局こんな感じで処理を作りました。

• 処理はその時点での最大の候補を持っている。
• Shicho方向探索中に、新たな候補をみつけたら、そのShicho列はそこで終り。
  
  左下方向には、それより大きな値は無いから。でも、 以降のShichoにはより大きなものがある可能性があるので、Diagonalの次の列に移る。
• あるDiagonal上のマスの数が、候補より小さければ、候補が解
  
  Diagonal上のあるマスの左上と左下方向には、それより大きな値は無いから。

4桁以上の場合の結果と時間

user> (time (pe4 4))
"Elapsed time: 11.082221 msecs"
[99000099 [9999 9901]]

user> (time (pe4 5))
"Elapsed time: 93.824928 msecs"
[9966006699 [99979 99681]]

user> (time (pe4 6))
"Elapsed time: 846.100545 msecs"
[999000000999 [999999 999001]]

あっているかどうか検証してない。

元が一桁増える毎に実行時間が 100 倍だったので，これ（一桁増える毎に 10 倍）はかなり速くなっていますね．

👍
私も, 最初に, 同じ探索順序を検討したのですが, 降順にならないことが分かった時点であきらめてしまっていました.
方法ももちろん参考になりますが, 思いつきを最後まで形にする実行力. 見習いたいです.

桁が増えるとかなり効いてきますから, 元の問題の範囲での費用対効果にとらわれず, こういった演習をしておくと実用開発の時に役立ちますよね.