| Three Warehouses Puzzle |
| Written by Joe Celko |
|
Talking through a problem is often a good way to see what is required for its solution. Reducing it in scale is another good strategy. But, as programmers, at the end of the day we need to code an algorithm that deals with the general case - and that means making the problem bigger. If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick,Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in Joe Celko's series of Sharpen Your Coding Skills. Here's another puzzle in the series.
"Some days, I just want to use a brute force solution," said Bugsy Cottman, a junior programmer at International Storm Door & Software, looking up from his keyboard. His boss, Melvin Frammis, stepped up behind him and said, ".. which is why quick and dirty legacy code turns into 'family curse' code. Bugsy, it is worth the extra time to look at a problem from a high level and find general rules. What are you doing, anyway?" "We have three warehouses, call them A, B and C. They have widgets in them and a funny rule about rotating inventory." Bugsy cleared off his desk and made three piles of paper clips and put a Post-it note labeled 'A', 'B' and 'C' beside each pile. "The rule is that I take three widgets from one warehouse, I keep one and put one of the three into each of the other two warehouses." Melvin looked over the piles of paper clips and re-arranged them to have (A=3, B=1, C=4) in the piles.
"Okay, if I have this configuration, I can pull three widgets from A or from C because they have three or more widgets?" asked Melvin. Bugsy nodded. "If I pick A then the warehouses become (0, 2, 5); if I pick C then the warehouses become (4, 2, 1)." Bugsy nodded again.
"Let's say I start with A, then I have to pull the next widget from C since it is the only warehouse that has three or more widgets in stock. That will give (1, 3, 2) , then (2, 0, 3), then (3, 1, 0) and the process stops at (0, 2, 1)."
Melvin was moving paper clips as he spoke, then restored the configuration. "If you started with C, then the sequence would be.." "Wow! That is the same as before!" said Bugsy, "Is that always true? Or can I stop at some combination of the same final values? Obviously, the warehouse names are arbitrary" "What are you trying to do?" asked Melvin, "I forgot to ask! That makes me feel silly! Spec without a goal!" "I want to determine the final state if I know the starting inventory levels." said Bugsy, "I figured I just write code and see what happens. I know that the process will stop when all inventory levels are less than 3. That would be my loop termination condition." "Okay, that is a good brute force solution, and you know that each cycle reduces the total inventory by one, so this will terminate in a finite number of cycles that has to be less than the sum of all three inventory levels." said Melvin. "But what do you do with huge inventory levels? Just keep looping? Then you need to have a rule for making decisions about which warehouse to pick when you have 2 or 3 choices."
Okay, Reader it is your turn!
If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in Joe Celko's series of Sharpen Your Coding Skills and they have posed us further challenges ever since: Programmer Puzzle - Hermit Boxes Jigsaw Puzzles and The MacMahon Squares Vertex Coverings And The Cool Kids Problem Merkles and Social Engineering
If you want to send in solutions to any of them either use the Comments section or email editor@i-programmer.info.
Comments
or email your comment to: comments@i-programmer.info
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin. |
