# Install dependencies:
# pip install (none; uses Python standard library)
#
# Hybrid agent: A* is the deliberative planner; perceive/act is the
# agent loop, with a simple safety check before each move.

import heapq

GRID = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
]
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_list = [(heuristic(start, goal), 0, start, [start])]
    best_cost = {start: 0}
    while open_list:
        _, current_cost, current, path = heapq.heappop(open_list)
        if current == goal:
            return path
        if current_cost != best_cost[current]:
            continue
        for dr, dc in MOVES:
            nr, nc = current[0] + dr, current[1] + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 1:
                continue
            neighbor = (nr, nc)
            new_cost = current_cost + 1
            if new_cost < best_cost.get(neighbor, float("inf")):
                best_cost[neighbor] = new_cost
                heapq.heappush(
                    open_list,
                    (new_cost + heuristic(neighbor, goal),
                     new_cost, neighbor, path + [neighbor]),
                )
    return None


class HybridAgent:
    def __init__(self, grid, start, goal):
        self.grid, self.position, self.goal = grid, start, goal

    def perceive(self):
        print("Agent perceives environment.")
        print("Current position:", self.position)

    def deliberate(self):
        print("Agent is deliberating using A*...")
        return a_star(self.grid, self.position, self.goal)

    def react(self, next_position):
        """Safety layer: reject a move if it is blocked or outside the grid."""
        r, c = next_position
        if not (0 <= r < len(self.grid) and 0 <= c < len(self.grid[0])):
            return False
        return self.grid[r][c] == 0

    def act(self, path):
        if not path:
            print("No path to the goal was found.")
            return
        print("\nPlanned path:")
        print(path)
        for position in path[1:]:
            if not self.react(position):
                print("Obstacle detected; stopping and replanning is required.")
                return
            self.position = position
            print("Agent moves to:", self.position)
        if self.position == self.goal:
            print("Goal reached!")

    def run(self):
        self.perceive()
        self.act(self.deliberate())


if __name__ == "__main__":
    agent = HybridAgent(GRID, (0, 0), (4, 4))
    agent.run()