The Nextag Shuffling Puzzle


Its been a while since I have had any time to post anything on this blog. Not that I have time right now. It seems I am a constant rat-race marathon runner, and any kind of leisure, even of the educational variety, is unaffordable luxury. What that means is that this post isn't going to be as detailed as I would have liked it to be (which is probably how most of the future posts here will have to look like if I am going to be able to keep this blog alive at all).

So, here goes ...

A few weeks ago I ran into the puzzle below posted on the web somewhere. I don't remember the original link, but it turned out to be an applicant screening puzzle originating from the search engine company Nextag.

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut);

Please send the results of shuffles(1002, 101) along with your program ...

This is a perfect example of the kind of puzzles that fall into the category of Algoritmic Diversions. The sort of problems that are hard to solve by hand or analytically, and algorithmic solutions to which are difficult enough to make naive implementations inadmissible. For the best examples of such puzzles (which this is certainly one of), there are short and elegant solutions that trigger the "AHA!" response in people who have interest in such matters.

It seems the puzzle has been up for a while, and there are dozens of solutions posted all over the place. It had me going for a couple of days, at the end of which I came up with my own solution. I don't know if this is the best solution, it certainly seems more terse than some of the ones I have seen floating around. My spoiler is posted here (zip form, password is "crafty1255"), but I recommend that readers resist the temptation to look before coming up with their own solutions. I promise it will be a lot of fun. I'd love to see other solutions (not necessarily in Java), and will post the best and/or most interesting ones here. So get out your compilers, get set, ready, go ...