「孤独の7」を Ruby で
rscの日記さんのところで、「孤独の7」という虫喰い算を知りました。問題は右の画像のとおりです。ここで回答を募集していたようです。
Ruby で解きました。かかった時間はほぼ 0.1秒です(答えの uniqueness のチェックなし。チェックすると 0.7秒程度)。Ruby を使ってだから、まあまあなのではないでしょうか。
lonely7.rb
def main_loop 112.upto(143) {|i| @n = i; yield} end def num_loop(r) 1.upto(9) do |i| yield(@n * i) if check(@n * i, r) end end def check(a, r) #aはr桁か 10 ** (r - 1) <= a and a < 10 ** r end 1000.upto(9999) do |x1| main_loop do num_loop(4) do |i1| next unless check(a1 = x1 - i1, 2) 0.upto(9) {|x2| next unless check(a2 = a1 * 10 + x2 - @n * 7, 3) num_loop(3) do |i2| 0.upto(9) {|x3| next unless check(a3 = a2 * 10 + x3 - i2, 2) 0.upto(9) {|x4| next unless a3 * 10 + x4 < @n 0.upto(9) {|x5| num_loop(4) do |i3| if a3 * 100 + x4 * 10 + x5 == i3 num = x1 * 10000 + x2 * 1000 + x3 * 100 + x4 * 10 + x5 puts "#{num} / #{@n} = #{num / @n}" exit end end } } } end } end end end #=>"12128316 / 124 = 97809"
単純な総当りではないです。特に 112.upto(143)
と割る数を絞っているのは、7を掛けて 3桁になるというのと、1桁の数を掛けて 4桁になり得ることを使っています。また、桁数が指定できるところはすべて桁数のチェックをしています。メソッド num_loop(r)
は Ruby お得意のブロックを使って、(桁数チェックの入った)カスタムの制御構造を作り出しています。
ちなみにマシン・スペックは Core i5-4210U 1.70GHz×2。
追記
rsc さんの Python のコードを Ruby に移植してみました。上手いですねえ。僕のコードよりずっといいですね(見てもらえばわかりますが、僕と発想が真逆です)。実行時間はほぼ 0.7秒です。
require 'kaki/utils/nest_loop' def digit(n) n.zero? ? 0 : n.to_s.length end def get_num(x, n) (x / n) % 10 end [10, 10, 10].nest_loop do |a, b, c| next if a.zero? (100...200).each do |dvs| quo = 10000 * a + 7000 + 100 * b + c dvd = quo * dvs next unless digit(dvs * a) == 4 next unless digit(dvs * 7) == 3 next unless digit(dvs * b) == 3 next unless digit(dvs * c) == 4 tmp = [0, 0, 0, 0, 0] k = [2, 3, 2, 3, 0] rem = dvd / 100000 catch(:exit) do 5.times do |i| tmp[i] = rem * 10 + get_num(dvd, 10 ** (4 - i)) rem = tmp[i] % dvs throw(:exit) unless digit(rem) == k[i] end puts "#{dvd} / #{dvs} = #{quo}" end end end
なお、手製のライブラリのメソッド(nest_loop)を使っています(参照)。