From: ThoML <micathom@...>
Date: 2008-05-07T02:55:03+09:00
Subject: Re: Reverse Divisible Numbers (#161)

Ok, I had some free time. The enclosed solution still finds less
numbers than marcelo's elegant solution but it is slightly faster.

For 100_000_000_000_000_000_000_000

marcelo: 572 numbers, 1m28s
my enclosed solution: 550 numbers, 0m1.583s

Unless you want to find 550 reverse divisible numbers really fast
there is no real reason to use the enclosed version due to the
imperfect rules set. Anyway, here it is:


def rdn(limit = 1_000_000)
    rules = [
        lambda {|t, th, a, b|
            t.sub(/^(#{th}#{a}9*)#{b}/, "\\19#{b}")
        },
        lambda {|t, th, a, b|
            t.sub(/^(#{th}0*)/, '\\10')
        },
        lambda {|t, th, a, b|
            t.gsub(/#{b}(0*)#{a}/, "#{b}\\10#{a}")
        },
        lambda {|t, th, a, b|
            t.sub(/^(#{th})(#{th})$/, "\\1#{a}#{b}\\1")
        },
        lambda {|t, th, a, b|
            z  = th[/0+$/]
            th = th[0, th.size - z.size] if z
            t.sub(/^(#{th}#{z})(#{z}#{th})$/, "\\1#{a}#{b}#{a}#{b}\
\2")
        },
        lambda {|t, th, a, b|
            th ? ["#{a}#{b}0", th, th, "0#{a}#{b}"].join : t
        },
        lambda {|t, th, a, b|
            th ? ["#{a}#{b}", th, th, "#{a}#{b}"].join : t
        },
        lambda {|t, th, a, b| [t, t].join},
    ]

    half = {
        '1089' => lambda {|t| t[0, t.size / 2][/^(109*890*)*/]},
        '2178' => lambda {|t| t[0, t.size / 2][/^(219*780*)*/]},
    }

    digits = limit.to_s.size

    out = {1089 => 9801, 2178 => 8712}

    axioms = [
        ['1089'],
        ['2178']
    ]

    axioms.each do |nums|
        nums0    = nums[0]
        nums0pre, nums0post = nums0.scan(/../)
        makehalf = half[nums0]
        cache = Hash.new do |h, n|
            nh = makehalf.call(n)
            rules.each do |rule|
                n1  = rule.call(n, nh, nums0pre, nums0post)
                n1i = n1.to_i
                if n1 != n and !out.has_key?(n1i) and n1.size < digits
                    m1i = n1.reverse.to_i
                    if m1i < limit
                        nums << n1
                        if m1i % n1i == 0
                            out[n1i] = m1i
                            val = true
                        end
                    end
                end
            end
            h[n] = false
        end
        begin
            found = false
            nums.each {|n| found ||= cache[n]}
        end while found
    end
    return out
end


if __FILE__ == $0
    limit  = (ARGV[0] || 1_000_000).to_i
    nums = rdn(limit).sort_by {|a, b| b}
    nums.each do |n1i, m1i|
        puts "#{m1i} = #{n1i} * #{m1i / n1i}"
    end
    puts "Found #{nums.size} numbers"
end