Friday, March 24, 2006

Solution to the NexTag card shuffle problem

I found the NexTag card shuffle problem from Reddit interesting enough to solve as it reminded me of the problems from IOI and ACM competitions from long ago.

The problem is the following:

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);".


Spoilers follow.

Each card has a position and each shuffle takes each card and transfers it to a different position. The number of transfers during which one particular card ends up in its initial position is the cycle length for that card. The number of shufles for reaching the starting position is the least common multiple of all the cycle lengths.

Code follows (runs in less than 10 milliseconds):
package com.blogsummaries;

/**
* @author http://blogsummaries.blogspot.com/
*
/
public class BlogSummariesShuffle {
public static void main(String[] args) {
final int cardCount = 1002;
final int cutSize = 101;

final long startTime = System.currentTimeMillis();
long result = shuffles(cardCount, cutSize);
final long endTime = System.currentTimeMillis();
final long totalTime = endTime - startTime;

System.out.println("shuffles(" + cardCount +
", " + cutSize + ") = " + result +
" (" + totalTime + " ms)");
}

private static long shuffles(int nCards, int iCut) {
// in which position will the card end up
// after one shuffle
final int[] pointers = new int[nCards];

if (2*iCut < nCards) { // cut is less than at half
final int midPortion = nCards - 2*iCut;

for (int i = 0; i < pointers.length; i++) {
if (i < iCut) // cut
pointers[i] = midPortion + i*2 + 1;
else if (i < nCards - iCut) // midportion
pointers[i] = i - iCut;
else // bottom
pointers[i] = midPortion +
(i - iCut - midPortion)*2;
}
} else { // cut is at more than a halfpoint
final int topPortion = nCards - 2*(nCards - iCut);

for (int i = 0; i < pointers.length; i++) {
if (i < topPortion) // top
pointers[i] = i;
else if (i < iCut) // midportion
pointers[i] = topPortion +
2*(i - topPortion) + 1;
else // bottom
pointers[i] = topPortion + 2*(i - iCut);
}
}

// how many shuffles will it take for the card
// to end up in the starting position
final long[] cycleLength = new long[pointers.length];
for (int i = 0; i < pointers.length; i++) {
int current = pointers[i];
cycleLength[i] = 1;
while (current != i) {
current = pointers[current];
cycleLength[i]++;
}
}

// the LCM of all the cycle lengths is the number
// of shuffles needed for ALL the cards to end up
// in their initial places
long lcm = cycleLength[0];
for (int i = 1; i < cycleLength.length; i++) {
lcm = lcm(lcm, cycleLength[i]);
}

return lcm;
}

private static long lcm(long a, long b) {
return (a*b) / gcd(a, b);
}

private static long gcd(long a, long b) {
return (b == 0) ? a : gcd(b, a % b);
}
}