ISEF computer science project mentoring

# Our example experiment: does a distance hint (A*) expand fewer cells than plain search (Dijkstra)?
import heapq, random, statistics

def make_grid(seed, size=30, wall_chance=0.25):
    rng = random.Random(seed)
    grid = [[rng.random() < wall_chance for _ in range(size)] for _ in range(size)]
    grid[0][0] = grid[size - 1][size - 1] = False
    return grid

def search(grid, use_hint):
    n = len(grid); goal = (n - 1, n - 1)
    hint = (lambda r, c: (goal[0] - r) + (goal[1] - c)) if use_hint else (lambda r, c: 0)
    frontier = [(hint(0, 0), 0, (0, 0))]
    cheapest = {(0, 0): 0}; expanded = 0
    while frontier:
        _, cost, (r, c) = heapq.heappop(frontier)
        if cost > cheapest[(r, c)]:
            continue
        expanded += 1
        if (r, c) == goal:
            return expanded, cost
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not grid[nr][nc]:
                if cost + 1 < cheapest.get((nr, nc), 10**9):
                    cheapest[(nr, nc)] = cost + 1
                    heapq.heappush(frontier, (cost + 1 + hint(nr, nc), cost + 1, (nr, nc)))
    return expanded, None          # no path in this maze

savings, skipped = [], 0
for seed in range(40):
    g = make_grid(seed)
    plain, length1 = search(g, use_hint=False)
    hinted, length2 = search(g, use_hint=True)
    if length1 is None:
        skipped += 1
        continue
    assert length1 == length2      # both must find equally short paths
    savings.append(1 - hinted / plain)

print(len(savings), "solvable mazes,", skipped, "skipped")
print("median saving", round(100 * statistics.median(savings), 1), "%")
print("range", round(100 * min(savings), 1), "to", round(100 * max(savings), 1), "%")

Our own teaching program, standard Python with no libraries to install. Fixed seeds mean anyone can rerun it and get the same mazes, which is the point.