/*
  This file contains the state space definition for the sliding-tiles
  puzzle.

  These are the only problem-specific (i.e., specific to the
  sliding-tile puzzle) parts of the code; everything else is generic
  and can be used without change for other search problems.
*/

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class PuzzleStateSpace implements StateSpace {
    /*
      We define static variables for the puzzle size so that they can
      be changed easily. For the 15-puzzle, WIDTH should set to be 4
      to have a 4x4 grid.
    */

    public static boolean USE_INPUT_FORMAT = false;

    private static int WIDTH = 4;
    private static int SIZE = WIDTH * WIDTH;

    /*
      For most parts of the code, it's useful to simply number all the
      cells sequentially, so for example in the 15-puzzle, the first
      row has indices 0...3, the second one 4...7, and so on. We call
      such a number a "cell index".

      At some points it is useful to convert back and forth between
      cell indices and 2-dimensional row/column coordinates. For
      example, in the 15-puzzle, coordinate (1, 3) means row 1
      (counting from 0) and column 3 (counting from 0) and has cell
      index 7 = 1 * 4 + 3.

      We give some simple conversion functions here.
    */

    private static int cellIndexToRow(int cellIndex) {
        return cellIndex / WIDTH;
    }

    private static int cellIndexToColumn(int cellIndex) {
        return cellIndex % WIDTH;
    }

    private static int coordsToCellIndex(int row, int column) {
        return row * WIDTH + column;
    }

    /*
      We make puzzle states and actions private since the search code
      cannot and should not look into the state. Since they are only
      accessed from this class, we can make them plain old datatypes
      without violating encapsulation.
    */

    private static class PuzzleState implements State {
        /*
          A state is represented as a fixed-size array, indexed by the
          cell indices (see above).
        */
        int cellContents[];

        public PuzzleState(int[] cellContents) {
            this.cellContents = cellContents;
        }

        public String toString() {
            if (USE_INPUT_FORMAT) {
                String result = "";
                for (int i = 0; i < SIZE; i++) {
                    if (i != 0)
                        result += " ";
                    result += cellContents[i];
                }
                return result;
            } else {
                String result = "\n";
                String dashLine = "-";
                for (int column = 0; column < WIDTH; column++)
                    dashLine += "-----";
                dashLine += "\n";
                result += dashLine;
                for (int row = 0; row < WIDTH; row++) {
                    for (int column = 0; column < WIDTH; column++) {
                        int index = coordsToCellIndex(row, column);
                        int tile = cellContents[index];
                        result += "| ";
                        if (tile == 0)
                            result += "  ";
                        else
                            result += String.format("%2d", tile);
                        result += " ";
                    }
                    result += "|\n";
                    result += dashLine;
                }
                return result;
            }
        }
    }

    private static class PuzzleAction implements Action {
        /*
          We have four different actions: left, right, up, down. For
          convenience in other parts of the code, each action stores
          three attributes: its name (to show to the user) and its
          deltaRow and deltaColumn values, i.e., how it changes the
          row and column of the blank tile. For example, going up has
          a deltaRow value of -1 and and a deltaColumn value of 0.
        */

        public String name;
        public int deltaRow;
        public int deltaColumn;

        public PuzzleAction(String name, int deltaRow, int deltaColumn) {
            this.name = name;
            this.deltaRow = deltaRow;
            this.deltaColumn = deltaColumn;
        }

        public String toString() {
            return name;
        }
    }

    /*
      A state space instance must store the initial state, and it also
      stores the four possible actions.
    */
    private PuzzleState initState;
    private PuzzleAction[] actions;

    public PuzzleStateSpace() {
        /*
          This method generates a puzzle state space where the initial
          state equals the goal state.
        */
        this(new PuzzleState(new int[] {
                    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}));
    }

    private PuzzleStateSpace(PuzzleState initState) {
        this.initState = initState;
        System.out.println("Instantiating sliding-tile puzzle instance for "
                           + WIDTH + "x" + WIDTH + " puzzle...");

        actions = new PuzzleAction[] {
            new PuzzleAction("up", -1, 0),
            new PuzzleAction("down", +1, 0),
            new PuzzleAction("left", 0, -1),
            new PuzzleAction("right", 0, +1)
        };
    }

    /*
      The following four methods define the interface of state spaces
      used by the search code.

      We use the method names "init", "isGoal", "succ" and "cost" to
      stay as close as possible to the names in the lecture slides.
      Without this constraint, it would be better to use more
      self-explanatory names like "getSuccessorStates" instead of
      "succ".

      All methods are const because the state space itself never
      changes.
    */

    public State init() {
        // Just return the initial state that we stored.
        return initState;
    }

    public boolean isGoal(State s_) {
        PuzzleState s = (PuzzleState) s_;

        /*
          The (only) goal state of the 15-puzzle is the one where the
          cells, in index order, have contents 1, 2, 3, ..., 15, 0 (=
          blank). Similarly for the n-by-n case.

          We only test the tiles, not the blank. If the tiles are all
          correct, then the blank is necessarily also correct.
        */

        for (int i = 0; i < SIZE - 1; i++)
            if (s.cellContents[i] != i + 1)
                return false;

        return true;
    }

    public ArrayList<ActionStatePair> succ(State s_) {
        PuzzleState s = (PuzzleState) s_;

        ArrayList<ActionStatePair> result = new ArrayList<ActionStatePair>();

        // Determine the cell index of the blank.
        int blankIndex = 0;
        while (s.cellContents[blankIndex] != 0)
            blankIndex++;

        int blankRow = cellIndexToRow(blankIndex);
        int blankColumn = cellIndexToColumn(blankIndex);

        for (PuzzleAction action : actions) {
            int newBlankRow = blankRow + action.deltaRow;
            int newBlankColumn = blankColumn + action.deltaColumn;
            // Test that the action is valid, i.e., the blank remains in bounds:
            if (newBlankRow >= 0 && newBlankRow < WIDTH &&
                newBlankColumn >= 0 && newBlankColumn < WIDTH) {
                int newBlankIndex = coordsToCellIndex(newBlankRow, newBlankColumn);
                // Copy the contents of the old states, then update the
                // blank and the moved tile.
                int[] newCellContents = Arrays.copyOf(s.cellContents, SIZE);
                newCellContents[newBlankIndex] = 0;
                newCellContents[blankIndex] = s.cellContents[newBlankIndex];

                PuzzleState succState = new PuzzleState(newCellContents);
                result.add(new ActionStatePair(action, succState));
            }
        }

        return result;
    }

    public int cost(Action a) {
        return 1;
    }

    /*
      The following method instantiates the state space by reading the
      problem description from a file specified on the command line.
      The puzzle state space is a *parameterized* one (i.e., the
      initial state depends on arguments specified by the user of the
      code).
    */
    public static StateSpace buildFromCmdline(ArrayList<String> args) {
        if (args.size() != 1) {
            Errors.usageError("need one input file argument");
        }

        String filename = args.get(0);
        System.out.println("Reading input from file " + filename + "...");
        Scanner scanner;
        try {
            scanner = new Scanner(new File(filename));
        } catch (FileNotFoundException e) {
            Errors.fileError("input file not found: " + filename);
            scanner = new Scanner(""); // unreachable; silences compiler
        }

        int[] cellContents = new int[SIZE];
        boolean[] tileUsed = new boolean[SIZE];

        for (int i = 0; i < SIZE; i++) {
            int tile = scanner.nextInt();
            if (tile < 0 || tile > SIZE)
                Errors.fileError("invalid tile number");
            if (tileUsed[tile])
                Errors.fileError("duplicate tile");
            cellContents[i] = tile;
            tileUsed[tile] = true;
        }

        PuzzleState init = new PuzzleState(cellContents);
        return new PuzzleStateSpace(init);
    }
}