Question

I can't seem to find the solutions for problem set 9 as given out in 2011 6.00SC. So here's what I came up with, I'd appreciate if you can point out anything that could be smoothened out. tmpCompare, getBinaries, getCombos, getValue and getWork are helper functions I wrote.

https://gist.github.com/anonymous/6155431

Answer 1

here is my greedy - http://dpaste.com/1331742/

i'll look at your bruteforce later ...

right off the bat, you might want to consider making getBinaries() and getCombos() into generators:
http://docs.python.org/2.7/tutorial/classes.html#generators
http://docs.python.org/2.7/reference/simple_stmts.html#yield
http://docs.python.org/2.7/reference/expressions.html#yieldexpr

Answer 2

your bruteforce is producing correct answers.

here are a couple of combination generators i wrote for a different problem
http://dpaste.com/1333088/

here is an alternative to your getValue() and getWork() - don't know if i'd really say that it smooths anything out, just different - uses a generator expression as an argument to sum()
http://dpaste.com/1333103/

think about the time complexity of getValue() and getWork()
at lines 171 and 172, you call getValue() and getWork() for your (currently) bestCombo.
depending on the size of your initial subject list, these statements could get executed a Lot of times. calling a function is pretty expensive. each time you find a new bestCombo, just store its value and work in separate variables and refer to them in line 173

Answer 3

so thinking about getWork() and getValue() some more - it looks like you could combine those two - and halve the number of function calls and iterations over the the subjects.
maybe something like this http://dpaste.com/1333787/

here is a profile of your bruteforce() - called with a small dictionary (20 subjects) and a work constraint of 15 - http://dpaste.com/1333830/ - more than half the time is spent in getCombos()

Answer 4

Hey bwCA, thanks for your responses. I am currently trying to get my head around generators. Was it something like this what you had in mind when you suggested to make getBinaries() a generator?

https://gist.github.com/anonymous/6176661

As far as I understand, the advantage would be not having a possibly giant list of binaries in the memory.

Answer 5

' ... not having a possibly giant list of binaries in the memory.' - yep
nice generator. I'm gonna put it my bag of tricks.

lets see... i have this in my bag of tricks, that might interest you
http://dpaste.com/1335636/