// Arup Guha
// 5/12/09
// Solution to 2009 AP Computer Science A
// Free Response Section Problem 4: TileGame

// Note: I want to make the solution fit in one file, so I am making this 
//       class default instead of public. It doesn't change any of the 
//       relevant issues in this problem. I have written an implementation
//       so that I can test the TileGame class.

import java.util.*;

class NumberTile {
	
	private int[] values;
	
	public NumberTile(int up, int right, int down, int left) {
		values = new int[4];
		values[0] = up;
		values[1] = right;
		values[2] = down;
		values[3] = left;
	}
	
	// Sorry no loop, I got lazy.
	public void rotate() {
		int temp = values[0];
		values[0] = values[3];
		values[3] = values[2];
		values[2] = values[1];
		values[1] = temp;
	}
	
	// Accessors...
	public int getLeft() {
		return values[3];
	}
	
	public int getRight() {
		return values[1];
	}
	
	public int getUp() {
		return values[0];
	}
	
	public int getDown() {
		return values[2];
	}
}

public class TileGame {
	
	private ArrayList<NumberTile> board;
	
	public TileGame() {
		board = new ArrayList<NumberTile>();
	}
	
	// Solution to part (a)
	private int getIndexForFit(NumberTile tile) {
		
		// No tiles, so this one goes in slot 0.
		if (board.size() == 0)
			return 0;
			
		// Try fitting it all the way to the left, first.
		if (tile.getRight() == (board.get(0).getLeft()))
			return 0;
			
		// Try each gap position. Here, two pairs of numbers must match.
		for (int i=0; i<board.size()-1; i++) {
			
			// Check left side of tile with Tile i.
			if (tile.getLeft() == (board.get(i).getRight()))
				
				// Check right side of tile with Tile i+1.
				if (tile.getRight() == (board.get(i).getLeft()))
					return i+1;
					
		}
		
		// Now, try fitting the tile at the very end.
		if (tile.getLeft() == (board.get(board.size()-1).getRight()))
			return board.size();
			
		// If we get here, the tile doesn't fit anywhere!
		return -1;
	}
	
	public boolean insertTile(NumberTile tile) {
		
		// Try four times for four rotations.
		for (int i=0; i<4; i++) {
			
			// Try out this orientation for the tile.
			int index = getIndexForFit(tile);
			
			// We found a fit.
			if (index != -1) {
				board.add(index, tile);
				return true;
			}
				
			// Try the next rotation.
			tile.rotate();	
		}
		
		// If we get here, none of the rotations worked.
		return false;
	}
	
	// Just for testing purposes.
	public void printTiles() {
		
		// Prints out first row, with each up value.
		for (int i=0; i<board.size(); i++) {
			System.out.print("  "+board.get(i).getUp()+"   ");
		}
		System.out.println();
		
		// Prints out second row, with each left and right value.
		for (int i=0; i<board.size(); i++) {
			System.out.print(board.get(i).getLeft()+"   "+board.get(i).getRight()+" ");
		}
		System.out.println();
		
		// Prints last row with each down value, and skips a line.
		for (int i=0; i<board.size(); i++) {
			System.out.print("  "+board.get(i).getDown()+"   ");
		}
		System.out.println();
		System.out.println();
	}
	
	public static void main(String[] args) {
		
		// Inserting tiles from sample in reverse order, so they fit the
		// way they are drawn in the question.
		TileGame t = new TileGame();
		t.insertTile(new NumberTile(5,9,2,2));
		t.insertTile(new NumberTile(3,2,5,2));
		t.insertTile(new NumberTile(1,2,3,4));
		t.insertTile(new NumberTile(6,4,3,3));
		t.insertTile(new NumberTile(4,3,7,4));
		
		t.printTiles();
		
		// This is the test tile from the sample. My code should put it in index 3.
		if (t.insertTile(new NumberTile(4,2,9,2))) {
			System.out.println("The new tile was successfully inserted.");
			System.out.println("Here is the new configuration:");
			t.printTiles();
		}
		
		// This tile should not fit.
		if (!t.insertTile(new NumberTile(3,2,5,8)))
			System.out.println("This tile could not fit.\n");
			
		// Let's try a case that requires a rotation.
		if (t.insertTile(new NumberTile(4,2,9,8))) {
			System.out.println("The new tile was successfully inserted.");
			System.out.println("Here is the new configuration:");
			t.printTiles();
		}
	}
}