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?

Dec 24 '06 #1

Felix Benner

smartbei schrieb:

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.

Dec 24 '06 #2

smartbei

Felix Benner wrote:

smartbei schrieb:

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.

Dec 24 '06 #3

Paul Watson

smartbei wrote:

Felix Benner wrote:

>smartbei schrieb:

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

Dec 25 '06 #4

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)

Dec 25 '06 #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...

Dec 28 '06 #6

Tim Roberts

go****@yahoo.com wrote:

>
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.
--
Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.

Dec 30 '06 #7

Paul Watson

Tim Roberts wrote:

go****@yahoo.com wrote:

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

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}

Jan 1 '07 #8

Tom Plunket

Paul Watson wrote:

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!

--

Jan 1 '07 #9

gokkog

"Paul Watson дµÀ£º
"

Tim Roberts wrote:

go****@yahoo.com wrote:

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.

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=St...als&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[i]):
min[i] = 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

Jan 1 '07 #10