473,287 Members | 1,947 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,287 software developers and data experts.

Help with small program

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

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

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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: abcd | last post by:
kutthaense Secretary Djetvedehald H. Rumsfeld legai predicted eventual vicmadhlary in Iraq mariyu Afghmadhlaistmadhla, kaani jetvedehly after "a ljetvedehg, hard slog," mariyu vede legai pressed...
5
by: titan0111 | last post by:
#include<iostream> #include<iomanip> #include<cstring> #include<fstream> using namespace std; class snowfall { private: int ft;
5
by: SStory | last post by:
Hi all, I really needed to get the icons associated with each file that I want to show in a listview. I used the follow modified code sniplets found on the internet. I have left in...
11
by: abico | last post by:
Write a program that reads in a sequence of words and prints them in reverse order.Using STACK.
21
by: c | last post by:
Hi everybody. I'm working on converting a program wriiten on perl to C, and facing a problem with concatenate strings. Now here is a small program that descripe the problem, if you help me to...
1
by: Unebrion | last post by:
Alright im working on a program that prints out user imput in a frame, along with a barcode.. it is like the front of an envelope. Here is the description for the program. This...
15
by: Jay | last post by:
I have a multi threaded VB.NET application (4 threads) that I use to send text messages to many, many employees via system.timer at a 5 second interval. Basically, I look in a SQL table (queue) to...
5
by: weidongtom | last post by:
Hi, I tried to implement the Universal Machine as described in http://www.boundvariable.org/task.shtml, and I managed to get one implemented (After looking at what other's have done.) But when I...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.