From: tho_mica_l <micathom@...>
Date: 2008-01-30T03:49:57+09:00
Subject: Re: Making Change (#154)

> It happens to be with the euro
> coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
> and euro has additionally 2-1 cent coins), so there is probably a less
> stringent sufficient condition.

#1
My code does backtracking if it runs into a dead end. I'm not sure if
this qualifies as greedy -- but you're the wizard and I may be wrong.
The problem with primes input (see vsv's test cases) is that in this
case, it does an exhaustive search then and recurse more often than
those 8000 times or so that are good for ruby.

#2
So I made some real-world-like tests based on Euro Money * 100. The
solutions had to give change for a random amount N times.

C Porth's solution turned out to be lightning fast on these standard
cases. tml3 is tml2 with the the safety bolts removed. Since Euro
coins
include 1cent coins there always is a good solution and backtracking
can
be minimized. Behold!

N=1000
                  user     system      total        real
dominik      13.679000   0.000000  13.679000 ( 13.980000)
eric        205.015000   0.951000 205.966000 (210.522000)
paolo       191.516000   3.074000 194.590000 (198.816000)
paolo_eric  158.618000   3.275000 161.893000 (165.488000)
porth         0.811000   0.000000   0.811000 (  0.811000)
tml1          0.951000   0.000000   0.951000 (  0.971000)
tml2          5.258000   0.000000   5.258000 (  5.388000)
tml3          0.651000   0.000000   0.651000 (  0.651000)
vsv           4.907000   0.000000   4.907000 (  5.008000)
yoan         10.114000   0.000000  10.114000 ( 10.345000)

So Eric was probably right. There were some space issues involved. :-)

Here is the code for doing the benchmark (in case you'd like to do
this
yourself at home and maybe create your own coin sets):


    #!/usr/bin/env ruby

    require 'benchmark'

    solutions = [
        'tml1', 'tml2', 'tml3',
        'porth',
        'vsv',
        'yoan',
        'paolo', 'paolo_eric',
        'eric',
        'dominik',
    ]

    # N = 100
    # X = 3000

    N = 1000
    X = 30000

    # N = 10000
    # X = 100000

    # In Euro Cents.
    COINS = [50000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20,
10, 5, 2, 1]

    puts "Building cache"
    cache = {}
    load 'solution_tml3.rb'
    X.times do |a|
        if a % 1000 == 0
            STDOUT.print '.'
            STDOUT.flush
        end
        cache[a] = make_change(a, COINS)
    end
    puts

    Benchmark.bm(12) do |x|
        solutions.each do |f|
            load "solution_#{f}.rb"
            x.report(f) do
                N.times do |i|
                    money  = rand(X)
                    change = make_change(money, COINS)
                    if cache[money] != change
                        STDOUT.puts "CONFLICT #{money}:
#{change.inspect} <=> #{cache[money].inspect}"
                        STDOUT.flush
                    end
                end
            end
        end
    end


BTW, I'm sure Grandma' would love 18 cent coins.

Regards,
Thomas.