import java.util.ArrayList;
import java.util.Collection;

/**
 * @author Pieter Koopman, Sjaak Smetsers
 * @author Camil Staps, s4498062
 * 
 * A template implementation of a sliding game also
 * implementing the Graph interface
 */
@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.
public class SlidingGame implements Configuration
{
    public static final int N = 3, SIZE = N * N, HOLE = SIZE;
    
    /*
     * The board is represented by a 2-dimensional array;
     * The position of the hole is kept in 2 variables holeX and holeY
     * We store the summed manhattan of all tiles and the hole in manhattan
     */
    private final int [][] board;
    private int holeX, holeY;
    private final int manhattan;
    
    /*
     * A constructor that initializes the board with the specified array
     * @param start: a one dimensional array containing the initial board.
     * The elements of start are stored row-wise.
     */
    public SlidingGame (int [] start) {
        board = new int[N][N];

        assert start.length == SIZE: "Length of specified board incorrect";
        
        for( int p = 0; p < start.length; p++) {
            board[p % N][p / N] = start[p];
            if ( start[p] == HOLE ) {
                holeX = p % N;
                holeY = p / N;
            }
        }
        
        manhattan = calculateManhattan();
    }
    
    /**
     * A constructor that initialises the board with a specified 2D array
     * @param board a 2D array containing the initial board
     */
    public SlidingGame (int[][] board) {
        this.board = new int[N][N];
        
        assert board.length == N: "Length of specified board incorrect";
        
        for (int a = 0; a < N; a++) {
            assert board[a].length == N: "Length of specified board incorrect";
            for (int b = 0; b < N; b++) {
                this.board[a][b] = board[a][b];
                if (board[a][b] == HOLE) {
                    holeX = a;
                    holeY = b;
                }
            }
        }
        
        manhattan = calculateManhattan();
    }
    
    /**
     * Calculate the summed Manhattan distance for all tiles and the hole
     * @return the Manhattan distance
     */
    private int calculateManhattan() {
        int result = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                int this_x = (board[x][y] - 1) % N;
                int this_y = (board[x][y] - 1) / N;
                result += Math.abs(this_x - x) + Math.abs(this_y - y);
            }
        }
        return result;
    }
    
    public int getManhattan() {
        return manhattan;
    }
    
    /**
     * Attempt to move the hole in a specified direction
     * @param d the direction in which to move
     * @return A new instance of this class where the hole has moved
     * @throws ArrayIndexOutOfBoundsException If the hole cannot be moved
     */
    private SlidingGame move(Direction d) throws ArrayIndexOutOfBoundsException {
        int[][] newboard = new int[N][N];
        for (int a = 0; a < N; a++)
            System.arraycopy(board[a], 0, newboard[a], 0, N);
        
        newboard[holeX][holeY] = newboard[holeX + d.GetDX()][holeY + d.GetDY()];
        newboard[holeX + d.GetDX()][holeY + d.GetDY()] = HOLE;
        return new SlidingGame(newboard);
    }

    /*
     * Converts a board into a printable representation.
     * The hole is displayed as a space.
     * @return the string representation
     */
    @Override
    public String toString() {
        StringBuilder buf = new StringBuilder();
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                int puzzel = board[col][row];
                // Using String.format to pad left as in http://stackoverflow.com/a/391978/1544337; provides better formatting for puzzles with N > 3
                buf.append(String.format("%1$" + ((int) Math.log10(SIZE - 1) + 2) + "s", puzzel == HOLE ? "  " : puzzel + " "));
            }
            buf.append("\n");
        }
        return buf.toString();
    }
     
    /*
     * A standard implementation of equals checking whether 2 boards are filled 
     * in exactly the same way.
     * @return true iff this object and o are equal
     */
    @Override
    public boolean equals(Object o) {
        if (o == null || o.getClass() != getClass()) {
            return false;
        } else {
            SlidingGame other_puzzle = (SlidingGame) o;
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    if (board[col][row] != other_puzzle.board[col][row]) {
                        return false;
                    }
                }
            }
            return true;
        }
 	}

    @Override
    public boolean isSolution () {
        for( int p = 0; p < SIZE; p++) {
            if (board[p % N][p / N] != p + 1) {
                return false;
            }
        }
        return true;
    }

    @Override
    public Collection<Configuration> successors () {
        Collection<Configuration> successors = new ArrayList<Configuration>();
        try {
            successors.add(move(Direction.EAST));
        } catch (ArrayIndexOutOfBoundsException e) {}
        try {
            successors.add(move(Direction.SOUTH));
        } catch (ArrayIndexOutOfBoundsException e) {}
        try {
            successors.add(move(Direction.WEST));
        } catch (ArrayIndexOutOfBoundsException e) {}
        try {
            successors.add(move(Direction.NORTH));
        } catch (ArrayIndexOutOfBoundsException e) {}
        return successors;
    }
    
    /**
     * According to the assignment we should use:
     *      result += board[x][y] * Math.pow(31, x + N*y);
     * However, this results for even small boards in INT_MAX, so this is not very useful.
     * 
     * Giving every board a unique hash would be:
     *      result += board[x][y] * Math.pow(SIZE, x + N*y);
     * However, already with N=4 that results in INT_MAX as well.
     * 
     * The current implementation uses SIZE as base and subtracts n(n-1) from the exponent. 
     * This results in values well below INT_MAX for N up to 5 (and possibly higher).
     * Of course, it also means that different puzzles may have the same value.
     * For N>3 this is unavoidable since 16! > INT_MAX. For N <= 3  we are not too concerned
     * since the program is fast enough for small programs for us to accept this imperfectness.
     */
    @Override
    public int hashCode() {
        int result = 0;
        for (int x = 0; x < N; x++)
            for (int y = 0; y < N; y++)
                result += board[x][y] * Math.pow(SIZE, x + N*y - (N-1)*N);

        return result;
    }

    @Override
    public int compareTo(Configuration t) {
        SlidingGame tsg = (SlidingGame) t;
        return manhattan - tsg.getManhattan();
    }

}