Halp! (Python)

Hi guys.
So here's the story, I'm trying to solve this problem with a python script. (I feel like I'm advertising, I've already posted links to Euler three times now)

So here's my brute-force, inefficient script:

Spoiler for Brute Force:

Code:

---

i = 1  #counter

for g in range(0,2): #100p
    for f in range(0,4): #50p
        for e in range(0,10): #20p
            for d in range(0,20): #10p
                for c in range(0,40): #5p
                    for b in range(0,100): #2p
                        for a in range(0,200): #1p
                            total = a + 2*b + 5*c + 10*d + 20*e +50*f + 100*g
                            if total==200: #We need 200p after all!
                                i = i+1
                                print 'Found'

print 'Total:'
print i

---

I've ran in once, and it wasn't the right answer, but the script should be right. I've checked with printing all the stuff, and that checks out.

So after a night's sleep I decided to optimize:

Spoiler for So-called optimized:

Code:

---

i = 1  #counter

for g in range(0,2):
    m=4-2*g
    for f in range(0,m):
        n=10-5*g-2*f
        for e in range(0,n):
            o=20-10*g-5*f-2*e
            for d in range(0,o):
                p=40-20*g-10*f-4*e-2*d
                for c in range(0,p):
                    q=100-50*g-25*f-10*e-5*d-2*c
                    for b in range(0,q):
                        r=200-100*g-50*f-20*e-10*d-5*c-2*b
                        for a in range(0,r):
                            total = a + 2*b + 5*c + 10*d + 20*e +50*f + 100*g
                            if total==200:
                                i = i+1
                                print 'Found'

print 'Total:'
print i

---

I hope you can see what I did there. If I've already got one coin of 100p, my maximum for getting 200p while adding 50p coins is 2, or 4-2*g, thus making the making the maximum value for f smaller.

Thing is, this just returns "Total: 1". What's wrong with my code?

P.S: Everything is, actually indented properly. Python editor does it automatically after a colon.
Finally, I'm NOT asking you to give me the answer, that would ruin the fun.

EDIT: I've ran the brute force, just with m instead of four. It wasn't the right answer. Trying again without m. (That means it'll make about a bazillion loops). 2*4*10*20*40*100*200=1.28e9 to be exact. Dang.

*edited*
added code tags to preserve indentation (bloody python....)
Ynot

Please wrap the code in [code] tags to preserve the indentation.

edited OP

Quote:

---

Originally Posted by Ynot

edited OP

---

Thanks. So, does anybody have any help?

I'm still stuck with it >.<

One thing: the range() function is (in mathy words) inclusive-exclusive [a,b)... in Pythony words, range(0, x) returns [0, 1, 2, ..., x-2, x-1]. So you'll want to change eg. "for a in range(0,200)" -> "for a in range(0, 200+1)" to get those cases where any one coin makes up the whole thing.

This actually might explain the problem with your second code... if a is the number if 1p coins that need to be added to get to £2, and you use range(0, a), then it will only go up to a-1 and never actually reach the value a, and so never obtain £2. Similarly of course for the outer loops. So you need to add one to each of those ranges as well.

That probably answers your question.

Just because I have to put my own ideas in :P, you can actually eliminate the final inner loop in the second version completely. If r >= 0 then clearly you can add exactly r 1p coins to make £2, so that's one combination done :).

Another trick is using xrange() instead of range() which is exactly the same but returns a generator instead of a list, probably speeding things up a bit since you don't have to allocate lots and lots of lists.

Quote:

---

Originally Posted by RedfishBluefish

One thing: the range() function is (in mathy words) inclusive-exclusive [a,b)... in Pythony words, range(0, x) returns [0, 1, 2, ..., x-2, x-1]. So you'll want to change eg. "for a in range(0,200)" -> "for a in range(0, 200+1)" to get those cases where any one coin makes up the whole thing.

This actually might explain the problem with your second code... if a is the number if 1p coins that need to be added to get to £2, and you use range(0, a), then it will only go up to a-1 and never actually reach the value a, and so never obtain £2. Similarly of course for the outer loops. So you need to add one to each of those ranges as well.

That probably answers your question.

Just because I have to put my own ideas in :P, you can actually eliminate the final inner loop in the second version completely. If r >= 0 then clearly you can add exactly r 1p coins to make £2, so that's one combination done :).

Another trick is using xrange() instead of range() which is exactly the same but returns a generator instead of a list, probably speeding things up a bit since you don't have to allocate lots and lots of lists.

---

Thanks ;)
I figured the r thingey today, too.
Thanks for your advice!