import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

/**
 * Holds a maze representation Solves it too, if asked.
 *
 * @author geoffreytowell Created: Sept, 2019 Modified: August 12, 2021
 */
public class Maze {
	// Letters indicating state in the maze
	public static final char START = 's';
	public static final char FINISH = 'e';
	public static final char WALL = '*';
	public static final char PATH = ' ';
	public static final char USED_PATH = 'A';

	/**
	 * The internal representation of the maze
	 */
	char[][] mazeRep;

	/**
	 * The directions of allowed movement in the maze There are two set of
	 * directions
	 */
	Coordinate[] diagonal = { new Coordinate(-1, -1), new Coordinate(1, -1), new Coordinate(1, 1),
			new Coordinate(-1, 1) };

	Coordinate[] updownrl = { new Coordinate(1, 0), new Coordinate(-1, 0), new Coordinate(0, 1),
			new Coordinate(0, -1) };
	Coordinate[] moves = diagonal;

	/**
	 * Maze constructor. This takes the name of a file containing a maze and reads
	 * it into the internal represenation.
	 * 
	 * @param fileName the name of the file containing the maze
	 * @throws FileNotFoundException
	 * @throws ImproperMazeException
	 */
	public Maze(String fileName) throws FileNotFoundException, ImproperMazeException, IOException {
		// first read the file into an array list to get the dimensions of the maze
		ArrayList<String> tmaz = new ArrayList<>();
		BufferedReader br = null;
		try {
			br = new BufferedReader(new FileReader(fileName));
			int wid = -1;
			String lin;
			while ((lin = br.readLine()) != null) {
				if (wid > 0 && lin.length() != wid) {
					throw new ImproperMazeException(
							"Maze must be a rectangle current width=" + wid + " new line width=" + lin.length());
				}
				if (wid < 0)
					wid = lin.length();
				tmaz.add(lin);
			}

			// with the file read complete, fill in the internal representation
			mazeRep = new char[tmaz.size()][wid];
			for (int i = 0; i < tmaz.size(); i++) {
				String s = tmaz.get(i);
				for (int j = 0; j < s.length(); j++) {
					if (s.charAt(j) == WALL || s.charAt(j) == START || s.charAt(j) == FINISH || s.charAt(j) == PATH) {
						mazeRep[i][j] = s.charAt(j);
					} else {
						throw new ImproperMazeException("Maze contains an unknown character ||" + s.charAt(j) + "||");
					}
				}
			}
		} finally {
			if (br != null)
				br.close();
		}
	}

	/**
	 * Copy contrructor
	 * 
	 * @param oldMaze the maze to be copied
	 */
	public Maze(Maze oldMaze) {
		mazeRep = new char[oldMaze.getDim1()][oldMaze.getDim2()];
		for (int i = 0; i < getDim1(); i++) {
			for (int j = 0; j < getDim2(); j++) {
				mazeRep[i][j] = oldMaze.mazeRep[i][j];
			}
		}
		this.moves = oldMaze.moves;
	}

	/**
	 * @return a string showing the maze
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < mazeRep.length; i++) {
			for (int j = 0; j < mazeRep[i].length; j++) {
				sb.append(mazeRep[i][j]);
			}
			sb.append("\n");
		}
		return sb.toString();
	}

	/**
	 * Set a character in the maze
	 * 
	 * @param c   the character to set into the maze
	 * @param val the coordinate in which to set the character
	 */
	public void setCoordValue(Coordinate c, char val) {
		mazeRep[c.getD1()][c.getD2()] = val;
	}

	/** The dize in the first dimension of the maze */
	private int getDim1() {
		return mazeRep.length;
	}

	/** The size in the second dimension of the maze */
	private int getDim2() {
		return mazeRep[0].length;
	}

	/**
	 * Solve the maze, But do so by considering moving to the proveded location in
	 * the maze.
	 * 
	 * @param c     the location to consider for solving the maze from
	 * @param depth how many moves you have already made (not really needed)
	 * @return if the maze is solvable from the location, a solution. Otherwise null
	 */
	private Maze solve(Coordinate c, int depth) {
		System.out.println(depth + " Considering " + c);
		System.out.println(this);
		if (c.getD1() < 0 || c.getD2() < 0 || c.getD1() >= getDim1() || c.getD2() >= getDim2()) {
			System.out.println(" Off Grid");
			return null;
		}
		if (mazeRep[c.getD1()][c.getD2()] == FINISH) {
			setCoordValue(c, USED_PATH);
			System.out.println("Solved in " + depth + " steps!!!");
			return this;
		}
		if (mazeRep[c.getD1()][c.getD2()] == WALL) {
			System.out.println(" Wall");
			return null;
		}
		if (mazeRep[c.getD1()][c.getD2()] == PATH) {
			setCoordValue(c, USED_PATH);
			for (Coordinate mv : moves) {
				System.out.println("try move " + mv);
				Maze mm = (new Maze(this)).solve(new Coordinate(c, mv), depth + 1);
				if (mm != null)
					return mm;
			}
		}
		System.out.println(" No way forward");
		return null;
	}

	/**
	 * Find the location of the starting point
	 * 
	 * @return the location of the starting point (or null if there is no start)
	 */
	public Coordinate getStart() {
		for (int i = 0; i < mazeRep.length; i++)
			for (int j = 0; j < mazeRep[i].length; j++)
				if (mazeRep[i][j] == START)
					return new Coordinate(i, j);
		return null;
	}

	/**
	 * Solve the maze, or indicate that the maze cannot be solved.
	 */
	public void solve() {
		Coordinate mstart = getStart();
		if (mstart != null) {
			setCoordValue(mstart, PATH);
			Maze zz = solve(mstart, 0);
			if (zz != null) {
				System.out.println(zz);
				return;
			} else {
				return;
			}
		} else {
			System.out.println("No starting point");
			return;
		}

	}

	public static void main(String[] args) {
		String[] defargs = { "r", "maze3.txt" };
		if (args.length < 2) {
			args = defargs;
			System.out.println("Using default args: expected 2 args \"[r|d] fileName got " + args.length);
		}
		Maze m;
		try {
			m = new Maze(args[1]);
		} catch (FileNotFoundException fnf) {
			System.err.println(fnf + " " + args[0]);
			return;
		} catch (ImproperMazeException ime) {
			System.err.println(ime);
			return;
		} catch (IOException ioe) {
			System.err.println(ioe);
			return;
		}
		switch (args[0]) {
		case "r":
		case "R":
			m.moves = m.updownrl;
			break;
		case "d":
		case "D":
			m.moves = m.diagonal;
			break;
		default:
			System.err.println("the first arg must be either r or d. Got " + args[0]);
			return;
		}
		System.out.println(m);
		m.solve();
	}
}