読者です 読者をやめる 読者になる 読者になる

「孤独の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桁か
  a < 10 ** r and a >= 10 ** (r - 1)
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 'utils'

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)を使っています(参照)。