443,400 Members | 903 Online Need help? Post your question and get tips & solutions from a community of 443,400 IT Pros & Developers. It's quick & easy.

# Help with small program

 P: n/a 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
9 Replies

 P: n/a 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['key'] -= 1 a instead use: anslist.append(dict(hist.items)) which will copy the dict. Dec 24 '06 #2

 P: n/a 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['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

 P: n/a smartbei wrote: Felix Benner wrote: >smartbei schrieb: >>Hello, I am a newbie with python, though I am having a lot of fun usingit. Here is one of the excersizes I am trying to complete:the program is supposed to find the coin combination so that with 10coins you can reach a certain amoung, taken as a parameter. Here is thecurrent 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 anslistThe 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 howmany 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 thisresult is replaced by the incorrect final one? hist is stored in anslist as a pointer only, therfore the hist[c] -= 1operates on the same dict as is stored in the anslist. Try the followingin the python interpreter:a = { 'key' : 1 }l = [a]l['key'] -= 1ainstead 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

 P: n/a 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

 P: n/a "Paul Watson Ð´µÀ£º 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

 P: n/a go****@yahoo.com wrote: >Interesting impl in Python! I am wondering what if the requirement isto 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

 P: n/a Tim Roberts wrote: go****@yahoo.com wrote: >Interesting impl in Python! I am wondering what if the requirement isto 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

 P: n/a 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

 P: n/a "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 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

### This discussion thread is closed

Replies have been disabled for this discussion. 