# A node within the space to search
class Node:
    # Initialize values in constructor
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent

    # Determine if this node is the same as another
    # (If we don't do this, python will count two different objects as
    # different nodes even if they share the same location; this breaks our
    # checks for whether a node has already been visited)
    def __eq__(self, other):
        if other.value is not None and len(other.value) == 2:
            return other.value[0] == self.value[0] and other.value[1] == self.value[1]


def getNeighbors(location, grid):
    # Get row count
    rows = len(grid)

    # If there are no rows, return an empty list
    if rows < 1:
        return []

    # Get the columns count
    cols = len(grid[0])

    # If there are no columns, return an empty list
    if cols < 1:
        return []

    # Make sure the position is valid and within the provided grid
    if len(location) != 2\
            or location[0] < 0\
            or location[0] >= rows\
            or location[1] < 0\
            or location[1] >= cols:
        return []

    # Define neighbors list
    neighbors = []

    # Add up neighbor
    if location[0] > 0 and grid[location[0] - 1][location[1]] != 1:
        neighbors.append([location[0] - 1, location[1]])
    # Add down neighbor
    if location[0] < rows - 1 and grid[location[0] + 1][location[1]] != 1:
        neighbors.append([location[0] + 1, location[1]])
    # Add left neighbor
    if location[1] > 0 and grid[location[0]][location[1] - 1] != 1:
        neighbors.append([location[0], location[1] - 1])
    # Add right neighbor
    if location[1] < cols - 1 and grid[location[0]][location[1] + 1] != 1:
        neighbors.append([location[0], location[1] + 1])

    # Return neighbors list
    return neighbors


# Expand a node into its neighbors, put them into the frontier, and mark the
# node as visited
def expandNode(node, grid, closed_list, open_list):
    # Make sure this node isn't visited or queued to be visited already
    if node in closed_list:
        return

    # Add this node to the visited list
    closed_list.append(node)

    if node in open_list:
        return

    # Get possible neighbors for this node's position
    for neighbor in getNeighbors(node.value, grid):
        # Make sure the neighbor isn't already visited or scheduled to be visited
        for n in closed_list:
            if n.value == neighbor:
                continue
        for n in open_list:
            if n.value == neighbor:
                continue

        # Mark accessible neighbors as to-be-visited
        open_list.append(Node(neighbor, node))


# The grid values must be separated by spaces, e.g.
# 1 1 1 1 1
# 1 0 0 0 1
# 1 0 0 0 1
# 1 1 1 1 1
# Returns a 2D list of 1s and 0s
def readGrid(filename):
    # Initialize grid to empty list
    grid = []

    # Open the file
    with open(filename) as f:
        # Read each line of the file
        for line in f.readlines():
            # Split each line into its individual values and add them to the
            # grid
            grid.append([int(x) for x in line.split()])

    # No need to close file using `with` syntax

    # Return the grid
    return grid


# Writes a 2D list of 1s and 0s with spaces in between each character
# 1 1 1 1 1
# 1 0 0 0 1
# 1 0 0 0 1
# 1 1 1 1 1
def outputGrid(filename_str, grid, start, goal, path):
    # Open file
    with open(filename_str, 'w') as f:
        print(
            'Goal: ' + str(goal[0]) + ', ' + str(goal[1]) + ' | Grid size: ' + str(len(grid)) + 'x' + str(len(grid[0])))

        # Mark the start and goal points
        grid[start[0]][start[1]] = 'S'
        grid[goal[0]][goal[1]] = 'G'

        # Mark intermediate points with *
        for i, p in enumerate(path):
            if 0 < i < len(path) - 1:
                grid[p[0]][p[1]] = '*'

        # Write the grid to a file
        for r, row in enumerate(grid):
            for c, col in enumerate(row):
                # Don't add a ' ' at the end of a line
                if c < len(row) - 1:
                    f.write(str(col) + ' ')
                else:
                    f.write(str(col))

            # Don't add a '\n' after the last line
            if r < len(grid) - 1:
                f.write("\n")


def setPath(current, path):
    # Keep track of current looping node
    node = current

    # Loop through parents to beginning
    while node is not None:
        # Add this node to the path
        path.append(node.value)

        # Assign current node to parent
        node = node.parent

    # Flip the path around so the first element is the beginning
    path.reverse()


# Perform a search using breadth-first if `dfs` is false, or depth-first if `dfs` is True
def uninformedSearch(grid, start, goal, dfs=False):
    # Initialize search
    open_list = [Node(start, None)]
    closed_list = []

    # Loop until we reach the goal
    while len(open_list) > 0:
        # Pull new node from open_list
        if dfs:
            # DFS is LIFO so we use `pop()` to remove last element
            current = open_list.pop()
        else:
            # BFS is FIFO so we use `pop(0)` to remove first element
            current = open_list.pop(0)

        # Check if we're at the goal position
        if current.value == goal:
            # Create path
            path = []
            setPath(current, path)

            # Return path
            return path

        # Add traversable neighbors to `open_list` and current node to
        # `closed_list`
        expandNode(current, grid, closed_list, open_list)

    # No path was found!
    return []


# Determine which algorithm to use
getting_input = True
algo_type = None
while getting_input:
    algo_type = input('Please enter the algorithm type (DFS/BFS): ')
    if algo_type == 'DFS':
        algo_type = True
    elif algo_type == 'BFS':
        algo_type = False
    else:
        print('Please enter \"DFS\" or \"BFS\"')
        continue

    getting_input = False

start = [1, 1]
goal = [5, 8]

# Read the grid in, perform the search, and output the path
grid = readGrid('maze_in.txt')
print(grid)
solved_path = uninformedSearch(grid, start, goal, algo_type)
outputGrid("maze_out.txt", grid, start, goal, solved_path)