It’s Friday, and time again for a new Fragment: my weekly programming-related puzzle.
This Week’s Fragment
“I knew I couldn’t trust that guy!”, exclaimed Joe the Plumber, having just returned from selling left-handed monkey wrenches at the pipe fitters’ convention. “I sold a wrench to this guy, Pierre Lefebvre, who didn’t have enough cash, nor have his checkbook or credit card with him. So I had him write his account information for both on a sheet of paper and give it to me. The checking account information is bad (my bank says that the routing number, 374088048, is invalid), and the paper is torn such that I don’t have the last digit of the credit card number, just 4754 2700 7476 257.”
Inspector Lestrade took one look at the paper and responded, “I can tell you the correct checking number or credit card number, or both. Which would you like?”
How did Lestrade do it? Can you determine the correct numbers?
If you want to “play along”, post a solution as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post. For an extra challenge, try writing code to correct the numbers or at least prove that the numbers you chose were valid. Maybe one day a plumber will thank you.
Last Week’s Fragment – Solution
You have 13 bottles of wine, and have been tipped off that one of them is tainted with a deadly poison: so deadly that one drop can kill a person or large animal within 24 hours. With the help of four lab rats, how can you determine which one contains the fatal potion within one day?
The solution requires giving some rats wine from multiple bottles, and since the poison is so deadly, a little dab’ll do ya’ (or do in a rat). Joel proposed a “divide and conquer” or “binary search” approach, which is nice and elegant and does the job (it’s also the solution I first thought of when I heard this on Car Talk). But there’s only time for one round of testing, so you’ll have to throw all four rats at the problem at once.
Thinking in binary is the right approach. Number the bottles 1-13 and represent each number in binary: 0001 through 1101. Assign each of the four rats to one of the binary “positions”; let’s call them “A” in the one’s position, “B” in the two’s position, “C” in the four’s position, and “D” in the eight’s position. And dole out the wine based on the binary representation of each bottle number. For example, bottle number 1 goes to rat A, bottle 2 to rat B, bottle 3 (binary 0011) to rats A and B, and so on up to bottle 13 (binary 1101) given to rats A, C, and D. The rats that kill over will identify the bottle number.
Wayne posted this solution and should probably get a bottle of poisoned Quivira wine as a prize. Both Wayne and Joel noted that we could take on up to 16 bottles of wine with this solution, but I went with Car Talk’s lucky thirteen to keep it interesting.