From: vsv <gm.vlkv@...>
Date: 2008-01-27T19:34:56+09:00
Subject: Re: Making Change (#154)

On Jan 26, 6:45 pm, James Gray <ja...@grayproductions.net> wrote:
> On Jan 26, 2008, at 1:40 PM, Alex Shulgin wrote:
>
> > BTW, is it reasonable to assume amount <= 100 or do we need to prepare
> > for this one:
>
> > def test_huge
> >  assert_equal([...], make_change(1_000_001)
> > end
>
> > ?
>
> I leave that to your best judgement.  We should probably remember that
> not all places in the world have a 100 cent dollar though.
>
> James Edward Gray II

my best 'judgement' so far can be formalized in the following code:
###
require 'test/unit'
class TestMakeChange < Test::Unit::TestCase

    def test_no_solution
        assert_equal( nil, make_change( -1 ) )
        assert_equal( nil, make_change( 1, [] ) )
        assert_equal( nil, make_change( 1.5, [2, 1] ) )
        assert_equal( nil, make_change( 1, [2] ) )
        assert_equal( nil, make_change( 7, [5, 3] ) )
        # 1023 instead of 127 is too slow :(
        assert_equal( nil, make_change( 127, (1..10).map{ |n|
2**n } ) )
    end

    def test_no_change
        assert_equal( [], make_change(0) )
    end

    def test_one_coin
        a = [*(1..100)]
        for i in a
            assert_equal( [i], make_change(i, a) )
        end
    end

    def test_ones
        a = [*(1..100)]
        for i in a
            assert_equal( [1]*i, make_change( i, [1]+a[i..-1] ) )
        end
    end

    def test_two_middles
        for i in 1..100
            b = i*10
            m = b/2+1
            assert_equal( [m, m], make_change( m*2, [b, m, 1]) )
        end
    end

    def test_first_and_last
        for i in 1..10
            b = i*100
            assert_equal( [b, 1], make_change( b+1, (1..b).to_a) )
        end
    end

    def test_binary
        a = (0..7).map{ |n| 2**n }.reverse!
        for i in 0..255
            bits = a.inject([i]){ |r,x| r[0]<x ? r :
                                       [r[0]-x, *(r[1..-1]<<x)]
                                  }[1..-1]
            assert_equal( bits, make_change( i, a ) )
        end
    end

    def test_primes
        a = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97]
        a.reverse!
        for i in 1..a.size
            v = a[0,i].inject(){|r,n|r+n}
            r = make_change( v, a )
            assert( r.size <= i )
        end
        for i in 1..a.size/2
            assert_equal( 2, make_change( a[i]+a[-i], a ).size )
        end
        # by tho_mica_l
        assert_equal( [97]*46 + [89, 7, 5], make_change( 4563, a ) )
    end

    def test_misc
        assert_equal( [25, 10, 1, 1, 1, 1], make_change( 39 ) )
        assert_equal( [9, 2], make_change( 11, [10, 9, 2] ) )
        assert_equal( [5, 2, 2, 2], make_change( 11, [10, 5, 2] ) )
        assert_equal( [8]*3, make_change( 24, [10, 8, 5, 1] ) )
        assert_equal( [9]*3, make_change( 27, [10, 9, 5, 1] ) )
        #
        for i in 1..8
            assert_equal( [9]*i, make_change( 9*i, [10,9,1] ) )
            assert_equal( [10]+[9]*i, make_change( 10+9*i,
[10,9,1] ) )
        end
    end
end
#####
BRs
Sergey