/*
 * SquarePuzzle is a simple solitaire game.  The user attempts to 
 * rearrange the tiles to the unscrambled configuration.
 */
package puzzle;
import util.MyVector;
import java.lang.Number.*;
import java.io.*;

public class SquarePuzzle implements Serializable{
 
    public int height, width; // Dimensions of the puzzle
    public int[][] tile; // tile[i][j] indicates which tile is in
                          // position i, j.  The value 0 corresponds
                          // to an empty position (no tile). 
    public int[] location; // location[t] indicates where tile t
    // is located.  This includes the "empty tile", tile 0.
    // The coordinates [i][j] satisfy i*width+j = location[t].
    
    public String pad(String s, int newsize) {
        String rv;
        StringBuffer whitespace = new StringBuffer();
        for (int i=0; i<newsize - s.length(); i++)
            whitespace.append(' ');
        rv = whitespace.toString() + s;
        return rv;
    }

    public void randomizePosition() {
        MyVector tilesleft = new MyVector(height*width);
        for (int i=0; i<height*width; i++)
            tilesleft.add(new Integer(i));
        for (int i=0; i<height*width; i++) {
            int next_tile = ((Integer)tilesleft.randomRemove()).intValue(); 
            tile[i/width][i%width] = next_tile;
            location[next_tile] = i;
        }
    }

    public void orderPosition() {
        for (int i=0; i<height*width; i++) {
            tile[i/width][i%width] = (i+1)%(height*width);
            location[(i+1)%(height*width)] = i;
        }
    }

    public boolean isSolved() {
        for (int i=0; i<height*width; i++) 
            if (location[(i+1)%(height*width)] != i)
                return false;
        return true;
    }

    private void showPosition () {
        for (int i=0; i<height; i++) {
            for (int j=0; j<width;j++)
                if (tile[i][j] != 0)
                    System.out.print(pad(String.valueOf(tile[i][j]),3));
                else
                    System.out.print("   ");
            System.out.println("");
        }
        System.out.println("");
    }
    
    /*
     * Given a value, move the tile with that value into the
     * adjacent empty cell, if there is one, and return true.
     * If the empty cell is not adjacent, return false.
     */
    private boolean slidePiece(int value) {
        int loc1 = location[value];
        int loc2 = location[0];
        int i1 = loc1/width, i2=loc2/width;
        int j1 = loc1%width, j2=loc2%width;
        if ((((i1-i2==1)||(i2-i1==1))&&(j2-j1==0))
            ||(((j1-j2==1)||(j2-j1==1))&&(i2-i1==0))) {
            location[0]=loc1;
            location[value]=loc2;
            tile[i1][j1]=0;
            tile[i2][j2]=value;
            return true;
        }
        else
            return false;
    }

    public boolean slidePiece(int i, int j) {
        if (!((0<=i)&&(i<height)&&(0<=j)&&(j<height)))
            return false;
        return slidePiece(tile[i][j]);
    }

    private void inputMove() {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String input;
        int move;
        char key;
        try { 
            System.out.print("Please enter a move (? for help): ");
            input = in.readLine();
            key = input.charAt(0);
            if (key == '?' || key == '/') 
                System.out.println("Instructions: Type a number between 1 and 15 to slide the corresponding tile.\nOnly tiles adjacent to the empty space may be moved.\nYou may also type one of the following directives:\n  R : Randomize the tile arrangement.\n  O : Order the tiles into the solved configuration.\n  Q : Quit the game.");
            else if (key == 'r' || key=='R') {
                randomizePosition();
                showPosition();
            }
            else if (key == 'o' || key=='O') {
                orderPosition();
                showPosition();
            }
            else if (key =='q' || key=='Q') {
                System.out.println("Thanks for playing!");
                System.exit(0);
            }
            else {
                move = Integer.parseInt(input);
                slidePiece(move);
                showPosition();
                if (isSolved())
                    System.out.println("Congratulations!  You've solved the puzzle!");
            }
        } catch (Exception e) {
            System.out.println("Exception handling input.");
        }        
    }

    public SquarePuzzle(int h, int w) {
        height = h; width = w;
        tile = new int[height][];
        for (int i=0; i<height; i++) 
            tile[i] = new int[width];
        location = new int[height*width];
        randomizePosition();
    }
     
    public static void main(String[] args) {
        System.out.println("Welcome to SquarePuzzle v1.1");
        SquarePuzzle puzz = new SquarePuzzle(4,4);
        puzz.showPosition();
        while (true) {
            puzz.inputMove();
        }
    }
}