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 is the latest puzzle.
"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.."
Melvin began moving paper clips again,
" (3, 1, 4) then (4, 2, 1), (1, 3, 2), (2, 0, 3), (3, 1, 0), ending at (0, 2, 1). "
"Wow! That is the same as before!"
"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."
"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!
What are the termination states?
- How can you get to them? Express it as a formula.
- Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.
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: