Crazy Croupier - 2nd Tuenti Challenge - 12

CrazyCroupier.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * Crazy Croupier - 2nd Tuenti Challenge - 12
 * 
 * Example:
 * Number of cards: N = 10
 * Number of cards in the first set: L = 3
 * Cards: 10 1 4 2 8 5 6 7 3 9
 * 
 * First set: 10 1 4
 * Second set: 2 8 5 6 7 3 9
 * 
 * Shuffled set: 4 9 1 3 10 7 6 5 8 2
 */
public class CrazyCroupier {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // read number of cases
        int cases = Integer.parseInt(scanner.nextLine());

        for (int i=1; i<=cases; i++) {
            // read N L, for example 10 6
            String line = scanner.nextLine();
            String[] arguments = line.split(" ");

            // N = cards in the deck
            int N = Integer.parseInt(arguments[0]);

            // L cards in the first bunch (where to cut the deck)
            int L = Integer.parseInt(arguments[1]);

            long result = processCase(N, L);
            System.out.printf("Case #%d: %d\n", i, result);
        }
    }

    /**
     * Returns the number of shuffles required to return the deck to its original order.
     * The algorithm will calculate the number of iterations that each individual card needs
     * to come back to its position. The solution will be the least common multiple (lcm)
     * of the individual results.
     */
    private static long processCase(int n, int cut) {
        int[] deck = new int[n]; // first deck shuffling result

        shuffleDeck(n, cut, deck);

        // cache source -> target positions for O(1) access
        final Map<Integer, Integer> permutations = new HashMap<Integer, Integer>();
        for (int i=0; i<deck.length; i++) {
            permutations.put(deck[i], i+1);
        }

        // cache to avoid multiple lcd calculations for the same num, O(1) access
        Set<Long> calculatedLcm = new HashSet<Long>();
        long lcm = 0;
        for (int i=0; i<deck.length; i++) {
            long numberPermutations = 1; // we already did the first shuffling
            int currentPosition = i+1;

            // still no at the original position
            while (currentPosition != deck[i]) {
                numberPermutations++;
                currentPosition = permutations.get(currentPosition);
            }

            if (calculatedLcm.contains(numberPermutations) == false) {
                lcm = lcm(lcm, numberPermutations);
                calculatedLcm.add(numberPermutations);
            }
        }

        return lcm;
    }

    /**
     * Shuffles the deck one time according to the algorighm.
     */
    private static void shuffleDeck(int n, int cut, int[] deck) {
        int min = Math.min(cut, n-cut); // number of cards shuffled

        // shuffle two bunch of cards
        for (int i=0; i<min; i++) {
            deck[2 * i] = cut - i;   // 1st bunch
            deck[2 * i + 1] = n - i; // 2nd bunch
        }

        // put the rest of the cards in proper order, at the end
        for (int i=0; i<n - 2 * min; i++) {
            if (cut >= n / 2) { // first bunch is bigger
                deck[n - 1 - i] = i + 1;
            } else { // second bunch is bigger or equal
                deck[2 * min + i] = n - min - i;
            }
        }
    }

    /**
     * Least common multiple. Probably a more efficient approach can be found but
     * it is good enough.
     */
    private static long lcm(long a, long b) {
        if (a == 0 || b == 0) {
            return Math.max(a, b);
        }
        return a * b / gcd(a, b);
    }

    /**
     * Greatest common divisor, see also {@link BigInteger#gcd(BigInteger)}
     */
    private static long gcd(long a, long b) {
        long mod = a % b;
        return mod == 0 ? b : gcd(b, mod);
    }
}