import java.util.*;

public class Main
{
    private static Scanner stdin = new Scanner(System.in);
    public static void main(String[] args)
    {
        final int numberOfDisks = 10;

        int[] pegA  = new int[numberOfDisks];
        int[] pegB  = new int[numberOfDisks];
        int[] pegC  = new int[numberOfDisks];

        SetupDisks(pegA, pegB, pegC);
        PrintDisks(pegA, pegB, pegC);

        int steps = SolveTowers(pegA, pegB, pegC);

        PrintDisks(pegA, pegB, pegC);

        System.out.printf("Steps taken: %d\n", steps);

    }

    static int SolveTowers(int[] pegA, int[] pegB, int[] pegC)
    {
        int steps = 0;

        do
        {
            MakeLegalMove(pegA, pegB);
            //PrintDisks(pegA, pegB, pegC);

            MakeLegalMove(pegA, pegC);
            //PrintDisks(pegA, pegB, pegC);

            MakeLegalMove(pegB, pegC);
            //PrintDisks(pegA, pegB, pegC);

            steps += 3;
        } while(!CheckIfComplete(pegA, pegB, pegC));

        return steps;
    }

    static void SetupDisks(int[] pegA, int[] pegB, int[] pegC)
    {
        for(int i = 0; i < pegA.length; i++)
        {
            pegA[i] = i + 1;
            pegB[i] = -1;
            pegC[i] = -1;
        }
    }

    static void PrintDisks(int[] pegA, int[] pegB, int[] pegC)
    {
        for (int i = 0; i < pegA.length; i++)
        {
            System.out.printf("%d\t%d\t%d\n", pegA[i], pegB[i], pegC[i]);
        }

        System.out.println();
    }

    static int FindFirstEmptyIndex(int[] peg)
    {
        for(int i = peg.length - 1; i >= 0; i--)
        {
            if(peg[i] == -1)
            {
                return i;
            }
        }

        return -1;
    }

    static int FindFirstDiskIndex(int[] peg)
    {
        for(int i = 0; i < peg.length; i++)
        {
            if(peg[i] != -1)
            {
                return i;
            }
        }

        return -1;
    }

    static int LookupValueFromPeg(int[] peg, int index)
    {
        if(index == -1)
        {
            return Integer.MAX_VALUE;
        }

        return peg[index];
    }

    static void SwapDiskOnPeg(int[] pegFrom, int[] pegTo)
    {
        int pegFromDiskIndex = FindFirstDiskIndex(pegFrom);
        int pegToEmptyIndex = FindFirstEmptyIndex(pegTo);

        pegTo[pegToEmptyIndex] = pegFrom[pegFromDiskIndex];
        pegFrom[pegFromDiskIndex] = -1;
    }

    static void MakeLegalMove(int[] peg1, int[] peg2)
    {
        //Step 1: Find out which peg we are moving from and to.
        int peg1DiskIndex = FindFirstDiskIndex(peg1);
        int peg2DiskIndex = FindFirstDiskIndex(peg2);

        int peg1DiskValue = LookupValueFromPeg(peg1, peg1DiskIndex);
        int peg2DiskValue = LookupValueFromPeg(peg2, peg2DiskIndex);

        if(peg1DiskValue == peg2DiskValue)
        {
            System.out.printf("Error: disks contain same value. Both empty?\n");
            return;
        }
        else if(peg1DiskValue > peg2DiskValue)
        {
            //Move peg2 to peg1
            SwapDiskOnPeg(peg2, peg1);
        }
        else
        {
            //Move peg1 to peg2
            SwapDiskOnPeg(peg1, peg2);
        }
    }

    static boolean CheckIfComplete(int[] pegA, int[] pegB, int[] pegC)
    {
        for(int i = 0; i < pegA.length; i++)
        {
            if(pegA[i] != -1 || pegB[i] != -1 || pegC[i] != i + 1)
            {
                return false;
            }
        }

        return true;
    }
}