Put on your thinking cap for another challenge that requires computational thinking. This time Melvin Frammis and his junior partner Bugsy Cottman need to respond to an emergency.
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.
This puzzle is their twelfth appearance.
Melvin Frammis burst through the front doors of International Storm Door & Software, still in his pajamas, and ran nonstop to the basement. When he got there, Bugsy Cottman his junior programmer was a bit busy getting a disaster team organized.
“Bugsy, tell me what has happened!” said Melvin.
“Remember that backup server we keep in what used to be an old civil defense bomb shelter?” replied Bugsy. “Well, the shelter sprung a leak and we have to go in and do emergency repairs. I’ve got the teams we need and the equipment, but there some problems.”
“Yes, there always are.” said Melvin, in an exasperated tone, “What are we playing up against?”
“The tunnel that leads to the room can only hold two people. Since the lights are out, one of those people is going to have to be carrying a large flashlight for the second person. I did a quick estimation, and figured out that Johnny can get down the tunnel in about one minute. But thanks to what they have to carry, it’s going to take Paul about two minutes, George, about five minutes and Ronnie, who’s gonna have to do the heavy stuff, will be lugging equipment for at least 10 minutes. I figure the best the way to do this is to send ‘Johnny Quick’ as the tour guide for everyone since he can get back up and down the tunnel faster than anyone else. Give him the flashlight and let him run back and forth.”
Melvin grabbed a piece of scratch paper and made some quick notes. “Okay the teams can only move as fast as the slowest guy. And it’s gonna take Johnny a minute to get back to get the next team set up” said Melvin out loud. “this gives us 2 minutes + 1 minute return + 5 minutes + 1 minute return + 10 minute for the final trip and Johnny stays there. So that’s 19 minutes to get our disaster recovery team in place.”
Bugsy then turned to his coworkers and started to get the first teams together. But then Melvin said, “That’s not optimal! We can do better.”
Your problem is to find the better way.
When you first hear it, Bugsy's approach seems to be the obvious way to solve the problem. As it works out, it’s actually better to team up the slower workers.
a) Team up Johnny and Paul. This first team takes two minutes to go down (thanks to Paul) and one minute for Johnny to come back.
b) Make a team of George and Ronnie, which will take 10 minutes to go down the tunnel, thanks to Ronnie. Give the flashlight to Paul, who will take two minutes to get back to the start of the tunnel. Paul is not as fast as Johnny, but he is better than either George or Ronnie.
c) Finally, Johnny and Paul make the final trip. This puts all four members in the fallout shelter, with a total of 17 minutes elapsed time.
This is actually a general principle of scheduling, when there is a bound on the time that has to be used for a particular task.
- 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.
Sharpen your Coding Skills - Elevator Puzzle