The Friday Fragment

Published on 20 March 2010
This post thumbnail

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

This Week's Fragment

While the code required to solve this week's puzzle is small, it requires a little setup. I'll do it in story form.

Little Johnny is riding along in the toddler seat at the back of Mom's minivan, secretly playing with Dad's new deck of cards which he is not allowed to touch. Mom gives him the long-awaited news, "we're almost there", and he panics: he knows he must put the cards back in the box just the way he found them. That means just like new, sorted in suit and rank order. Little Johnny's stubby fingers aren't very dexterous, but he knows he can sort them by laying them out in piles and then re-stacking the piles until they're ordered. So he grabs his Toy Story 2 lunch box, which gives him room for 4 piles. He has to hurry, but fortunately he knows a way to do it in only four passes of laying out cards into piles and stacking the piles. Johnny's a smart little toddler, because he knows which pile to put each card in for each pass to make this all work.

Are you smarter than a toddler?  Can you write the code to determine the pile number for each card on each pass so that they're all sorted in the end?

To help out, I'll post a comment with some scaffolding code. If you want to use it, just fill in the missing line.

What this is really is a technique that banks have used for years to sort large numbers of checks into various orders (account number, destination, amount, etc.) on machines that have anywhere from 5 to 35 available pockets. It's called a fine sort with compression and base conversion, which sounds really fancy but actually boils down to one or two lines of code.

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

Last week's puzzle was to solve the following cryptogram:

Si spy net work, big fedjaw iog link kyxogy

This cryptogram is the dedication in the excellent book, Network Security, by Kaufman, Perlman, and Speciner. Nothing fancy here: it's just a simple substitution cipher. So you can solve it by just sitting down with a pencil and paper and plugging at it, building up the substitution table as you go. Classic cryptanalysis starts with trying frequent letters (like the nostril combination - NSTRTL, familiar to Wheel of Fortune viewers), common patterns (ad, in, ing, ou, ur, etc.), and common words (to, the, and for are a great start for this puzzle). If you like such puzzles, try the cryptograms web site.

The solution is:

To the bad guys, for making our jobs secure

That's a clever dedication for a book on computer security, huh?