Problem 62 「立方数置換」
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
class P62 def initialize @keta_values = keta_values end def keta_values # ある桁数の最初の立法数を求める。ex. 3桁なら5(=125)、4桁なら10(=1000)、 (0..20).map do |keta| ((10**(keta-1))**(1/3.0)).to_i + 1 end end def main keta = 5 #5ケタ以上を探す loop do cubics = cubics( keta ) cubics.each_with_index do |cubic, idx| return cubic[0] if permutations( idx, cubics ).size == 5 end keta += 1 end "Not find" end def cubics( digit ) # ex. for return value. 36 ** 3 -> [46656, "45666"] これは [立法数、立法数の各値をソートして文字列にした] (@keta_values[digit]..10000000).inject([]) do |cubics, n| # 10000000 ** 3 is 22digits cubic = n * n * n if cubic.to_s.size > digit return cubics elsif cubic.to_s.size == digit cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort.inject{|conb,s| conb+s}] end cubics end end def permutations( idx, cubics ) drop_cubics = cubics.drop( idx ) base = drop_cubics[0] drop_cubics.select { |cubic| base[1] == cubic[1] } end end puts P62.new.main
cubics()で立法数を求め、その各桁を文字列変換しソートしたものを配列にし
て返す。permutationsでは、cubics()の結果を他の立法
数と比べ、同じものを配列に入れて返す。mainでは、同じものが5つあれば、
立法数を返す。
cubics()の
cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort.inject{|conb,s| conb+s}]
は当初以下のようなコードだった。これだと答がでるまでに15秒以上かかっていた。
cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort]
同様のことをC++で書くと100msecかからないので、Rubyといえども遅すぎる。
調べてみると処理速度改善に一番効きそうなのはpermutations()の以下のコードだ。
base[1] == cubic[1]
これの左辺値は当初 ["4","5","6","6","6"] のようなArrayだったので、"45666"のようなStringに変えたらどうかと試してみた。すると15秒だったのが4秒に短縮できた。やったー。どうもArray.==は再帰的にエレメントを比較しているのに対し(Array.cを最後まで読み切れてないけど,,,) SrtingだとCのmemcmp()に行きつく。たぶんこれが原因だろう。
これでもまだ遅いのだけど、==が左辺値のメソッドだと知っていることで、簡単に改善すべき箇所に気づける良い例だと思った。