[QUIZ] Making Change (#154)

T

tho_mica_l

Here is an possible overview that includes only basic tests most
I excluded vsv's solution because it caused an error. I now realized
that this was because me loading mathn.

solution_vsv.rb 0.180000 0.000000 0.180000 ( 0.180000)

regards,
Thomas.
 
E

Eric I.

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)

Those times are awfully small, and I wonder if they're masking some
useful differences and magnifying some less meaningful differences.

For example, I have a test that I've been using, which combines
Phrogz's, vsv's, and some of my own. When running with Ruby 1.8.6, I
get:

Paolo: 27.919662 s
Eric: 25.756986 s
tho_mica_l_1: 20.899582 s (note: modified for Ruby 1.8.6)
Paolo (w/ Eric mod): 19.207968 s

And that gives a different sense than tho_mica_l's solution being 19
times faster than Paolo's.

So I suspect depending on whether you're using 1.8.6 vs. 1.9, and
whether or not you use test cases that require larger search spaces,
you're likely to get different results.

Eric

P.S. To convert the tho_mica_l_1 solution for Ruby 1.8.6, I had to add
the odd? and even? methods to Integer and convert 'changer' into a
method.
 
A

Adam Shelly

This week's Ruby Quiz is to complete a change making function with this
skeleton:

def make_change(amount, coins = [25, 10, 5, 1])

Your function should always return the optimal change with optimal being the
least amount of coins involved. You can assume you have an infinite number of
coins to work with.


Here's my somewhat simplisitc solution. I just work upwards through
progressively larger sets of coins until I find one that works. I
think the only interesting part is that you can select what to do when
there is no exact match.
-Adam

#select what to do when can't make exact change
STRATEGY=[:RoundDown,:RoundUp,:Refuse][1]

class Array
def sum
inject(0){|s,v|s+v}
end
end

def minimum_change coins,strategy
case STRATEGY
when :RoundDown
0
when :RoundUp
coins[0]
when :Refuse
nil
end
end

#make amount of change with the fewest possible coins
#
# iterate through progressively larger sets of coins
# until you find a set that adds up to amount,
def make_change(amount, coins = [25, 10, 5, 1])
change = Array.new(amount+1)
coins=coins.sort
#handle cases where change is less than smallest coin
return [minimum_change(coins,STRATEGY)] if amount < coins[0]
#initial sets are one coin
sets = coins.map{|c|[c]}
loop do
sets.each{|set|
return set.reverse if set.sum==amount
# record the first set to match each sum (incase we can't make
exact change)
change[set.sum]||=set
}
#generate more sets by adding 1 of each coin to existing sets
#only keep unique sums smaller than target amount.
sets = sets.inject([]){|result,set|
newsets=coins.map{|c|(set+[c]).sort}.find_all{|s|s.sum<=amount }
result+newsets
}.uniq
#if we can't make exact change, reduce amount until we can
if sets.empty?
amount -=1 until change[amount]
#use STRATEGY to round up or down
minchange=minimum_change(coins,STRATEGY)
return (change[amount].reverse<<minchange)-[0] if minchange
return minchange
end
end
end
 
T

tho_mica_l

Those times are awfully small

I also ran it with more iterations but the ranking remains about the
same.
For example, I have a test that I've been using, which combines
Phrogz's, vsv's, and some of my own.

I also have an extended set of test cases that builds on whatever was
posted to the list. For this comparison I only selected test cases
for
which a sufficient number of solutions returned results in finite
time
(I'm doing this on a 4-yrs old notebook, so time is limited :).
And that gives a different sense

This is also about what I get when I run phrogz's test cases. But
these
test cases don't seem representative somehow. phrogz's cases are
rather
suited to test the program's correctness not so much to measure its
general performance I'd say. (BTW I would never claim that my
solution
is in general 19 times faster than anyone of other solution in all
possible situations. I know my code well enough to know how to make
it
run in circles for quite some time.)

In a "natural" setting, I think something like this

default_change = [25, 10, 5, 1]
30.times do |a|
make_change(a ** 2, default_change)
end

is more likely to be a problem the program has to solve. So, my
reasoning is that a good solution should solve these standard cases
fast
and should not go wild on "strange" input, which my first solution
does
with certain input. (But most other solutions do too.)

I also think all solutions in this listing perform pretty well on
these
general cases. This would become obvious if one included a brute
solution that always does a full search.

I think Paolo's solution is cool because it's really compact, because
it
avoids recursion and because it doesn't need to include optimizations
for special cases. My solution on the other hand needs special case
handling in order to avoid deep recursion, which ruby19 doesn't like
too
much as it seems. But then, with "normal" input the number of
recursions
should be limited since coin values are usually selected in a way to
make it easy for people to give change. This probably is the reason
for
why there aren't any 17cent coins around -- which would be fun
though.
So maybe a depth-first search is the more appropriate approach for
this
problem after all. Or maybe not?

Anyway, I said this listing is rather subjective, didn't I.

Regards,
Thomas.
 
P

Paolo Bonzini

should be limited since coin values are usually selected in a way to
make it easy for people to give change.

Of course. If every coin is a multiple of the immediately smaller
coin, the greedy algorithm is ok. It happens to be with the euro
coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
and euro has additionally 2-1 cent coins), so there is probably a less
stringent sufficient condition.
why there aren't any 17cent coins around -- which would be fun though.

There was a puzzle on DDJ asking for the optimal set of coins (i.e.
the one giving the smallest number of coins on average). I don't have
it at hand but the results were weird, I recall.
 
J

James Gray

There was a puzzle on DDJ asking for the optimal set of coins (i.e.
the one giving the smallest number of coins on average). I don't have
it at hand but the results were weird, I recall.

The book this quiz is based on explores that topic. It recommended we
adopt an 18 cent coin, among other variations.

James Edward Gray II
 
J

Jesús Gabriel y Galán

This week's Ruby Quiz is to complete a change making function with this
skeleton:

def make_change(amount, coins =3D [25, 10, 5, 1])

end

Your function should always return the optimal change with optimal bein= g the
least amount of coins involved. You can assume you have an infinite nu= mber of
coins to work with.
I am having problems with the 100001, [100000, 1] situation when I
think I shouldn't so there might be a bug in there. Didn't have time
to check it yet. I'll try to find the problem if I have time.

I've had 5 minutes and I solved this issue. I wanted shift/push
but I was using pop/push so was trying the combinations
of lower coins before the big ones, leading to more tests
than necessary. Now this case finds a solution with the 100000
coin and quickly prunes the rest. Still having problems with the
2**n stuff but I'm pretty sure I won't have time to look at it anymore...

Anyway, fun quiz as usual, thanks for this.

Jesus.


class Solution
attr_reader :remaining_amount, :coins, :usable_coins

def initialize(amount, usable_coins, coins=3D[])
@remaining_amount =3D amount
@usable_coins =3D usable_coins.sort.reverse.select {|x| x <=3D amount}
@coins =3D coins
end

def explode
# check if this is an invalid branch or already a solution
return [] if @usable_coins.empty?
return [] if @usable_coins.last > @remaining_amount
return [] if @remaining_amount =3D=3D 0
# generate two possible scenarios: use a coin of the highest value
and generate a Solution with less remaining amount
# but the same set of usable_coins or remove the highest value and
generate a Solution with the same remaining amount
# but less usable_coins
first =3D Solution.new(@remaining_amount - @usable_coins.first,
@usable_coins, (@coins.dup) << @usable_coins.first)
second =3D Solution.new(@remaining_amount, @usable_coins[1..-1], @coins=
)
[first, second]
end

def is_solution?
@remaining_amount =3D=3D 0
end

def number_of_coins
@coins.length
end

def to_s
"[#{@coins.inspect}, #{@remaining_amount}, #{@usable_coins.inspect}]"
end
end

def make_change(amount, coins =3D [25, 10, 5, 1])
queue =3D []
solution_so_far =3D nil
length_so_far =3D nil
queue << Solution.new(amount, coins)
until queue.empty?
current =3D queue.shift
# prune branches that would result in a worse solution
next if solution_so_far && current.number_of_coins >=3D length_so_far
if current.is_solution?
solution_so_far =3D current
length_so_far =3D current.number_of_coins
else
queue.push(*current.explode)
end
end
return [] if solution_so_far.nil?
solution_so_far.coins
end
 
T

tho_mica_l

It happens to be with the euro
coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
and euro has additionally 2-1 cent coins), so there is probably a less
stringent sufficient condition.

#1
My code does backtracking if it runs into a dead end. I'm not sure if
this qualifies as greedy -- but you're the wizard and I may be wrong.
The problem with primes input (see vsv's test cases) is that in this
case, it does an exhaustive search then and recurse more often than
those 8000 times or so that are good for ruby.

#2
So I made some real-world-like tests based on Euro Money * 100. The
solutions had to give change for a random amount N times.

C Porth's solution turned out to be lightning fast on these standard
cases. tml3 is tml2 with the the safety bolts removed. Since Euro
coins
include 1cent coins there always is a good solution and backtracking
can
be minimized. Behold!

N=1000
user system total real
dominik 13.679000 0.000000 13.679000 ( 13.980000)
eric 205.015000 0.951000 205.966000 (210.522000)
paolo 191.516000 3.074000 194.590000 (198.816000)
paolo_eric 158.618000 3.275000 161.893000 (165.488000)
porth 0.811000 0.000000 0.811000 ( 0.811000)
tml1 0.951000 0.000000 0.951000 ( 0.971000)
tml2 5.258000 0.000000 5.258000 ( 5.388000)
tml3 0.651000 0.000000 0.651000 ( 0.651000)
vsv 4.907000 0.000000 4.907000 ( 5.008000)
yoan 10.114000 0.000000 10.114000 ( 10.345000)

So Eric was probably right. There were some space issues involved. :)

Here is the code for doing the benchmark (in case you'd like to do
this
yourself at home and maybe create your own coin sets):


#!/usr/bin/env ruby

require 'benchmark'

solutions = [
'tml1', 'tml2', 'tml3',
'porth',
'vsv',
'yoan',
'paolo', 'paolo_eric',
'eric',
'dominik',
]

# N = 100
# X = 3000

N = 1000
X = 30000

# N = 10000
# X = 100000

# In Euro Cents.
COINS = [50000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20,
10, 5, 2, 1]

puts "Building cache"
cache = {}
load 'solution_tml3.rb'
X.times do |a|
if a % 1000 == 0
STDOUT.print '.'
STDOUT.flush
end
cache[a] = make_change(a, COINS)
end
puts

Benchmark.bm(12) do |x|
solutions.each do |f|
load "solution_#{f}.rb"
x.report(f) do
N.times do |i|
money = rand(X)
change = make_change(money, COINS)
if cache[money] != change
STDOUT.puts "CONFLICT #{money}:
#{change.inspect} <=> #{cache[money].inspect}"
STDOUT.flush
end
end
end
end
end


BTW, I'm sure Grandma' would love 18 cent coins.

Regards,
Thomas.
 
A

Atsuhiro Teshima

Hi, I'm Atsuhiro.
this is the first time I contribute to Ruby-forum.

I find one solution for Ruby-Quiz154.

the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I'll glad if you
point out some problem in my solution.)


class Making_change
$change = []
def make_change(amount,coins=[25,10,5,1])
@coing = coins
if amount < 0
print "amount should be a positive integer \n"
exit
end

coins.each do |i|
if amount >= i
$change << i
amount = amount-i
redo
elsif amount == 0
return $change
else next
end
end
end
end

a = Making_change.new
p a.make_change(52) # => [25,25,1,1]
p a.make_change(-30) # => amount should be a positive integer
 
J

James Gray

Hi, I'm Atsuhiro.
this is the first time I contribute to Ruby-forum.

I find one solution for Ruby-Quiz154.
Welcome!

the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I'll glad if you
point out some problem in my solution.)

Wow. I promise I wasn't solving problems this hard when I was so
new. Great work!

Youe code does have a small problem with variable scoping. To see it,
change the last few lines to:

a = Making_change.new
p a.make_change(52)
p a.make_change(52)

and run it.

We all run into this when we are new and quickly learn that global
variables are almost never what we want. In this case, your global
$change variable is the problem.

I'll stop talking there and see if that's a big enough hint to help
you fix it. If not, just let us know and I'll give more hints.

Again, I'm impressed!

James Edward Gray II
 
J

Jesús Gabriel y Galán

Hi, I'm Atsuhiro.
this is the first time I contribute to Ruby-forum.

Hi, welcome to the Ruby community...
the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I'll glad if you
point out some problem in my solution.)

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].

Next, some comments on the code
class Making_change
$change = []

you don't need a global variable here.
If you wanted to store the latest change
given by an instance of this class (but for the
problem at hand you don't even need that), you could
use a instance variable of the class:

@change
def make_change(amount,coins=[25,10,5,1])
@coing = coins

here you are storing the coins in an instance variable,
but it's not needed since every invocation of the make_change
method carries the coins array, so it's not some state you
would need to store anyway, so I'd just remove this altogether.
As you should remove the $change also, change should be
a local variable to this method so:

change = []
if amount < 0
print "amount should be a positive integer \n"
exit
end

coins.each do |i|
if amount >= i
$change << i
amount = amount-i
redo
elsif amount == 0
return $change
else next
end
end
end
end

To avoid iterating so much, check at Ilan Berci 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
a = Making_change.new
p a.make_change(52) # => [25,25,1,1]
p a.make_change(-30) # => amount should be a positive integer

Anyway, this algorithm has the problem of the two middles:

p a.make_change(14, [10,7,1]) # => [10,1,1,1,1], should be [7,7]

Hope this helps,

Jesus.
 
A

Atsuhiro Teshima

Wow. I promise I wasn't solving problems this hard when I was so
new. Great work!

Hi, I'm really glad to get such a message from you,the author of
Ruby-Quiz!!Thank you so much!

a = Making_change.new
p a.make_change(52)
p a.make_change(52)

I tried this code and found my problem, I also find out why I shouldn't
use global $change variable.Thank for your advice.I'll try not to make
this kind of mistakes again.

I'll try the next Ruby-Quiz, though many of quizes are really difficult
for me^^

AtsuhiroTeshima
 
A

Alex Shulgin

This week's Ruby Quiz is to complete a change making function with this
skeleton:

def make_change(amount, coins = [25, 10, 5, 1])

end

Hi,

I've had some connectivity issues, so here is my a bit too late
solution to this:

#!/usr/bin/env ruby

def make_change(amount, coins = [25, 10, 5, 1])
coins = coins.sort.reverse

# p amount
# p coins

best_change = Array.new(amount + 1)
0.upto(amount) do |n|
best_change[n] = coins.map do |c|
n - c < 0 \
? [] \
: (best_change[n - c].empty? && n != c \
? [] \
: [c] + best_change[n - c])
end.delete_if{ |a| a.empty? } \
.sort{ |a, b| a.size <=> b.size }[0] || []
end

# p best_change

best_change[amount]
end

if __FILE__ == $0

require 'test/unit'

class TestMakeChange < Test::Unit::TestCase
def setup
@_1071_coins = [10, 7, 1]
@ua_coins = [50, 25, 10, 5, 2, 1]
@au_coins = [200, 100, 50, 20, 10, 5]
end

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

def test_change_equal_to_one_coin
assert_equal([10], make_change(10, @_1071_coins))
assert_equal([7], make_change(7, @_1071_coins))
end

def test_two_middles
assert_equal([7, 7], make_change(14, @_1071_coins))
end

def test_us
assert_equal([25, 10, 1, 1, 1, 1], make_change(39))
assert_equal([25, 25, 25, 25], make_change(100))
assert_equal([25, 25, 25, 10, 10, 1, 1, 1, 1], make_change(99))
end

def test_ua
assert_equal([2, 2], make_change(4, @ua_coins))
assert_equal([25, 10, 2], make_change(37, @ua_coins))
assert_equal([50, 25, 10, 10, 2, 2], make_change(99, @ua_coins))
end

def test_24_1082
assert_equal([8, 8, 8], make_change(24, [10,8,2]))
end

def test_au
assert_equal([], make_change(1, @au_coins))
assert_equal([20, 10, 5], make_change(35, @au_coins))
end

def test_15_1053
assert_equal([5, 3, 3, 3], make_change(14, [10, 5, 3]))
end

def test_x97
assert_equal([99, 99, 99], make_change(297, [100, 99, 1]))
assert_equal([100, 99, 99, 99], make_change(397, [100, 99, 1]))
assert_equal([100, 100, 99, 99, 99], make_change(497, [100, 99,
1]))
end

def test_4563
assert_equal([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],
make_change(4563, [97, 89, 83, 79, 73, 71, 67, 61,
59, 53, 47, 43, 41, 37, 31, 29,
23, 19, 17, 13, 11, 7, 5, 3]))
end

def test_huge
# assert_equal([], make_change(1_000_001))
end
end

end

Yep, I know it's ugly, but I hadn't much time to eliminate that
`best_change[0]' corner case...

Great Quiz anyway! :)
 
R

Raffa

i found a solution that 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 recursion & stack
- possibility to add coins after the processing don't affect the
previous memoizing array at all
- it is simple do it manual (pencil / notebook), cause all to do is to
take note of some x/y integer part and rest

i haven't seen all solutions posted, so i don't know if this algorithm
is just been presented, if no, then i'll post in next minutes

(sorry for my bad english)
 
B

Bernardo Monteiro Rufino

[Note: parts of this message were removed to make it a legal post.]

My Solution:

class Array
def sum
inject(0){|sum, n| sum + n;};
end

end

class ChangeError < StandardError; end

def make_change(amount, coins=[25, 10, 5, 1])
change = coins.sort.reverse.inject([]) do |change, coin|
change << coin until change.sum + coin > amount;
change;
end
raise ChangeError unless change.sum == amount;
change.sum;
end
 
R

Raffa

- 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}*" +
x.inspect}
#puts @results.inspect
#puts @rests.inspect



end


__END__
 
R

Raffaele Tesi

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( 3**1_000+2, (1..1_000).map{ |n| 3**n } )
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)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top