Making Change (#154)

Ruby
101

My Solution:

class Array

102

  • can process inputs like “make_change 1_000_000_000_000 4 3 7 6 85 98
    54 22 3423 34 509 435 243 345” in < 0.2 sec. (in super no-
    optimization / ultra-verbose mode)

  • no use of recursion & stack

  • no use of incremental/decremental operations

  • it is not necessary to sort the input array of coins (when the input
    array tends to infinite this is important)

  • possibility to add coins after the processing don’t affect the
    previous memoizing array at all (ony incremental change). Optimal for
    store/retrieve table.

  • it is simple do it manual (pencil / notebook), cause all to do is to
    take note of some x/y integer part and rest .

  • (this code only generates the table as discussed in “manual
    algorithm”, useful only to perceive the relative speed/scalability of
    the solution. Don’t look at it! Full of boring shit)

manual algorithm:

take pencil / notebook

step 1:
trace a x/y axis, report the amount y, coins on x, eg make_change 6,
[4, 3, 1] becomes:

6|
|
|
|

 
4   3   1

step 2:
in every matrix(x,y) cell report the integer part and the rest of the
division between the corrispondent amount/coin, in the format
",. If there is a rest, push it in the y axis,
too:

6| 1,2|2,0|6,0

2 
4   |3  | 1

‘2’ is, obviously, the rest between 6 and 4

step 3:
proceed as step 2, until there are no rests to process. Where the
integer part of the division is 0, don’t consider it, puts a “-” char
(nil):

6|1,2|2,0|6,0
2| - | - |2,0

4   | 3 |   1

ok, finished. This is the result table. This has to be read in this
way:

  • The number of possible solutions are the number of cells that ands
    with “,0” : 2,0 at matrix(0,1); 6,0 at matrix(0,2); 2,0 at matrix
    (1,2)

  • If the cell containinng “,0” is a level 1 cell [ matrix(0,x)] this
    is also THE possible solution, and the formula is <integer_part> *
    <coin_value> (3 *2; 6 * 1). <integer_part> represents also, obviously,
    the number of coin, number_of_coins that will be used to compute the
    obtimal solution

  • if the “,0” is not a level 1 cell, this is only a part of the
    solution, exactly the last “node”, SURELY the last node of a solution.
    In this case the rest in the y coordinate of the cell (‘2’ in the
    example, below 6, the rest of 6 and 4 ) has to be considered as an
    index ‘linked’ to a ‘cell’ with the identical rest.
    In the matrix(0,0) there is the cell “1,2”. [Geralizing, when we have
    a “n,0” cell.value case, we have to now what amount we are processing,
    then use it to find a “?,n” cell]. We have to do this operation n
    times, until we ‘parse’ a cell with base ndex 0 [matrix(0,n)] (or we
    can sum the amounts till total==input amount).

  • at every intermediate step (previous point), we have to compute
    "integer_part * relative coin, so for the example: when we found the
    “2,0” cell (matrix (x,y) where x>0) we compute
    amount 2 of coin 1 +
    (find a cell with rest 2 (2 as the number of the vertical
    axys) -> “1,2” of matrix(0,0)
    … + amount 1 of coin 4

      the last "cell" is a top one then we can stop this

computation. (or: the total 21 + 14 == 6[input value]).

    we can set to 'nil' the cell so processed.

proceeding in this way all the possible ‘goal’ permutation are:

  • 6 * 1
  • 2 * 1 + 1 * 4
  • 2*3
    (tree as tree are the 0-rest ‘cells’)
    the optimal solution is, obviously, the one with minor total amounts
    (the third one)

that’s all.

more complex example

make_change 100, [20,15,9,7,5,6,4,3]

step 1: trace x/y axis, put 100 on the y, coins on the y. divide 100
for every coin and fill the cells consequently, in the format
integer_part,rest. Push every rest on the y axys

 |

100| 5,0|6,10|11,1|14,2|20,0|16,4|25,0|33,1
10 | |
1 | |
2 | |
4 | |

1 
 20|  15  |9 |   7 |   5  |  6  |  4  | 3

step 2: proceed in the same way of step 1: divide each rest on the y
with the coin on the x and eventually push rests (if presents).
Proceed until the table is full, not more elements on the y to
process. Note: ultra-verbose / no-optimization

100| 5,0|6,10|11,1|14,2|20,0|16,4|25,0|33,1
10 | - | - |1,1 | 1,3| 2,0 | 1,4 | 2,2|3,1
1 | - |----------------------------------
2 | |-----------------------------------
4 | |------------------------- |1,0|1,1
1 | -----------------------------------------
1----------------------------------------------
3-------------------------------------|1,0
4---------------------------------1,0 | 1,1
2-------------------------------------------
1-------------------------------------------
1--------------------------------------------
1----------------------------------------------
--------|----|----|----|----|----|----|—
20|15 | 9 | 7 | 5 | 6 | 4 | 3

Ok done, by hand, in a few secs, simply not?
Now, let’s query this table

Q- how many solutions has this problem?
R- 7, as 7 are the cells “,O”

Q- let’s go, candidate! list me these 8 kids
R-
then… there are 3 single-step solutions (4 top-level ",0"s cells):
1)- 5 * 20c ---------------------------- total of 5 coins
2)- 20 * 5c----------------------------- total of 20 coins
3)- 25 * 4c--------------------------- total of 25 coins
(till now the best solution is the first)

then we have a “2,0” at matrix (1,4) so we compute 25c (5 is the
coin on x axys). This is not a top-level cell then we see at the
vertical axys value (10) and we use it to find a cell with “,10”
value. Here it is at matrix(0,1) “6,10”, that becomes 615c.
This is a top-level cell, then we can end this path. This solution
is, then: 25c + 615. (and in effect 25+615) =100. So:
4)- 25c + 615 -------------------- total of 8 coins

Similarly we proceed with the “1,0” cell on (6,4): 14 + …
the y axys value for it is 4 the we have to find a cell “,4”, ok
proceed
ops!! we have two cells with “,4”!!! the “1,4” at matrix(1,5) and
the “16,4” at (0,5). Which one we can take? mumbe mumble. let’s try
with the toplevel cell (toplevel=stop computation). Then the result,
adding the previous computation is 166 + 14… =100 bingo! This is a
solution
5) 166+1*4 ----------------------------- total of 17 coins

and following the other path? Not being a toplevel cell we compute
the partial (16)
curr tot partial: 14 + 16
and we watch at the y axys of “1,4”, “10”, and we use this number to
find a cell “,10”, ok “6,10” at matrix(0,1) [toplevel] then we add
this partial (615) and we have the solution

  1. 14c + 16c + 6*15c--------------------- total of 8 coins
    then we proceed

Q- But here we have a complication, it’s not linear, you have said: no
stack, and that we can nil-lize the cells considered, here…
R- The solution is absolutely linear, it’s true that there can be more
occurrences (",y") cells for a y given but let’s see the entire y axys
amounts (where we push the rests). You see that the “4” case compares
2 times, and both with cells “1,0”, then is true: every computed cell
can be set to null, every solution is on the board and stop.

let’s proceed in speedy-mode with the last solution. we’ve just popped
the 1,0 at matrix(8,6) then remains the one at matrix(7,7), (y axys
amount:3)
13 + …
lookup the “1,3” at matrix(1,3) [not topleve, y axys amount:10]
17 +
lookup for 10, found at matrix (0,1)
6*15
[top level! stop computation]

7)- 13c + 17c + 6*15c ----------------------- total of 8 coins
__END

the best solution is the number 1: 5*20

Consideration & optimization

  • This solution can be terribly improved, at least for memory
    concerns. (eg if a division give me a rest x just computed and with
    all values ‘nil’ we can erase it. See the 1-rest in the example).

    • I think the obtimal solution is to use an hash for the rests for
      simple lookups, the value can be an array of occurrences. Or…

  • The code below is terrible, full of variables not used and so on.
    The purpose (for me) is to generate the table and stop. (Retrieving
    the solutions is a stupid affair, and i want to think at the best data
    structure for store the memoizing array [matrix is useful only for
    presentation], before the last step)

CODE:

Node = Struct.new(:amount, :cost, :rest,:coin)
def make_change(amount, coins = [25, 10, 5, 1])
return [ ] if amount.zero?

#coins = coins.sort_by { |coin| -coin }

#@r =Hash.new # rests (indexed)

queue=[amount]
j=0

@matrix=Array.new
@row=Array.new
@amounts=Array.new
@results=Array.new
@rests=Hash.new

loop do

amount = queue.shift
@amounts << amount
return if amount == nil

coins.each_with_index do |coin, idxCoin|

  cost=amount/coin
  #cost=nil if amount=0
  rest= amount%coin

  #puts "#{amount}-#{coin}-#{rest}"


  row="#{cost},#{rest}"
  #row="#{cost},#{coin}"
  row = nil if cost==0


  #if cost==0
   # @row << nil
  #else
  #  @row<<"#{cost},#{rest}"
  #end

  @row << row


  #aResult=
  #@results<< "#{cost}*#{coin}" if cost >0  and rest ==0

#Node.new(amount,cost,0,coin) if cost > 0 and rest ==0
#@rests[rest] ="#{cost}*#{coin}" if cost >0 and rest >0
#@r[rest] += Node.new(cost,coin)
#print “- #{rest}”

 queue << rest if cost > 0 and rest >0
 #puts "(#{cost}-#{rest})"
 # p queue.size

  end
  @matrix << @row
  @row=[]

#return if queue.size> 50

end

end

if FILE == $PROGRAM_NAME
amount, *coins = ARGV.map { |n| Integer(n) }
abort “Usage: #{$PROGRAM_NAME} AMOUNT [COIN[ COIN]…]” unless
amount

coins.empty? ? make_change(amount) : make_change(amount, coins)

@matrix.each_with_index {|x,i| puts “amount:#{@amounts[i]}” +
x.inspect}
#puts @results.inspect
#puts @rests.inspect

end

END

103

some benchmark about generating the table for the un-ottimized algorithm
posted previously. (the very last step, retrieve the best solution
requires no time)

all the test on the forum is solved in 0.x sec.

make_change( 31_000+2, (1…1_000).map{ |n| 3n } )
15 sec. ---------------- (nil)

make_change( 1_000_000_000_000_000_000_000_000_000_000_000, [43, 4321,
1234, 31423242, 2, 3432, 545, 5654, 667, 67, 4756, 4657465756, 3443243,
323123, 421455367, 76879, 8679886, 6, 2, 1, 6, 87, 5, 9, 76, 67])
40 sec. -----------------(183071 candidate solutions)

104

Jesús Gabriel y Galán wrote:

Hi Gesús, Thank for your advices!

The first problem is that your solution returns
[10,1,1,1,1] for make_change(14, [10,7,1])
when the correct answer would be [7,7].

Now,I’m trying to fix this problem.

To avoid iterating so much, check at Ilan B. solution.
For each coin value, making a division you would know
how many of this coins can fit, something like (not tested):

num = amount / coin
num.times {change << coin}
amount %= coin

Oh, obviously this code is better than mine.I’ll fix it.

Atsuhiro T.

105

2008/1/30, Raffa [email protected]:

(… interesting post …)

Raffa, I think your algorithm doesn’t always find the best solution. Try
it with

make_change(24, [10, 7, 1])

What would be the answer of your algorithm? I think it would be one of

210 + 41
37 + 33

but not

110 + 27

Regards,
Pit

106

Hi,

I joined Ruby T. couple of days before and this is my first post.
I am a newbie and tring to learn Ruby from last one month.

I have written spec for the problem (This is the first time I am playing
with RSpec) - Parked at Loopia

And this is my (naive :frowning: ) solution - Parked at Loopia

Solving this first problem was fun. :slight_smile: I learned a lot from everyone’s
post.

Cheers,
Amey