Vibe Engines Learn
CODING CHALLENGE · N°42

A* Pathfinding on a Grid

Medium GraphsShortest PathHeuristics

The pathfinder inside games and robots: A* finds the shortest route on a grid by expanding nodes in order of "cost so far + estimated cost to go". The heuristic focuses the search toward the goal instead of spreading out blindly like plain BFS. Return the shortest path length. Solve it in Python or TypeScript, with hidden tests.

The problem

Given a grid of 0 (open) and 1 (wall), a start cell and a goal cell (both [row, col]), return the length (number of steps) of the shortest path using 4-directional moves, or -1 if the goal is unreachable. Use A* with the Manhattan-distance heuristic.

EXAMPLE 1
Input grid = [[0,0,0],[1,1,0],[0,0,0]], start = [0,0], goal = [2,0]
Output 6
must go around the wall row: right, right, down, down, left, left
EXAMPLE 2
Input grid = [[0,1],[1,0]], start = [0,0], goal = [1,1]
Output -1
walls block every route
CONSTRAINTS
  • Moves are up/down/left/right only (no diagonals); each step costs 1.
  • The Manhattan distance |dr| + |dc| is an admissible heuristic (never overestimates), so A* returns the true shortest length.
  • Expand nodes in order of f = g + h (cost-so-far + heuristic); return g at the goal, or -1 if the frontier empties first.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement astar(grid, start, goal): keep a frontier of cells ordered by f = g + h, and the best g reached per cell. Pop the lowest-f cell; if it is the goal return its g; otherwise relax its open neighbours. Return -1 if the frontier empties.

HINTS — 4 IDEAS
  1. g is the number of steps taken to reach a cell; h is the Manhattan distance from that cell to the goal.
  2. Order the frontier by f = g + h. A priority queue is ideal; for small grids, scanning the frontier for the minimum works too.
  3. Track the best g found for each cell; only push a neighbour when you reach it with a smaller g.
  4. Because the heuristic never overestimates, the first time you pop the goal, its g is the shortest path length.
CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Algorithms & DSA