# Paste: a

Author: a chill Thu, 5 Aug 2010 14:59:48
Plain Text |
import java.math.BigInteger;

public class RunShuffles {

private static int nCards, iCut;

public static void main(String[] args) {

nCards = Integer.parseInt(args[0]);
iCut = Integer.parseInt(args[1]);
//System.out.printf("nCards: %d, iCut: %d\n", nCards, iCut);

int unshuffledDeck[] = new int[nCards];
int shuffledDeck[] = new int[nCards];
int periods[] = new int[nCards];
int factors[] = new int[nCards];
long start_time = System.nanoTime();

for (int i = 0; i < nCards; i++) {
unshuffledDeck[i] = i;
periods[i] = -1;
factors[i] = 0;
}

shuffledDeck = unshuffledDeck;
//printDeck(shuffledDeck);

for (int counter = 1; counter <= nCards; counter++) {
shuffledDeck = shuffle(shuffledDeck);
//printDeck(shuffledDeck);
for (int i = 0; i < nCards; i++) {
if (periods[i] == -1 && shuffledDeck[i] == i) {
periods[i] = counter;
}
}
}

//System.out.printf("Final periods:\n");
//printDeck(periods);

BigInteger a = new BigInteger("1");
for (int i = 0; i < nCards; i++) {
a = lcm(a, new BigInteger(Integer.toString(periods[i])));
}

System.out.printf("lcm: %s in %d ns\n", a.toString(), System.nanoTime() - start_time);

}

public static void printDeck(int[] deck) {
for (int i = 0; i < deck.length; i++) {
if (iCut == i) System.out.printf("| ");
System.out.printf("%d ", deck[i]);
}
System.out.printf("\n");
}

public static int[] shuffle(int[] deck) {
int smaller_size, i, j;
int new_deck[] = new int[nCards];

if (nCards - iCut > iCut) smaller_size = iCut;
else smaller_size = nCards - iCut;

for (i = 0; i < 2*smaller_size; i+=2) {
new_deck[nCards-i-1] = deck[iCut - i/2 - 1];
new_deck[nCards-i-2] = deck[nCards - i/2 - 1];
}

i /= 2;

if (iCut - i > 0) {
//	printf("Bottom pile was smaller\n");
for (j = 0; j < nCards - 2*(nCards-iCut); j++) {
new_deck[j] = deck[j];
}
}
else if (nCards - iCut - i > 0) {
//	printf("Top pile was smaller\n");
for (j = 0; j < nCards - 2*iCut; j++) {
new_deck[j] = deck[iCut + j];
}
}
return new_deck;

}

public static BigInteger lcm(BigInteger a, BigInteger b) {
BigInteger productAB = a.multiply(b);
return productAB.divide(b.gcd(a));
}

}