A Fun Programming Challenge

by William Grosso

Related link: http://www.nextag.com/serv/main/about/jobs/java.jsp



A friend sent me the following programming problem, which comes from the NextTag website.



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


On their site, they're using this as a screening function for software developers. As they put it:



We are looking for Java developers to help build our e-commerce web application. Try out this Programming Problem and see if you can make it run within a few minutes or less.


I'm not certain I understand why this is related to an e-commerce application, but it's an interesting challenge. Or, at least, I thought it was (Call me a dang-fool-coder, but sometimes I just like to hack away at problems).


After 4 hours, I've got it down to 31 milliseconds on the machine I'm using. I think that's good enough.


The fun part, for me, was realizing just how computationally intensive this problem really is, and, consequently, how bad my initial guess at how to do solve it was. At the end of the day, a few cute tricks and a little bit of thought about prime factorizations solved the problem in ways that objects named "deck" and "shuffler" didn't.

The hard question: is there a closed form solution for this problem?


8 Comments

Scott_Sauyet
2004-06-21 20:16:05
Comparing code
I'd be interested to see how you did it (or others who tried as well.) My code is posted below. It took about an hour, and runs in 10ms on my 1.5GHz Pentium with 512MB RAM. On my 2.4 GHz, 512 MB Pentium at home, it takes less than one millisecond. (I have a background in mathematics, so most of my hour was not spent in determining algorithms but in typing and debugging.) Is your code significantly different?


public class Deck {


public static long shuffle(int nCards, int iCut) {
Deck deck = new Deck(nCards);
deck.shuffle(iCut);
return lcm(deck.getCycles());
}

public Deck(int count) {
if (count < 1) {
throw new IllegalArgumentException("Deck must contain at least " +
"one card. You entered " + count + ".");
}
this.count = count;
cards = new int[count];
for (int i = 0 ; i < count; i++) {
cards[i] = i;
}
}


public void shuffle(int cut) {
cut = cut % count;
int[] top = new int[cut];
System.arraycopy(cards, 0, top, 0, cut);
int[] bottom = new int[count - cut];
System.arraycopy(cards, cut, bottom, 0, count - cut);
int[] updated = new int[count];
int shared = Math.min(cut, count - cut);
int different = count - shared - shared;
int[] extras = new int[different];
if (cut > count - cut) {
System.arraycopy(top, 0, extras, 0, different);
} else {
System.arraycopy(bottom, 0, extras, 0, different);
}
for (int i = 0; i < shared; i++) {
updated[count - (2 * i) - 1] = top[cut - i - 1];
updated[count - (2 * i) - 2] = bottom[count - cut - i - 1];
}
System.arraycopy(extras, 0, updated, 0, different);
cards = updated;
}


public int[] getCycles() {
int[] cycles = new int[count];
for (int i = 0; i < count; i++) {
int index = i;
int result = 1;
while (cards[index] != i) {
result++;
index = cards[index];
}
cycles[i] = result;
}
return cycles;
}


public String toString() {
StringBuffer buffer = new StringBuffer();
buffer.append("Deck [");
buffer.append(cards[0]);
for (int i = 1; i < count; i++) {
buffer.append(", ");
buffer.append(cards[i]);
}
buffer.append("]");
return buffer.toString();
}


private static long gcd(long a, long b) {
if (a == 0 && b == 0) return 1;
if (a < 0) return gcd(-a, b);
if (b < 0) return gcd(a, -b);
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (b < a) return gcd(b, a);
return gcd(a, b % a);
}


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


private static long lcm(int[] values) {
long result = 1;
for (int i = 0; i < values.length; i++) {
result = lcm(result, values[i]);
}
return result;
}

private int[] cards;
private int count;


public static void main(String[] args) {
if (args.length != 2) {
System.out.println("Usage: java Deck nCards iCut");
System.exit(1);
}
int cards = 0;
int cut = 0;
try {
cards = Integer.parseInt(args[0]);
cut = Integer.parseInt(args[1]);
} catch (NumberFormatException nfe) {
System.out.println("Arguments must be numeric.");
System.exit(2);
}
long start = System.currentTimeMillis();
long result = shuffle(cards, cut);
long time = System.currentTimeMillis() - start;
System.out.println("A perfect shuffle on " + cards + " cards, cut " + cut
+ " deep, takes " + result + " iterations to restore"
+ " the deck.");
System.out.println("Calculation performed in " + time + "ms.");
}
}


The most interesting decision was to not reduce to a canonical set of cycles. There is a cycle length listed for each card in the shuffle. This can cause no problems, since multiple copies will wash out of the least common multiple ("lcm" and "gcd" refers to the gretest common divisor.)


I would be curious to see if there are significantly different approaches to this.


Thanks,


-- Scott Sauyet

wegrosso
2004-06-21 22:20:57
Comparing code
My version is more efficient (my home machine is a P-3 866), but the two approaches are fairly equivalent.
David_You
2005-05-27 13:17:06
Comparing code
Oh, just find the Next Tag Question and come to here.
The program can be further optimized, basically you don't have to re-calculate the cycle number in a shuffle loop. replace the code within the loop with this will be much faster for a bigger number say "A perfect shuffle on 100001 cards, cut 101 deep"
==========
if (cycles[i] != 0) { //calculated already
continue;
}
int index = i;
int result = 1;
while (cards[index] != i) {
result++;
index = cards[index];
}
cycles[i] = result;
//reset index
index = i;
//Set the Loop's cycle's result.
while (cards[index] != i) {
cycles[index] = result;
index = cards[index];
}
================
David_You
2005-05-27 13:56:44
Comparing code
And there should be a math way to calculate how many shuffle loops it has and how big the groups are instead of using the brutal computing force. But then, it becomes a total math problem instead of a programming problem, which makes it a not so good interview question for Java Developers.
sideysinghsodhi
2005-06-26 01:18:28
Comparing code
I am confused here.


for:
nCards=1002
iCut=101


I ran the code on this page (class Deck) and it computes the answer to be:
5812104600


whereas, my code computes it as:
152760


my code follows:


import java.util.*;


public class Shuffles {

long shuffles(int nc, int ic) {
int vs[] = new int[nc];
int tvs[] = new int[nc];

int i, j, k;
for(i=0;i long tot = 0;
boolean done = false;
int minv = Math.min(ic, nc-ic);
int rem = minv + (nc- (2*minv));

do {
j = nc-1;
for(i=0;i tvs[j] = vs[i];
tvs[j-1] = vs[nc-i-1];
j -= 2;
}
for(i=minv,j=0;i for(i=0;i
//for(i=0;i //System.out.println();

tot++;

done = true;
for(i=0;i done = false;
break;
}
//if(v%1000==0) System.out.println(v);
} while(!done);
return tot;
}

public static void main(String args[]) {
Shuffles s = new Shuffles();

long t1 = System.currentTimeMillis();
System.out.println("total shuffles = " + s.shuffles(1002, 101));
long t2 = System.currentTimeMillis();

System.out.println("total time = " + (t2-t1));
}
}

fschmidt
2005-07-19 09:15:11
why this problem
Why is this problem related to an e-commerce application? It isn't. Good programmers can program anything, and this problem is designed to find good programmers.


I made this problem up about 20 years ago when a friend asked me something about shuffling cards at a time when I was looking for a problem to screen programmers. I have been using this problem to screen programmers at various companies ever since. Good programming often requires making a first pass design, and then stepping back and rethinking the problem to find the best solution. Very few simple problems require this, but the card shuffling problem is one. I assume everyone knows the little math required. What is really needed is the ability to visualize what is happening, and make an insight from that. And this kind of thinking is what programming is about.


I would like to continue using this problem to screen programmers, but unfortunately this page shows up in Google. I would greatly appreciate it if a "noindex" meta-tag were added to this page, as in:



tmoertel
2006-03-23 14:45:39
Tried it in Haskell
If you want to see a tiny solution in the Haskell programming language, I have posted one here:


http://blog.moertel.com/articles/2006/03/23/the-perfect-shuffles-puzzle-solved-in-haskell


Cheers,

Tom

SmithJameson
2006-03-24 13:45:31
another, quite elegant solution
This one's nice:
http://blogsummaries.blogspot.com/