package com.emansoft.shuffling;

/**
 * @author Emanuel M. Kadziela
 *         Date: Jul 25, 2005
 */
public class Shuffles
{
    static long shuffles(int nCards, int iCut)
    {
        long shuffles = 0;

        //initialize the deck
        int[] initialDeck = new int[nCards];
        int[] markings = new int[nCards];
        for (int i=0; i<nCards; i++)
            initialDeck[i] = i;
        //printDeck(initialDeck, shuffles);

        //cut and shuffle the initial deck for the first time
        int[] tempDeck = cutAndShuffle(initialDeck, iCut);
        //count the first shuffle
        shuffles++;
        markings = markWaves(tempDeck, markings, shuffles);
        //compare the shuffled deck to the original deck and if they are different,
        // keep shuffling, comparing and counting
        while (!java.util.Arrays.equals(initialDeck, tempDeck))
        {
            //printDeck(tempDeck, shuffles);
            tempDeck = cutAndShuffle(tempDeck, iCut);
            shuffles++;
            markings = markWaves(tempDeck, markings, shuffles);
            long result = processWaves(markings);
            if (result != -1)
                return result;
        }
        //printDeck(tempDeck, shuffles);
        System.out.println("returning based on shuffles");
        return shuffles;
    }

    static int[] cutAndShuffle(int[] deck, int iCut)
    {
        int[] top = new int[iCut];
        int[] bot = new int[deck.length - iCut];
        int[] result = new int[deck.length];
        //cut the deck
        for (int i=0; i<iCut; i++)
            top[i] = deck[i];
        for (int j=0;j<(deck.length-iCut); j++)
            bot[j]=deck[iCut+j];

        //shuffle the two decks back into one deck
        int iBotIndex = bot.length;
        int iTopIndex = top.length;
        while(iTopIndex > 0 && iBotIndex > 0)
        {
            iTopIndex--;
            result[iTopIndex+iBotIndex] = top[iTopIndex];//bottom card from the top deck goes down
            iBotIndex--;
            result[iTopIndex+iBotIndex] = bot[iBotIndex];//bottom card from the bottom deck goes down

        }
        while (iTopIndex > 0)
        {
            iTopIndex--;
            result[iTopIndex] = top[iTopIndex];
        }
        while (iBotIndex > 0)
        {
            iBotIndex--;
            result[iBotIndex] = bot[iBotIndex];
        }

        return result;
    }


    static void printDeck(int[] deck, long shuffles)
    {
        System.out.print("shuffle number: "+shuffles+" : [");
        for (int i = 0; i<deck.length; i++)
        {
            System.out.print(deck[i]+" ");
        }
        System.out.println("]");
    }

    static int[] markWaves(int[] deck, int[] markings, long shuffles)
    {
        for (int i=0; i<deck.length; i++)
            if (deck[i] == i)
                if (markings[i] == 0)
                    markings[i] = (int) shuffles;
        return markings;
    }
    static long processWaves(int[] markings)
    {
        for (int i=0; i<markings.length; i++)
            if (markings[i] == 0)
                return -1;
        long result = markings[0];
        for (int j=1; j<markings.length; j++)
        {
            long mark = (long) markings[j];
            if ( ((result % mark) != 0) && ((mark % result) != 0) )
            {
                result = reduceAndMultiply(result,mark);
            }
            else if (mark > result)
                result = mark;
        }
        return result;
    }
    static long reduceAndMultiply(long result, long mark)
    {
        int iterations = 0;
        for (int i=2;i<111;i++)
        {
            while (result%i==0 && mark%i==0)
            {
                result = result/i;
                mark = mark/i;
                iterations++;
            }
            if (iterations>0)
                result = result*iterations*i;
            iterations=0;
        }
        result = result*mark;
        if (mark>110)
        {
            for (int j=2; j<100; j++)
                if (mark%j==0)
                    return result;
            System.out.println("Warning, the number of shuffles may be excessive as I check for common prime factors" +
                    "only up to 111 and seem to have found one exceeding 111");
        }
        return result;
    }

    public static void main (String args[])
    {
        int iDeck = new Integer(args[0]).intValue();
        int iCut = new Integer(args[1]).intValue();
        System.out.println("It takes "+shuffles(iDeck, iCut)+" shuffles to do a deck of "
                        +iDeck+" cards with a cut of "+iCut+" cards.");
    }

}