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?
As promised, here’s some scaffolding code, in Smalltalk. You code the missing part.
| cardCount pileCount passCount cards random stack | "Some constants:" cardCount := 52. pileCount := 4. passCount := 4. "Shuffle the cards:" random := EsRandom new. cards := ((1 to: cardCount) asSortedCollection: [ :a :b | random next > 0.5 ]) asOrderedCollection. "Sort the cards:" stack := cards copy. 1 to: passCount do: [ :eaPass | | piles | "Put each card from the stack into the correct pile:" piles := (1 to: pileCount) collect: [ :ea | OrderedCollection new ]. 1 to: cardCount do: [ :eaCardIndex | | card pileNumber | card := stack removeFirst. pileNumber := 1. "REPLACE THIS WITH YOUR CODE TO CALCULATE THE PILE #" (piles at: pileNumber) add: card ]. "Done with this pass, now stack up the piles:" piles do: [ :eaPile | stack addAll: eaPile ]]. "Stack is now sorted:" (cards -> stack) inspectThis solution can actually sort all the cards in just 3 passes, since log(52)/log(4) < 3.
pileNumber := ((card / (pileCount raisedTo: (eaPass – 1))) ceiling) \\ pileCount.
(pileNumber = 0) ifTrue: [pileNumber := pileCount.].
Of course, Little Johnny called me up to remind me the that the real goal of the problem was to keep him out of trouble for playing with the cards. He told me my solution required dealing 3*52 or 156 cards and would have taken too long. So Little Johnny explained the real problem was to sort the cards moving as few as cards possible. He first dealt 4 piles separating by suit. Then picking up pile one, he fanned all 13 cards at once and picked out the cards in order laying them in the empty spot where pile one previously occupied. Sometimes he could place two or more cards at a time since they were already in sequence in his hand. As more cards were removed from his hand the odds increase that multiple cards could be laid down at once. He then repeated the process for the other three piles (suits). Johnny only required two dealing passes (moving less than 100 cards) , and had the cards back in order, ready to be put in the box in record time.
While a document processor can’t selectively feed the lowest document, Johnny could easily pick the lowest card from his hand. He doesn’t have to know (or be taught) base 4 numbers or compression. And he sorted the cards in ~60% of the time of the 3 pass sort…Keeping him out of trouble and his parents clueless.
This is a good reminder that identifying the customer’s REAL problem isn’t always as easy as it first appears. The key is to listen to your customer. The time constraint wasn’t explicitly stated in Johnny’s problem, but is the most important factor to Johnny not getting caught. We were told Johnny knows how to do a 4 (or three) pass sort, but we shouldn’t care. It’s not part of the problem. Don’t get caught up in the technical merits or short comings of proposed solutions without first finding a solution that solves the customer’s real problem.
Very good point, Joe. Of course, Johnny’s story is contrived, down to the blurb I included about Little Johnny’s stubby fingers not being dexterous in order to “force” a non-fanning solution. But requirements are indeed king. And we’ve both had & been around enough young ones to know that a real-life Johnny would probably just find a sibling or pet to blame it on: requirements met, problem solved! 🙂