// =============================================================================
/**
 * Print a variety of basic 2D patterns to the console.
 *
 * @author sfkaplan@cs.amherst.edu
 */
public class Towers {
// =============================================================================


    // =========================================================================
    /**
     * The program's entry point.
     *
     * @param args The command-line arguments provided by the user.
     */
    public static void main (String[] args) {

	// If an incorrect number of arguments was provided on the command-line,
	// then print the correct usage and exit.
	if (args.length != 1) {
	    showUsageAndExit();
	}

	// Grab the argument.
	int numRings = 0;
	try {
	    numRings = Integer.parseInt(args[0]);
	} catch (NumberFormatException e) {
	    showUsageAndExit();
	}
	if (numRings < 0) {
	    showUsageAndExit();
	}

	Ring[][] towers = initialize(numRings);
	solve(towers);

    } // main()
    // =========================================================================



    // =========================================================================
    public static void solve (Ring[][] towers) {

	int numRings = towers[0].length;
	print(towers);
	move(towers, 0, 2, numRings);

    } // solve()
    // =========================================================================



    // =========================================================================
    public static void move (Ring[][] towers, int from, int to, int numToMove) {

	int other = 0;
	if (from + to == 1) {
	    other = 2;
	} else if (from + to == 2) {
	    other = 1;
	}

	if (numToMove > 0) {
	    move(towers, from, other, numToMove - 1);
	    moveOne(towers, from, to);
	    move(towers, other, to, numToMove - 1);
	}

    } // move()
    // =========================================================================



    // =========================================================================
    public static void moveOne (Ring[][] towers, int from, int to) {

	int fromTop = findTop(towers[from]);
	int toTop = findTop(towers[to]) + 1;
	Ring temp = towers[to][toTop];
	towers[to][toTop] = towers[from][fromTop];
	towers[from][fromTop] = temp;
	print(towers);

    } // moveOne()
    // =========================================================================



    // =========================================================================
    public static int findTop (Ring[] tower) {

	int top = tower.length - 1;
	while ((top >= 0) && (tower[top].getSize() == 0)) {
	    top -= 1;
	}
	return top;

    } // findTop()
    // =========================================================================
	


    // =========================================================================
    public static Ring[][] initialize (int numRings) {

	Ring[][] towers = new Ring[3][numRings];
	for (int i = 0; i < towers.length; i += 1) {
	    for (int j = 0; j < numRings; j += 1) {
		int ringSize = 0;
		if (i == 0) {
		    ringSize = numRings - j;
		}
		towers[i][j] = new Ring(ringSize);
	    }
	}

	return towers;

    } // initialize()
    // =========================================================================



    // =========================================================================
    public static void print (Ring[][] towers) {

	int numRings = towers[0].length;
	for (int row = numRings - 1; row >= 0; row -= 1) {
	    for (int tower = 0; tower < 3; tower += 1) {
		Ring currentRing = towers[tower][row];
		currentRing.print(numRings);
		System.out.print("\t");
	    }
	    System.out.println();
	}
	System.out.println();

    }
    // =========================================================================



    // =========================================================================
    /**
     * Print the correct form for running this program and exit with an error
     * code.
     */
    public static void showUsageAndExit () {

	System.err.println("USAGE: java Towers <number of rings>");
	System.exit(1);
	
    } // showUsageAndExit()
    // =========================================================================



// =============================================================================
} // class Towers
// =============================================================================