### 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:

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):

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

}

}