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.maincubics()で立法数を求め、その各桁を文字列変換しソートしたものを配列にし
て返す。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()に行きつく。たぶんこれが原因だろう。
これでもまだ遅いのだけど、==が左辺値のメソッドだと知っていることで、簡単に改善すべき箇所に気づける良い例だと思った。
