Solution to the NexTag card shuffle problem

2006-03-24T12:00:00.000-08:00

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

Blog Summaries

Solution to the NexTag card shuffle problem