For 1 the trick is in the first recursive call. When we subtract the current treasure from the target, we want to find solutions that include the current treasure. However inside that call, we don't know about the existence of that current treasure on the inner call - that fact is implicit in the fact that the target is smaller, and it will only get added back to the solution after the inner call returns.
For 2 the answer is, "Whenever we have a problem that we don't know how to solve, which can be somehow reduced to simpler versions of the same problem." For Fibonacci, that means smaller $n. In the case of the directory walk, that means farther down the directory tree. In the case of the partition problem, simpler means "fewer treasures".
Re^3: Mark Jason Dominus And Me - The Partition Problem
Replies are listed 'Best First'.
|Re^4: Mark Jason Dominus And Me - The Partition Problem|
by Tommy (Chaplain) on Nov 19, 2012 at 22:25 UTC
Ummm. Just doesn't make sense to me to try and hit a moving $target... pun intended. It makes a helluva lot more sense now that my target stays constant and my "share" is the only thing really changing (see code below).
Thank you tilly for helping me understand why I didn't understand. That's when everything started making sense.
This is how I would do it... (remove "print" statements after debugging done).
Click "Download code" link to see the actual, pretty, wide-formatted text
by Tommy (Chaplain) on Nov 19, 2012 at 23:27 UTC
Maybe it doesn't hurt to program the way your brain really thinks...at least not this time. You see, I stripped down the MJD code to its barest form, exactly from the book. Then I removed the print statements from my own version which was just shared in the node previous to this node.
Surprise: despite the fact that I'm passing around a reference to my "$share" with each call, my code benches twice as fast. I'm betting it's because I'm not constantly recalculating the "$target".
Anyway, here's the benchmarks. I wonder what conclusions could be drawn. If I cared more, I'd run it through Devel::NYTprof and find out what's really going on and why it's faster to do it the way that makes the most sense to my dyslexic brain: