Project Euler #004 – 回文数

26 11月 2009

Project EulerをClojureでおさらいシリーズ。
Problem 4

日本語訳：

回文数とは逆から数字を読んでも同じ数になる数である。2桁の数字の積からなる回文数で最大のものは 9009 (=91×99) である。

3桁の数字の積からなる回文数で最大のものを求めよ。

以前Rubyで解いたときのがこれ。

#!/usr/bin/env ruby
 
module MathLib
  module Numeric
    module Euler
      def palindromic?
        (self.to_s == self.to_s.reverse)
      end
    end
  end
end
 
class Numeric
  include MathLib::Numeric::Euler
end
 
largest = 0
100.upto(999).to_a.reverse.each do |x|
  break if x * x < largest
  100.upto(x).to_a.reverse.each do |y|
    xy = x * y
    break if xy < largest
    if xy.palindromic?
      largest = xy if xy > largest
    end
  end
end
 
p largest

回文数の判定は Numeric クラスにメソッドを追加してみた。なんかRubyっぽいでしょ？（笑）

その数値に対して「文字列にしたもの」と「文字列にしてから反転したもの」が等しいかどうかで判別している。

実行速度で軽く驚く。

0.085秒 (ruby 1.9.0) 0.146秒 (ruby 1.8.7)

思っていたよりも速い。

今度はClojureで書いてみる。

(defn palindrome? [number]
  "Return true if n is palindromic."
  (let [s (str number)]
    (= (apply str (reverse s))
       s)))
 
(defn euler-4 []
  (apply max
         (filter palindrome?
                 (for [x (range 100 1000)
                       y (range 100 x)]
                   (* x y)))))

タイムをとりやすいようにメインも関数定義した。

実行速度: 2.8秒
「なんだって〜〜〜っ」

Ruby版はすでに見つかっている回文数よりも小さければ回文判定をスルーしている。
ためしにこれを取り除いてみると、

0.210秒 (ruby 1.9.0)
0.430秒 (ruby 1.8.7)

となる。回文判定回数は、6124回 → 41219回となっていた。

Clojure版も同様に効率化してみる。

数を大きいほうから掛け合わせて、生成した積がすでに見つかっている回文数よりも小さければスキップ。

回文判定も少し改良した。

(defn palindrome? [number]
  "Return true if n is palindromic."
  (let [s (str number)]
    (= (reverse s) (seq s))))
 
(defn greater-and-palindrome?
  "Return latter number if it is parindromic and greater than former one."
  ([x] x)
  ([x y] (if (and (< x y)
                  (palindrome? y))
          y x)))
 
(defn euler-4-optimized []
  (reduce greater-and-palindrome? 1
          (for [x (reverse (range 100 1000))
                y (reverse (range 100 x))]
            (* x y))))