From: tho_mica_l <micathom@...>
Date: 2008-01-29T01:24:56+09:00
Subject: Re: Making Change (#154)

> Has anyone done time comparisons of the submissions?  I'm just curious
> at what the fastest strategies have been.

Well, this is somewhat subjective.

Here is an possible overview that includes only basic tests most
people
agreed on:


      user     system      total        real
solution_eric.rb  0.380000   0.000000   0.380000 (  0.380000)
solution_gray.rb  3.295000   0.000000   3.295000 (  3.304000)
solution_ludtke.rb  1.552000   0.000000   1.552000 (  1.553000)
solution_paolo.rb  0.942000   0.190000   1.132000 (  1.171000)
solution_paolo_eric.rb  0.751000   0.190000   0.941000 (  0.972000)
solution_porth.rb  0.661000   0.000000   0.661000 (  0.661000)
solution_tml1.rb  0.050000   0.000000   0.050000 (  0.050000)
solution_tml2.rb  0.200000   0.000000   0.200000 (  0.200000)
solution_yoan.rb  0.241000   0.000000   0.241000 (  0.281000)


I excluded solutions returning unexpected results, caused errors
(with
ruby19) and solutions that took considerably longer than this
selection
to solve the cases listed below.

As always with such listings, another composition of the tests would
result in a totally different table. From other test runs that also
included more exotic tests I'd say that Paolo's solution performs
much
better than it would look on the basis of this table. It is also one
of
the solutions that deal well with all sorts of crazy input.


Here are the tests I used (I used "print 'x'" to identify solutions
returning unexpected results, which explains the parentheses and the
!=...). The files are saved in solution_NAME.rb:


Benchmark.bm do |x|
    Dir['solution_*.rb'].each do |f|
        load f
        x.report(f) do
            20.times do
                (make_change(14, [10,7,3]) || []).sort != [7, 7]
                (make_change(14, [10, 7, 1]) || []).sort != [7, 7]
                (make_change(10, [10, 7, 1]) || []).sort != [10]
                (make_change(7, [10, 7, 1]) || []).sort != [7]
                (make_change(0)) != []
                (make_change(14, [10, 5, 3]) || []).sort != [3, 3, 3,
5]
                (make_change(11, [10,9,2]) || []).sort != [2, 9]
                (make_change(297, [100, 99, 1]) || []).sort !=
[99,99,99]
                (make_change(397, [100, 99, 1]) || []).sort !=
[99,99,99, 100]
                (make_change(497, [100, 99, 1]) || []).sort !=
[99,99,99, 100,100]
                (make_change(1000001, [1000000, 1]) || []).sort != [1,
1000000]
                (make_change(39, [25, 10, 5, 1]) || []).sort.reverse !
= [25, 10, 1, 1, 1, 1]
                (make_change(14, [10, 7, 1]) || []).sort.reverse !=
[7, 7]
                (make_change(0, [25, 10, 5, 1])) != []
                (make_change(1000001, [1000000, 1]) ||
[]).sort.reverse != [1000000, 1]

                (make_change(1000001, [1000000, 2, 1]) ||
[]).sort.reverse != [1000000, 1]
                (make_change(24, [10, 8, 2])) != [8, 8, 8]

                (make_change(11, [10, 9, 2]) || []).sort.reverse !=
[9, 2]
                (make_change(19, [5, 2, 1]) || []).sort.reverse != [5,
5, 5, 2, 2]
                (make_change(39, [5, 2, 1]) || []).sort.reverse != [5,
5, 5, 5, 5, 5, 5, 2, 2]
                money = [1000,500,200,100,50,20,10,5,2,1]
                (make_change(1789, money) || []).sort.reverse !=
[1000,500,200,50,20,10,5,2,2]
                money = [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47,
43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3]
                (make_change(101, money) || []).sort.reverse != [89,
7, 5]
                # print 'x' if (make_change(4563, money) ||
[]).sort.reverse != [97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97,
97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97,
97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97,
89, 7, 5]
            end
        end
    end
end