Help with small program

[smartbei]

Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:

coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s < fin and l < 10:
for c in coins:
if (s+c) <= fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)

bar(50)
print anslist

The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?

 

[Felix Benner]

Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:

coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s < fin and l < 10:
for c in coins:
if (s+c) <= fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)

bar(50)
print anslist

The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?

hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:

a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a

instead use:

anslist.append(dict(hist.items))

which will copy the dict.

 

[smartbei]

Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:

coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s < fin and l < 10:
for c in coins:
if (s+c) <= fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)

bar(50)
print anslist

The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?

hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:

a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a

instead use:

anslist.append(dict(hist.items))

which will copy the dict.

Thanks!
BTW - its hist.items(), after that it worked.

 

[Paul Watson]

Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:

coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s < fin and l < 10:
for c in coins:
if (s+c) <= fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)

bar(50)
print anslist

The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?

hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:

a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a

instead use:

anslist.append(dict(hist.items))

which will copy the dict.

Thanks!
BTW - its hist.items(), after that it worked.

An alternative.

cointypes = (100, 10, 5, 1, 0.5)
needed = {}

def coins(fin):
cur = fin
for c in cointypes:
v = int(cur / c)
if v > 0:
needed[c] = v
cur -= v * c

if __name__ == '__main__':
coins(51)
print needed
coins(127)
print needed

 

[Paul Watson]

Better alternative.

cointype = (100, 10, 5, 1, 0.5)

def coins(fin):
needed = {}
for c in cointypes:
v, r = divmod(fin, c)
if v > 0:
needed[c] = v
fin = r
return needed

if __name__ == '__main__':
print coins(51)
print coins(127)
print coins[12.5)

 

[gokkog]

"Paul Watson дµÀ£º
<snip>

Interesting impl in Python! I am wondering what if the requirement is
to find the minimum number of coins which added to the "fin" sum...

 

[Tim Roberts]

Interesting impl in Python! I am wondering what if the requirement is
to find the minimum number of coins which added to the "fin" sum...

Given the set of coins in the original problem (100, 10, 5, 1, 0.5), the
solution it provides will always be optimal. Even if we change this to
American coinage (50, 25, 10, 5, 1), I believe it is still optimal.

It is certainly possible to construct a set of denominations for which the
algorithm occasionally chooses badly. For example, if you give it the set
(40,35,10) and ask it to make change for 70, it will be suboptimal.

 

[Paul Watson]

Given the set of coins in the original problem (100, 10, 5, 1, 0.5), the
solution it provides will always be optimal. Even if we change this to
American coinage (50, 25, 10, 5, 1), I believe it is still optimal.

It is certainly possible to construct a set of denominations for which the
algorithm occasionally chooses badly. For example, if you give it the set
(40,35,10) and ask it to make change for 70, it will be suboptimal.

Tim,

Unless I am missing the point, the minimum number of coins from the set
available will be chosen. Surely this homework is past due by now.

$ cat coins.py
#!/usr/bin/env python
import sys

cointypes = (100, 10, 5, 1, 0.5)

def coins(fin, cointypes):
needed = {}
for c in cointypes:
v, r = divmod(fin, c)
if v > 0:
needed[c] = int(v)
fin = r
return needed

def doit(fin, cointypes = cointypes):
h = coins(fin, cointypes)
print '%.1f requires %d coins in hash ' % (fin, sum(h.values())), h

if __name__ == '__main__':
doit(51)
doit(127)
doit(12.5)
doit(70, (40,35,10))

sys.exit(0)

$ ./coins.py
51.0 requires 6 coins in hash {1: 1, 10: 5}
127.0 requires 6 coins in hash {1: 2, 10: 2, 100: 1, 5: 1}
12.5 requires 4 coins in hash {0.5: 1, 1: 2, 10: 1}
70.0 requires 4 coins in hash {40: 1, 10: 3}

 

[Tom Plunket]

It is certainly possible to construct a set of denominations for which the
algorithm occasionally chooses badly. For example, if you give it the set
(40,35,10) and ask it to make change for 70, it will be suboptimal.

Unless I am missing the point, the minimum number of coins from the set
available will be chosen. Surely this homework is past due by now.

[...]

doit(70, (40,35,10))
70.0 requires 4 coins in hash {40: 1, 10: 3}

The point was that "minimum number of coins" in this case is actually
two, but the provided algorithm yields four.

-tom!

--

 

[gokkog]

"Paul Watson дµÀ£º
"

Given the set of coins in the original problem (100, 10, 5, 1, 0.5), the
solution it provides will always be optimal. Even if we change this to
American coinage (50, 25, 10, 5, 1), I believe it is still optimal.

It is certainly possible to construct a set of denominations for which the
algorithm occasionally chooses badly. For example, if you give it the set
(40,35,10) and ask it to make change for 70, it will be suboptimal.

Tim,

Unless I am missing the point, the minimum number of coins from the set
available will be chosen. Surely this homework is past due by now.

$ cat coins.py
#!/usr/bin/env python
import sys

cointypes = (100, 10, 5, 1, 0.5)

def coins(fin, cointypes):
needed = {}
for c in cointypes:
v, r = divmod(fin, c)
if v > 0:
needed[c] = int(v)
fin = r
return needed

def doit(fin, cointypes = cointypes):
h = coins(fin, cointypes)
print '%.1f requires %d coins in hash ' % (fin, sum(h.values())), h

if __name__ == '__main__':
doit(51)
doit(127)
doit(12.5)
doit(70, (40,35,10))

sys.exit(0)

$ ./coins.py
51.0 requires 6 coins in hash {1: 1, 10: 5}
127.0 requires 6 coins in hash {1: 2, 10: 2, 100: 1, 5: 1}
12.5 requires 4 coins in hash {0.5: 1, 1: 2, 10: 1}
70.0 requires 4 coins in hash {40: 1, 10: 3}

To be explicit, the min coins question could be resolved with "dynamic
programming". So it is not a pure python question. No, this is not a
homework question. Well, it is somewhat academic:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

I wrote the following Python implementation akin to topcoder algorithm:

#!/usr/bin/env python
default_cointypes = (1, 3, 5)

def mincoins(fin, cointypes = default_cointypes):
needed = {}
for c in cointypes:
needed[c] = 0
min = {}
for item in range(1, fin+1):
min[item] = 2007 # suppose 2007 is the "infinity"
min[0] = 0

for i in range(1, fin+1):
for c in cointypes:
if (c <= i and min[i-c] + 1 < min):
min = min[i-c] + 1
needed[c] += 1

print fin, "==>", min[fin]
print needed

if __name__ == '__main__':
mincoins(11)

Probably there are things to be improved and there could be the
pythonic way(s): Welcome your comments and ideas!


Happy new year!
Wenjie