Skip to content
Hello Python

Navigate a Grid with A*

Practice ExerciseIntermediateMediumHeapMatrix / GridA* Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement astar_path_length(grid, start, goal). Cells are 0=open and 1=blocked; movement is four-directional. Return shortest steps or -1.

Starter code

def astar_path_length(grid, start, goal):
    pass
Test cases

detour

{
  "args": [
    [
      [
        0,
        1,
        0
      ],
      [
        0,
        0,
        0
      ],
      [
        1,
        0,
        0
      ]
    ],
    [
      0,
      0
    ],
    [
      0,
      2
    ]
  ]
}

Expected: 4

blocked

{
  "args": [
    [
      [
        0,
        1
      ],
      [
        1,
        0
      ]
    ],
    [
      0,
      0
    ],
    [
      1,
      1
    ]
  ]
}

Expected: -1

Wizard outline
  1. Step 1: Normalize the start and goal

    Return zero when the start already equals the goal. A zero-move path is the base case for every later frontier expansion.

  2. Step 2: Recognize a one-step path

    Generate valid orthogonal neighbors and return one for an adjacent goal. A* repeatedly applies the same bounded-neighbor transition.

  3. Step 3: Seed a cost frontier

    Put the start cell in a heap and expand two frontier cells. A heap gives later checkpoints a persistent place to store cells and their path costs.

  4. Step 4: Repeat frontier expansion safely

    Carry real path cost through enough heap pops to reach a three-step goal. A best-cost map makes repeated expansion terminate without discarding shorter discoveries.

  5. Step 5: Prioritize the complete A* frontier

    Add Manhattan priority and continue until the frontier is exhausted. A* combines real cost with an admissible heuristic while preserving best known costs.

Footguns and prerequisites
  • Marking visited when pushed can discard a cheaper later route.
  • Adding the heuristic into the stored path cost double-counts estimates.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Use a min-heap ordered by g+h, Manhattan h, and a separate best-known g-score map.

Why it works: Manhattan distance never overestimates four-directional remaining cost. Relaxation preserves best known g-scores, so the first non-stale goal removal has shortest path length.

def astar_path_length(grid, start, goal):
    import heapq
    rows, cols = len(grid), len(grid[0])
    start, goal = tuple(start), tuple(goal)
    def heuristic(cell):
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
    distance = {start: 0}
    frontier = [(heuristic(start), 0, start)]
    while frontier:
        _, cost, cell = heapq.heappop(frontier)
        if cost != distance[cell]:
            continue
        if cell == goal:
            return cost
        row, col = cell
        for neighbor in ((row+1,col),(row-1,col),(row,col+1),(row,col-1)):
            r, c = neighbor
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0 and cost + 1 < distance.get(neighbor, float('inf')):
                distance[neighbor] = cost + 1
                heapq.heappush(frontier, (cost + 1 + heuristic(neighbor), cost + 1, neighbor))
    return -1