hill climbing algorithm

approach

the heightmap is a grid of letters. the start and end markers are found and replaced with a and z, so every cell compares by ord. a breadth-first search moves to a neighbour only if it is at most one letter higher, and returns the number of levels when it reaches the end.

part 1 starts the search from the single start cell. part 2 reuses the same function but seeds the queue with every a cell at once, so the first level that reaches the end is the shortest path from any of them.

the trick

the same bfs answers both parts: seed it with one cell or with every a cell, and the first level to reach the end is the shortest path.

# p1
print(bfs(heightmap, [start], end))

# p2
p2 = [(r, c) for r in range(len(heightmap)) for c in range(len(heightmap[0])) if heightmap[r][c] == 'a']
print(bfs(heightmap, p2, end))