# Approach
The basic approach to actually generating and solving the maze is straightforward - treat the rectangular
grid as a connected, undirected graph in which the vertices represent the "cells" of the maze, and the
edges represent the "walls" of the maze.
The maze is therefore represented in two distinct ways - one as a normal matrix with rectangular cells for the
purposes of rendering on the screen, and conceptually as a graph upon which we can then apply the usual graph
algorithms - BFS, DFS, Prim's et al.
The main idea to get the "perfect maze" is to simply generate a Spanning Tree for the maze. This ensures that
every cell in the maze is reachable from every other cell of the same maze, as well as ensuring that a unique
path exists between a unique pair of cells.
Solving the maze then simply entails implementing variations of the quintessential graph algorithms - DFS and BFS
to solve for the various desired configurations.
The main task/challenge is to actually render the maze on the terminal screen itself. If the task were to simply
solve the maze as we generate it, it would have been much simpler to simply use a recursive backtracking algorithm
(such as randomised DFS, for instance). However, I decided against that since I wanted some level of dynamic
capabilities - a crude form of animation as well as the freedom to render the cells in no particular order. This,
of course, brings about its own set of limitations, which I feel are justifiable enough for the scope of this project.
More specific design details follow in the individual sections.
## Generating the Maze
Generating the maze has three essential steps:
1. Reading in the dimensions from the user and generating a two dimensional matrix of conceptual "cells".
Each cell will basically hold metadata about the conceptual maze - coordinates for rendering, as well as
an id so that it can be mapped to the corresponding conceptual graph (see point 2).
2. Mapping the cells and the walls between the cells to a corresponding connected, undirected graph's
vertices and edges.
3. Generating a Spanning Tree using Prim's Algorithm (a randomised version to ensure variety in the shapes of the
generated mazes between runs). Since this maze is essentially a tree, simple DFS would have sufficed, but I find
Prim's to be a much simpler algorithm.
4. Finally, rendering the Spanning Tree state onto the screen using ANSI escape codes (see the next subsection for
more details on this).
### ANSI Escape Codes and rendering the Maze
As mentioned before, the basic approach to rendering the maze (in any state) is to use ANSI escape codes (see the
[#References] section below. This means that the code should essentially work for any terminal that has basic VT100
(or better) support. Note that this also means that it will not work on Windows' default terminals. It should work
on a terminal emulator like Cygwin/ConEmu/Cmder/Git Bash etc. though.
Note also that due to the variety of available dimensions of terminal screen configurations, I have decided to allow
only for a maximum of 80x24 (80 columns and 24 rows), which should work on almost any terminal configuration.
That also means that we allow only for a (hardcoded) limit of a 25 x 25 maze (even though on my MBP at high resolution,
at least 116x65 seems to be supported). Given enough time experimenting witn scrolling options using ANSI Escape Codes,
this limit can easily be rescinded.
We use ANSI Escape Codes specifically for the following purposes:
1. Clearing the terminal and setting the cursor at the top-left of the screen.
2. Locating a particular (LINE, COLUMN) location on the screen for rendering a conceptual cell as part of a maze.
To this end, each maze cell is considered to consist of the following "sprites":
`+---+` for the North and South walls, and `|` for the East and West walls
with the net effect that a cell (before modification) would look so:
+---+
| |
+---+
and the entire maze is built up using this basic structure.
3. Given the Spanning Tree (ST) state, a simple DFS will provide the path from any particular vertex to any other
vertex in the ST, and this path will be unique. The rendering of a "solved" state of the maze simply involves
rendering only the cells/vertices in this path by locating the position of the cell on the actual terminal screen
(using the coordinates stored in the cell metadata), and rendering the appropriate character.
The character to be displayed within a cell is determined from the direction of the movement. For a starting cell,
it is 's', for a terminal cell it is 't', and for an intermediate cell in the path, the proper character, '>', 'v',
'<', or '^' is chosen by simply determing the relative direction changes between two consecutive cells along the
path.
For instance, Suppose we have a path like so: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1). The translated path for this
would be: s v v t. This is because we can only move one step in the horizontal or vertical direction at a time.
Also note that the coordinate system used here is basically the same as that for SVG et al - the origin point is the
top-left of the screen, and it grows downwards in either direction. For the ANSI Escape Codes in particular, an (x, y)
coordinate represents LINE x, COLUMN y from the origin.
## Solving the Maze
To solve the maze in this context means finding the path from the top-left cell to the bottom-right cell of the maze.
Given the Spanning Tree (which now represents the conceptual maze), we simply perform DFS from cell 0 (proper coordinates
(0, 0) all the way down to cell height x width - 1 (proper coordinates (height-1, width-1)). As noted before, this path is
unique. The starting point is marked with 's' and the ending point is marked with 't', and the overall path is rendered as
explained in the previous section.
## Solving for the Longest Path
For the longest path problem, we use the common "trick" of finding the longest path between two vertices of a tree - using
two BFSes.
The first BFS (starting from any vertex is fine, but we can always start from cell 0 for consistency) will ensure that the
last vertex in the returned path is one end of *a* longest path (there can be many more, of course). Then, if we perform
another BFS from this vertex, we will get another longest path (which maybe the same as before) which starts with this
vertex.
As before, render the whole path using ANSI Escape codes.
## Solving for the Most Convoluted Path
**OUT OF SCOPE**. (One approach that is feasible is to find the path between each pair of vertices, and calculate "complexity" by, say, calculating how
many direction changes (consecutively) are present in the path, and then rendering the path with the maximum value. If the grid size is
`N x M`, then there are N * M vertices, and since we pick 2 of them as the start and end points at a time, there should be a maximum of
NMC2 (NxM choose 2) iterations. For the maximum grid size of 25 x 25, that would be around 19500 iterations, which seems reasonable enough).
Scoping this out for this release due to time constraints.
## References
Some references that I found useful dealing with
* [http://www.lihaoyi.com/post/BuildyourownCommandLinewithANSIescapecodes.html](http://www.lihaoyi.com/post/BuildyourownCommandLinewithANSIescapecodes.html)
* [https://en.wikipedia.org/wiki/ANSI_escape_code](https://en.wikipedia.org/wiki/ANSI_escape_code)