import random
import time

############################################################
# dictionary exercises (with environment diagrams)
############################################################


classes = [
    {
        "M": ("lec", 1, "objects"),
        "W": ("lec", 2, "looping"),
        "F": ("rec", "f-strings"),
    },
    {
        "M": ("lec", 3, "lists"),
        "W": ("lec", 4, "simulation"),
        "F": ("rec", "diagrams"),
    }
]


# EXERCISE:

# Why does the following code throw an error? Rewrite the code
# to accomplish the intended change.

# rec_friday = classes[1]["F"]
# rec_friday[1] = "dictionaries"


# EXERCISE:

# Draw an environment diagram depicting what happens when the previous
# code runs.


########################################


# EXERCISE:

# Write code to extract the content of all of the lectures.


############################################################
# tracing through bfs algorithm
############################################################


def neighbors(graph, node):
    return graph.get(node, [])


def bfs(graph, start, goal):
    if start == goal:
        return [start]

    current_frontier = [[start]]
    next_frontier = []
    visited = {start}

    while len(current_frontier) > 0:
        for path in current_frontier:
            node = path[-1]
            for next_node in neighbors(graph, node):
                if next_node in visited:
                    continue
                visited.add(next_node)
                new_path = path + [next_node]
                if next_node == goal:
                    return new_path
                next_frontier.append(new_path)
        # print(
        #     f" Current Frontier: {current_frontier}"
        #     f"\n Next Frontier: {next_frontier}"
        #     f"\n Visited: {visited}"
        #     "\n")

        current_frontier, next_frontier = next_frontier, []

    return None


# EXERCISE:

# Given the following grid, write out what the graph would be.
# Then, let's say the start is 'A' and the goal is 'D'.
# Write out the contents of current_frontier, next_frontier, and visited
# at every iteration of the while loop in the reference BFS code above.


grid = '''
-------
|A|█|B|
-------
|C|█|D|
-------
|E|F|G|
-------
'''


############################################################
# using bfs to solve a maze
############################################################


def make_grid():
    return [
        list("███████████████"),
        list("█    █        █"),
        list("█ ███ █ ███ ███"),
        list("█   █   █     █"),
        list("███ █████ ███ █"),
        list("█     █   █   █"),
        list("█ ███ █ ███ ███"),
        list("█   █   █     █"),
        list("█ ███ ███ ███ █"),
        list("█       █     █"),
        list("███████████████")
    ]


def print_grid(grid):
    for row in grid:
        print("".join(row))
    print()


def place_endpoint(grid, symbol):
    """
    Randomly generate endpoints for the BFS algorithm given a grid.
    A valid endpoint is any point on the grid that isn't a wall.
    Designate this endpoint on the grid as "S" or "G" depending on
    whether it's the start or the goal.

    Parameters:
        grid (list): A list of lists of strings. Each list of strings
            represents a row, and each string is either ' ' (empty) or
            █ (a wall).
        symbol (string): Either "S" or "G" depending on if the endpoint
            is meant to be the start or the goal.

    Return the coordinates of the endpoint as a tuple.
    """

    # TO-DO:
    # Randomly generate a valid endpoint. This point cannot be a wall
    # and needs to lie within the grid.

    # random documentation: https://docs.python.org/3/library/random.html

    # Write your implementation below:


########################################


def build_neighbors(cell, rows, cols, grid):
    x, y = cell
    neighbors = []
    for step_x, step_y in [(1,0),(-1,0),(0,1),(0,-1)]:
        nx, ny = x + step_x, y + step_y
        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] in [" ", "S", "G"]:
            neighbors.append((nx, ny))

    return neighbors


def build_graph(grid):
    rows = len(grid)
    cols = len(grid[0])
    graph = {}
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] in [" ", "S", "G"]:
                graph[(i,j)] = build_neighbors((i,j), rows, cols, grid)
    return graph


def solve_maze(grid, start, goal):

    graph = build_graph(grid)

    if start == goal:
        return [start]

    current_frontier = [[start]]
    next_frontier = []
    visited = {start}

    while len(current_frontier) > 0:

        for path in current_frontier:
            node = path[-1]

            for next_node in neighbors(graph, node):
                if next_node in visited:
                    continue
                visited.add(next_node)

                x, y = next_node
                if grid[x][y] == " ":
                    grid[x][y] = "."

                new_path = path + [next_node]
                if next_node == goal:
                    return new_path
                next_frontier.append(new_path)

        print_grid(grid)
        time.sleep(1)

        current_frontier, next_frontier = next_frontier, []

    return None


def mark_path(grid, path):
    if path:
        for x, y in path:
            if grid[x][y] not in ["S", "G"]:
                grid[x][y] = "x"


########################################


grid = make_grid()
start = place_endpoint(grid, "S")
goal = place_endpoint(grid, "G")
graph = build_graph(grid)
path = solve_maze(grid, start, goal)

# mark_path(grid, path)
# print("Final path:")
# print_grid(grid)


# EXERCISE

# When the following code is run, there appear to be two
# paths that reach the goal at the same time. Why does the
# function return one path over the other.

# grid = make_grid()
# grid[1][9] = "S"
# grid[7][1] = "G"
# path = solve_maze(grid, start=(1, 9), goal=(7, 1))
# mark_path(grid, path)
# print("Final path:")
# print_grid(grid)