import java.util.*;
import java.io.*;

/**
 * This class extends the Node class to solve the 15 puzzle.
 * Class state is stored in a 2-dimensional array.
 */
class FifteensNode extends Node {
    /*
     * This variable describes the state. Should be a 4x4 array of values 0,
     * ..., 15
     */
    private int[][] field;

    /**
     * Helper array.
     */
    private static int[] dx = { -1, 1, 0, 0 };

    /**
     * Helper array.
     */
    private static int[] dy = { 0, 0, -1, 1 };

    /**
     * Gets the Manhattan distance between the given two cells of the 4x4 board.
     */
    private static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    /**
     * Parses the state from the specified text file and creates a node
     * containing that state.
     */
    public static FifteensNode parseFromFile(String filename)
            throws IOException {
        Scanner scanner = new Scanner(new File(filename));
        int[][] field = new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                field[i][j] = scanner.nextInt();
            }
        }

        // Create a node with "null" parent, 0 g-value, and the parsed field
        return new FifteensNode(null, 0, field);
    }

    /**
     * Simple constructor.
     * 
     * @param parent -
     *            the parent node.
     * @param gValue -
     *            the g-value.
     * @param field -
     *            the field configuration. Should be a 4x4 array of integers 0,
     *            ..., 15.
     */
    public FifteensNode(FifteensNode parent, double gValue, int[][] field) {
        super(parent, gValue);
        this.field = (int[][]) field.clone();
    }

    /**
     * Returns "true" if the state of this node is the final (goal) state of the
     * puzzle.
     */
    public boolean isGoal() {
        // TODO: your code here
        /*
         * Implementation notes:
         * Return true if "int[][] field" contains the goal configuration, 
         * that is, if the tiles are ordered correctly.
         */
    }

    /**
     * The heuristic for the state of this node is the sum of Manhattan
     * distances from each tile's position to that tile's final position.
     */
    public double evaluateHeuristic() {
        // TODO: your code here
        /*
         * Implementation notes:
         * Return your heuristic value here, based on the state configuration
         * stored in "int[][] field".
         * You may find the method "getManhattanDistance" useful.
         */
    }

    /**
     * Generates children by trying all 4 possible moves of the empty cell.
     */
    public List<FifteensNode> generateChildren() {
        // TODO: your code here
        /*
         * Implementation notes:
         * Return the list of all successor states for this state.
         * 
         * Some helper code:
         * 1. Create an empty list: 
         * List<FifteensNode> children = new ArrayList<FifteensNode>();
         * 2. Generate all possible successor configurations of the "field" array
         * 3.     For each successor field, let's call it "childField" and 
         *        successor g-value childG, call
         *        children.add(new FifteensNode(this, childG, childField));
         * 4. Return the "children" list. 
         */
    }

    /**
     * Returns the String representation of this node's state.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        // sb.append("g+h = " + evaluate() + ":\n");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                sb.append(" ");

                // could use a standard formatting function here
                if (field[i][j] == 0) {
                    sb.append("  ");
                    continue;
                }
                if (field[i][j] < 10) {
                    sb.append(" ");
                }
                sb.append("" + field[i][j]);
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    /**
     * Prints out all the steps of the puzzle solution and the total number of
     * moves in the end.
     */
    public int printSolution() {
        int k = super.printSolution();
        System.out.println("Total # of moves: " + (k - 1));
        return k;
    }
}