From: Raffa <raffaboss@...>
Date: 2008-01-30T23:34:57+09:00
Subject: Re: Making Change (#154)

- 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
"<integer part>,<rest>. 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 2*1 + 1*4 == 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 2*5c (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 6*15c.
 This is a top-level cell, then we can end this path. This solution
is, then: 2*5c + 6*15. (and in effect 2*5+6*15) =100. So:
 4)- 2*5c + 6*15 -------------------- total of 8 coins

  Similarly we proceed with the "1,0" cell on (6,4):  1*4 + ..........
    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 16*6 + 1*4... =100 bingo! This is a
solution
5) 16*6+1*4 ----------------------------- total of 17 coins

and following the other path?   Not being a toplevel cell we compute
the partial (1*6)
   curr tot partial: 1*4 + 1*6
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 (6*15) and we have the solution

6) 1*4c + 1*6c + 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)
1*3 + ...
lookup the "1,3" at matrix(1,3) [not topleve, y axys amount:10]
1*7 +
lookup for 10, found at matrix (0,1)
6*15
[top level! stop computation]

7)-   1*3c + 1*7c + 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__