From: Yoan Blanc <greut.lists@...>
Date: 2008-01-27T21:44:15+09:00
Subject: Re: Making Change (#154)

vsv wrote:
> 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 } ) )
>   
I managed to get a solution (which is nil) even for this:

make_change( 2**100-1, (1..100).map{ |n| 2**n } )

in a reasonable time.

-- Yoan