Halp! (Python)

**ThreeLetterSyndrom** · 06-21-2009 09:33 AM

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:

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:

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

**dsr** · 06-21-2009 05:06 PM

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

**Ynot** · 06-21-2009 06:42 PM

edited OP

**ThreeLetterSyndrom** · 06-21-2009 06:59 PM

Originally Posted by Ynot

edited OP

Thanks. So, does anybody have any help?

I'm still stuck with it >.<

**RedfishBluefish** · 06-23-2009 01:20 PM

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

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

**ThreeLetterSyndrom** · 06-23-2009 09:43 PM

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

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

Thread: Halp! (Python)

LinkBack

Thread Tools

Display

Halp! (Python)

Bookmarks

Bookmarks

Posting Permissions