#!/usr/bin/env python3
"""
maze.py
This program solves a maze recursively. See any of the .txt files in
this directory for an example of how to code a maze problem:
1. @ sign represents current position of the solver and starts in 
   the maze.
2. Walls of the maze are presented by "0" characters
3. The exit of the maze is indicated by an opening in the bounding
   walls of the maze.
4. Empty spaces where the solver may go are represented by spaces.
"""

__author__ = "Richard White"
__version__ = "2026-02-10, based on work by Miller, Ranum, Yasinovskyy"

import os
import time
import sys

"""
These constants identify the symbols that re used
to indicate the state of the various cells in the
maze.
"""
PART_OF_PATH = '*'  # Will indicate final solution
TRIED = '.'         # Bread crumbs used by the solver
OBSTACLE = '0'      # Walls, etc.
DEAD_END = '-'      # Bread crumb used by the solver
WAIT = 0.2          # Delay to make fast solutions visible

def import_maze(filename):
    """Brings the text file version of the maze
    into the program. While importing, identifies
    the location of the maze solver `@` and 
    returns that value as `location`, a tuple.
    """
    infile = open(filename,'r')
    maze = []
    row = 0
    for line in infile:
        col = 0 
        row_list = []
        for ch in line.rstrip('\n'):
            if ch == '@':
                # Save the location
                rowLoc = row
                colLoc = col
                row_list.append(' ') # Don't actually place 
                                     # solver in lists
            else:
                row_list.append(ch)  # Walls
            col += 1
        maze.append(row_list)
        row += 1
    return maze, (rowLoc, colLoc)

def display(maze, location):
    """Displays the current state of the maze, including:
    @ - the location of the walker
    0 - an occupied space (typically a wall)
    * - a space that is part of the final solution
    . - a space that is has been tried
    _ - a dead end
    """
    os.system('clear')
    for row in range(len(maze)):
        for col in range(len(maze[0])):
            # This identifies the current location of the
            # solver. Note that it sometimes places the
            # walker "in" a wall, but that just indicates
            # that we're checking that location.
            if location[0] == row and location[1] == col:
                print('@',end='')
            else:
                print(maze[row][col],end='')
        print()
    time.sleep(WAIT)

def searchFrom(maze, location):
    """Begin searching recursively from this location to see
    if we can find a path out. `loc` is a tuple that contains
    the [row][col] of the current location.
    This boolean method returns False if the parameter `location`
    definitely *doesn't* lead out, and returns True if it definitely
    *does*.
    """

    # display the maze state on screen. Slows down the recursion,
    # but offers insight into how the recursive searching works.
    display(maze,location)

    # Pause for input so we can analyze situation
    input() 

    # What type of location are we at? 
    loc = maze[location[0]][location[1]]

    # First identify base cases.
    # 1. If this location is a wall ("obstacle"), we can't 
    #    move on from here.
    if loc == OBSTACLE:
        return False

    # 2. If this location has been tried, we've been here
    #    before and it hasn't worked out.
    if loc == TRIED or loc == DEAD_END:
        return False

    # 3. If we've reached a border of the maze, we found
    #    an exit! Mark it as being part of the path and 
    #    return True
    if location[0] == 0 or location[0] == len(maze) - 1 or \
       location[1] == 0 or location[1] == len(maze[0]) - 1:
        maze[location[0]][location[1]] = PART_OF_PATH
        return True

    # If we haven't run into one of these situations, we'll
    # mark where we are now...
    maze[location[0]][location[1]] = TRIED

    # ...  and recurse on to the next position.
    # Set up a variable `found` that will have a value of True
    # or False, depending on what the recursive call returns.
    found = searchFrom(maze, (location[0]-1, location[1])) or \
            searchFrom(maze, (location[0]+1, location[1])) or \
            searchFrom(maze, (location[0], location[1]+1)) or \
            searchFrom(maze, (location[0], location[1]-1))

    # After returning from this call, we have a value of True or False, 
    # depending on what we whether this part of a successful path
    # or not. Mark the location that we moved to at this point
    # with the appropriate symbol.
    if found:
        maze[location[0]][location[1]] = PART_OF_PATH
    else:
        maze[location[0]][location[1]] = DEAD_END

    # ... and return to previous location to either continue
    # identifying successful parts of the path, or continue 
    # searching if we haven't yet found a way out.
    return found


def main(argv):
    """
    The `argv` parameter is a list made up of optional parameters
    listed when this program is run by python. For example, the 
    instruction 
        python maze.py maze2.txt
    will call python with the `argv` list = ['maze.py', 'maze2.txt']
    with those items at indices                 0            1
    
    So, we can run th maze program from the command line AND specify
    which of the maze files we want to execute without having to change
    the code in our program.
    """

    maze, location = import_maze(argv[1]) 
    display(maze, location)

    # Initiate the recursive search! 
    searchFrom(maze, location)

    # Display final version of solve maze
    print("Done!")
    display(maze, location)


if __name__ == "__main__":
    main(sys.argv)  # sys.argv gets arguments, 0 filename, 1 comes after