【Project EulerにRubyで挑戦シリーズ】問4:Largest palindrome product

スポンサーリンク

今回の問題

Largest palindrome product

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桁の数の積で表される回文数の最大値を求めよ。

書いた内容

とりあえず解いてみる

引数が回文数かどうかを真偽値で返すpalindrome?メソッドを定義しました。
引数はinteger型になるのでto_sメソッドでstring型に変換した後に、
reverseメソッドで文字順を逆さにすることで回文数かどうかを判定できます。

あとは3桁の数をループで回し、得られた積が回文数であれば
予め用意した空の配列に足していきます。

得られた回文数の配列の最大値を取り出して上げれば、
求める解が 906609 である事がわかります。

def palindrome?(result)
  result.to_s.reverse == result.to_s
end

start_time = Time.now
palindromic_number_array = []
(100..999).each do |n|
  (100..999).each do |i|
    result = n * i

    if palindrome?(result)
      palindromic_number_array << result
    end
  end
end
puts palindromic_number_array.max
puts "処理速度 #{Time.now - start_time}s"
#=> 906609
#=> 処理速度 0.295427s

これ同じ計算してない?

each内部がブロック引数 i を 100 から始めてしまうと

  • n = 200, i = 100
  • n = 100, i = 200

のような無駄な処理が含まれています。
ということで、重複する計算を排除できるように i の範囲は n からとしました。
また、回文数かどうかのif文は短く簡潔だったので後置としました。

下の通り、処理速度が速くなりました!

def palindrome?(result)
  result.to_s.reverse == result.to_s
end

start_time = Time.now
palindromic_number_array = []
(100..999).each do |n|
  (n..999).each do |i|
    result = n * i
    palindromic_number_array << result if palindrome?(result)
  end
end
puts palindromic_number_array.max
puts "処理速度 #{Time.now - start_time}s"
#=> 906609
#=> 処理速度 0.150435s

もう少し頑張ってみる

解が 906609 になるのはわかったのですが、どの2数の積だったのかは分からないまま。
しかも、導きたいのは回文数の最大値なので、乗算のループは999から始めたほうが良さそう。

(999..100)のように範囲を逆転させた書き方は動作しないので、downtoメソッドを使いました。
また最大値となる回文数の算出結果が残り続けるように、answerというハッシュを定義して結果を入れました。

def palindrome?(result)
  result.to_s.reverse == result.to_s
end

start_time = Time.now
answer = { palindromic_number: 0, n: 100, i: 100 }
999.downto(100) do |n|
  999.downto(n) do |i|
    result = n * i
    if palindrome?(result) && answer[:palindromic_number] < result
      answer[:palindromic_number], answer[:n], answer[:i] = result, n, i
    end
  end
end
puts answer
puts "処理概要 #{Time.now - start_time}s"
#=> {:palindromic_number=>906609, :n=>913, :i=>993}
#=> 処理速度 0.149496s

913 * 993 = 906609 が解であることが分かりました!
ハッシュとシンボルを使ったので処理もほんの少し早いのかな?
今回は以上です。

※Project Eulerのリポジトリ

          
    

スポンサーリンク

  
Scroll Up