The Friday Fragment

It's Friday, and time again for a new Fragment: my weekly programming-related puzzle. For some background on Friday Fragments, see the earlier post.

This Week's Fragment

I "borrowed" this week's fragment from a recent Car Talk puzzler. I prefer original ones, but since this one follows last week's well, I thought I'd re-use it.

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?

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.

Last Week's Fragment - Solution

"If God had intended us to have computers, he would have given us 16 fingers." Anonymous

Last week's puzzle reminds us that there are three kinds of people in the world: those who understand binary, and those who don't. Your job was to write code to dictate which pile each of 52 playing cards should land in when sorting in multiple passes with only four piles. It was a spin on an old fine sort with base conversion and compression algorithm used for sorting checks and other things.

I received some excellent responses from base conversion pros like Joe Richardson and Stephen Ake. I'll publish Stephen's code, since I like his better than mine:

pileNumber := ((card / (pileCount raisedTo: (eaPass – 1))) ceiling) \\ pileCount. (pileNumber = 0) ifTrue: [pileNumber := pileCount].

If you're in that second (third?) group who doesn't keep their checkbooks in hex and is happy with the 10 fingers God gave us, think of it the following way...

If I let you use 13 piles on the first pass, then you could easily do it in two passes. In the first pass, sort by rank (13 piles), and then stack those up and sort by suit (4 piles). You could treat the suit and rank of each card as a two-digit number, with the rank as the low-order "digit" and the suit as the high-order "digit."

But Johnny didn't have room on his Toy Story 2 lunchbox for 13 piles on the second pass, only 4. So he had to convert the suit and rank of each card to a base 4 number. That's the base conversion part, which is important when the number of available piles (or pockets on a sorter) doesn't match the original base of the number. That's because you want to make the best use of all piles/pockets on all passes.

When sorting by things like account numbers on checks, there can also be gaps in the numbers, which wastes pockets and passes. To avoid this problem, you assign "aliases" to each number. For example, if the first two account numbers are 13500001 and 13511115, renumber the first account as "1", and the second as "2", and sort on the aliases. That's the compression part.

This is easier for ten-fingered humans to follow if we use 10 piles to sort cards with the numbers 000 through 999. The pile number for the first pass would be the digit in the ones position, then the tens position, and then the hundredths position. That's the 10^1, then 10^2, then 10^3 position, or the pocket count raised to the pass number. In code, a modulus (remainder) division "strips off" this digit for use.

Kudos to Joe and Stephen for also noticing that it can be done in only three passes, not four. That's because 52 base 4 is a three-digit number. I wasn't trying to be tricky; I just forgot to edit after deciding to give Johnny 4 piles instead of 3. And kudos to Stephen for solving it in Smalltalk (plugging into the scaffolding code I provided), since Smalltalk throws some extra twists: 1-based (not 0-based) arrays to adjust for, and a less-common exponentiation operator (raisedTo:, not ^). You can find Stephen's post in last week's comments; Joe sent me a funny response via email back on March 22; here's an excerpt:

Little Johnny is always one step ahead. He can sort the deck of cards using only 3 passes. Since Johnny is a smart kid, he assigns the numbers 1 through 13 to the cards of the first suit, 14-26 to the second suit, 27-39 the third, and 40-52 to the cards for the fourth suit. He does this in his head with no need of a sort pass. He then converts this decimal number to base 4 (since 4 piles are used). Knowing that 52 base 10 = 310 base 4, a three digit number, Johnny knows that it will take at most 3 passes to sort the cards. He might get lucky and sort the cards in only one or two passes. The first sort  pass uses the right most digit of this assigned base 4 number. The second pass uses the middle digit  and the third pass uses the left most digit.

Little Johnny has time left over to once again ask "Are we there yet?"

Finally, I neglected to mention that Luke (my middle son) solved last week's cryptogram. I often have to decode his (teen-speak) sentences, too.