# Install dependencies:
# pip install (none; uses Python standard library)
#
# Reactive agent chooses a nearby unvisited cell using current perception.
# Deliberative agent searches for a complete path using A*.

from heapq import heappush, heappop

GRID = [
    list("S......."),
    list("#..#...."),
    list("..##.#.."),
    list(".#...#.."),
    list("...#...G"),
]
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def find_position(symbol):
    for r, row in enumerate(GRID):
        for c, value in enumerate(row):
            if value == symbol:
                return r, c
    return None


def get_neighbors(position):
    r, c = position
    result = []
    for dr, dc in DIRECTIONS:
        nr, nc = r + dr, c + dc
        if (0 <= nr < len(GRID) and 0 <= nc < len(GRID[0])
                and GRID[nr][nc] != "#"):
            result.append((nr, nc))
    return result


def reactive_agent():
    """Make a local choice; it does not plan the full route."""
    current, goal = find_position("S"), find_position("G")
    path, visited = [current], {current}
    while current != goal:
        choices = [p for p in get_neighbors(current) if p not in visited]
        if not choices:
            print("Reactive agent is stuck!")
            return path
        current = min(choices, key=lambda p:
                      abs(p[0] - goal[0]) + abs(p[1] - goal[1]))
        path.append(current)
        visited.add(current)
    return path


def deliberative_agent():
    """Use A* to plan a complete route before taking action."""
    start, goal = find_position("S"), find_position("G")

    def heuristic(p):
        return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

    open_list = []
    heappush(open_list, (heuristic(start), 0, start))
    came_from, cost = {start: None}, {start: 0}
    while open_list:
        _, current_cost, current = heappop(open_list)
        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = came_from[current]
            return list(reversed(path))
        for neighbor in get_neighbors(current):
            new_cost = current_cost + 1
            if new_cost < cost.get(neighbor, float("inf")):
                cost[neighbor] = new_cost
                came_from[neighbor] = current
                heappush(open_list, (new_cost + heuristic(neighbor),
                                     new_cost, neighbor))
    return []


def display_path(path, title):
    display = [row[:] for row in GRID]
    for r, c in path:
        if display[r][c] == ".":
            display[r][c] = "*"
    print("\n" + title)
    print("-" * 35)
    for row in display:
        print(" ".join(row))
    print("Path:", path)
    print("Number of steps:", max(0, len(path) - 1))


if __name__ == "__main__":
    print("REACTIVE vs DELIBERATIVE AGENT")
    reactive_path = reactive_agent()
    planned_path = deliberative_agent()
    display_path(reactive_path, "Reactive Agent")
    display_path(planned_path, "Deliberative Agent (A*)")
    print("\nDifference:")
    print("Reactive agent: acts from the current situation.")
    print("Deliberative agent: searches a complete path toward the goal.")