#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1007
Task: Write a Python function that generates a random 15x15 maze and solves it with A* algorithm
Generated: 2026-02-12T16:47:13.249431
"""

import random
import heapq

def generate_maze(size=15):
    maze = [[1 for _ in range(size)] for _ in range(size)]
    directions = [(0, 2), (2, 0), (0, -2), (-2, 0)]
    stack = [(0, 0)]
    visited = set()
    visited.add((0, 0))
    maze[0][0] = 0

    while stack:
        x, y = stack[-1]
        neighbors = []
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < size and 0 <= ny < size and (nx, ny) not in visited:
                neighbors.append((nx, ny))
        if neighbors:
            nx, ny = random.choice(neighbors)
            maze[(x + nx) // 2][(y + ny) // 2] = 0
            visited.add((nx, ny))
            stack.append((nx, ny))
        else:
            stack.pop()
    return maze

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

def a_star(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    visited = set()
    queue = [(0, start)]
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while queue:
        current_f, current = heapq.heappop(queue)
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        visited.add(current)
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = current[0] + dx, current[1] + dy
            neighbor = (nx, ny)
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and neighbor not in visited:
                tentative_g = g_score[current] + 1
                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(queue, (f_score[neighbor], neighbor))
    return None

def solve_maze(maze):
    start = (0, 0)
    goal = (len(maze)-1, len(maze)-1)
    path = a_star(maze, start, goal)
    if path:
        print("Path found:", path)
    else:
        print("No path found.")

if __name__ == '__main__':
    maze = generate_maze()
    print("Generated Maze (0 = path, 1 = wall):")
    for row in maze:
        print(row)
    solve_maze(maze)