Search Practice: Midterm-Style Tasksڕاهێنانی گەڕان: ئەرکی وەک تاقیکردنەوەی نیوەی وەرز

import heapq

WALL = "#"
MAZE = [
    "#           ",
    "# ######### ",
    "# #       # ",
    "# # ##### # ",
    "#   #     # ",
    "### # ##### ",
    "    #       ",
]


class Point:
    def __init__(self, x, y):
        self.x = x  # row
        self.y = y  # column

    def __repr__(self):
        return f"({self.x}, {self.y})"

    def __eq__(self, other):          # two points are equal if row and column match
        return self.x == other.x and self.y == other.y

    def __hash__(self):               # so points can go in sets and dictionary keys
        return hash((self.x, self.y))


def is_open(maze, p):
    """True if p is inside the maze and not a wall."""
    return 0 <= p.x < len(maze) and 0 <= p.y < len(maze[0]) and maze[p.x][p.y] != WALL


def manhattan(a, b):
    return abs(a.x - b.x) + abs(a.y - b.y)


def solve(maze, start, end):
    """A* from start to end. Returns the path (a list of points) or None."""
    count = 0
    frontier = [(manhattan(start, end), count, start)]
    g = {start: 0}
    parent = {start: None}
    closed = set()
    while frontier:
        _, _, current = heapq.heappop(frontier)
        if current in closed:
            continue
        if current == end:
            return backtrack(parent, current)
        closed.add(current)
        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nxt = Point(current.x + dx, current.y + dy)
            if is_open(maze, nxt) and g[current] + 1 < g.get(nxt, float("inf")):
                g[nxt] = g[current] + 1
                parent[nxt] = current
                count += 1
                heapq.heappush(frontier, (g[nxt] + manhattan(nxt, end), count, nxt))
    return None


def backtrack(parent, end):
    path = []
    while end is not None:
        path.append(end)
        end = parent[end]
    return path[::-1]


if __name__ == "__main__":
    path = solve(MAZE, Point(6, 0), Point(0, 11))
    print("Path:", path)
    print("Cells:", len(path), "| steps:", len(path) - 1)

import random
from astar_grid import MAZE, Point, is_open, solve


def random_open_point(maze):
    while True:                                   # try until we hit an open cell
        p = Point(random.randint(0, len(maze) - 1),     # randint includes both ends
                  random.randint(0, len(maze[0]) - 1))
        if is_open(maze, p):
            return p


start = random_open_point(MAZE)
end = random_open_point(MAZE)
while end == start:                               # the goal must be another cell
    end = random_open_point(MAZE)

print(f"Random start: {start}, random goal: {end}")
path = solve(MAZE, start, end)
if path:
    print("Path:", path)
    print("Steps:", len(path) - 1)
else:
    print("No path between these two cells.")

from astar_grid import MAZE, Point, is_open, solve


def ask_point(prompt, maze):
    while True:
        text = input(prompt)
        try:
            x, y = map(int, text.split(","))      # "6,0" -> 6 and 0 (never eval!)
        except ValueError:
            print("Please type row,column - for example 6,0")
            continue
        p = Point(x, y)
        if is_open(maze, p):                      # inside the maze and not a wall
            return p
        print("That cell is outside the maze or a wall. Try again.")


for row in MAZE:
    print("|" + row + "|")

while True:
    start = ask_point("Start (row,column): ", MAZE)
    end = ask_point("Goal (row,column): ", MAZE)
    path = solve(MAZE, start, end)
    if path:
        print("Path:", path)
        print("Steps:", len(path) - 1)
    else:
        print("The goal cannot be reached from the start.")
    if input("Try again? (yes/no): ").strip().lower() != "yes":
        break

import heapq
from astar_grid import MAZE, Point, is_open, manhattan, backtrack


def solve_nearest(maze, start, goals):
    """A* that stops at the first goal it selects: the nearest one."""
    def h(p):                                   # distance to the NEAREST goal
        return min(manhattan(p, goal) for goal in goals)

    count = 0
    frontier = [(h(start), count, start)]
    g = {start: 0}
    parent = {start: None}
    closed = set()
    while frontier:
        _, _, current = heapq.heappop(frontier)
        if current in closed:
            continue
        if current in goals:                    # any goal ends the search
            return backtrack(parent, current), g[current]
        closed.add(current)
        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nxt = Point(current.x + dx, current.y + dy)
            if is_open(maze, nxt) and g[current] + 1 < g.get(nxt, float("inf")):
                g[nxt] = g[current] + 1
                parent[nxt] = current
                count += 1
                heapq.heappush(frontier, (g[nxt] + h(nxt), count, nxt))
    return None, None


start = Point(6, 0)
goals = {Point(0, 11), Point(4, 8)}
path, cost = solve_nearest(MAZE, start, goals)
print("Nearest goal:", path[-1])
print("Path:", path)
print("Cells on the path:", len(path))
print("Steps:", len(path) - 1, "| cost:", cost)

from astar_grid import MAZE, Point, is_open, solve


def visit_all_goals(maze, start, goals):
    for goal in goals:                          # check the goals BEFORE searching
        if not is_open(maze, goal):
            print(f"Goal {goal} is a wall or outside the maze.")
            return None
    route = [start]
    current = start
    for goal in goals:                          # the goals in the given order
        path = solve(maze, current, goal)
        if path is None:
            print(f"No path from {current} to {goal}.")
            return None
        route += path[1:]                       # path[0] is already in the route
        current = goal
    return route


start = Point(6, 0)
for goals in ([Point(0, 11), Point(2, 3), Point(5, 7)],
              [Point(0, 11), Point(2, 3), Point(5, 5)]):
    print("Goals:", goals)
    route = visit_all_goals(MAZE, start, goals)
    if route:
        print("Route:", route)
        print("Total steps:", len(route) - 1)
    print()

from itertools import permutations
from astar_grid import MAZE, Point, solve


def steps(a, b):
    return len(solve(MAZE, a, b)) - 1


start = Point(6, 0)
goals = [Point(0, 11), Point(2, 3), Point(5, 5)]
best = None
for order in permutations(goals):            # 3 goals -> 3 x 2 x 1 = 6 orders
    total = 0
    current = start
    for goal in order:
        total += steps(current, goal)
        current = goal
    print(order, total)
    if best is None or total < best[0]:
        best = (total, order)
print("Best order:", best[1], "with", best[0], "steps")

roads = [["Slemani", "Arbat"], ["Arbat", "Said Sadiq"], ["Said Sadiq", "Halabja"]]


def roads_to_graph(roads):
    graph = {}
    for town1, town2 in roads:
        if town1 not in graph:
            graph[town1] = []
        if town2 not in graph:
            graph[town2] = []
        graph[town1].append(town2)        # a road works both ways
        graph[town2].append(town1)
    return graph


def find_path(graph, start, end, visited=None):
    if visited is None:                   # a NEW set for every first call
        visited = set()
    if start == end:
        return [start]
    visited.add(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            path = find_path(graph, neighbour, end, visited)   # recursion
            if path:
                return [start] + path
    return None


def deliver_parcel(graph, start, destination):
    path = find_path(graph, start, destination)
    if path is None:
        print("No path found!")
    else:
        for i in range(len(path) - 1):
            print(f"Moving from {path[i]} to {path[i + 1]}")


graph = roads_to_graph(roads)
print(graph)
deliver_parcel(graph, "Slemani", "Halabja")

from collections import deque
from town_astar import ROADS, STRAIGHT_LINE, roads_to_graph, a_star


def fewest_roads(graph, start, goal):
    """Breadth-first search: the path with the fewest roads."""
    frontier = deque([start])          # a FIFO queue
    parent = {start: None}             # also our 'reached' set
    while frontier:
        town = frontier.popleft()      # the oldest town first
        if town == goal:
            path = []
            while town is not None:
                path.append(town)
                town = parent[town]
            return path[::-1]
        for nxt in graph[town]:
            if nxt not in parent:
                parent[nxt] = town
                frontier.append(nxt)
    return None


def km(graph, path):
    return sum(graph[a][b] for a, b in zip(path, path[1:]))


graph = roads_to_graph(ROADS)
path = fewest_roads(graph, "Slemani", "Halabja")
print("BFS:", " -> ".join(path), "|", len(path) - 1, "roads |", km(graph, path), "km")
cost, path, _ = a_star(graph, STRAIGHT_LINE, "Slemani", "Halabja")
print("A*: ", " -> ".join(path), "|", len(path) - 1, "roads |", cost, "km")

graph = {"Slemani": ["Arbat"], "Arbat": ["Slemani", "Said Sadiq"],
         "Said Sadiq": ["Arbat", "Halabja"], "Halabja": ["Said Sadiq"]}


def find_path(graph, start, end, visited=set()):   # WRONG: one set for ALL calls
    if start == end:
        return [start]
    visited.add(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            path = find_path(graph, neighbour, end, visited)
            if path:
                return [start] + path
    return None


print(find_path(graph, "Slemani", "Halabja"))   # first delivery
print(find_path(graph, "Slemani", "Halabja"))   # second delivery: same question!