Advent of Code - 2022
This is a solution to Day 12 of Advent of Code 2022.
Day 12 - Hill Climbing Algorithm
You try contacting the Elves using your handheld device, but the river you're following must be too low to get a decent signal.
You ask the device for a heightmap of the surrounding area (your puzzle input). The heightmap shows the local area from above broken into a grid; the elevation of each square of the grid is given by a single lowercase letter, where a is the lowest elevation, b is the next-lowest, and so on up to the highest elevation, z.
Also included on the heightmap are marks for your current position (S) and the location that should get the best signal (E). Your current position (S) has elevation a, and the location that should get the best signal (E) has elevation z.
You'd like to reach E, but to save energy, you should do it in as few steps as possible. During each step, you can move exactly one square up, down, left, or right. To avoid needing to get out your climbing gear, the elevation of the destination square can be at most one higher than the elevation of your current square; that is, if your current elevation is m, you could step to elevation n, but not to elevation o. (This also means that the elevation of the destination square can be much lower than the elevation of your current square.)
For example:
Sabqponm abcryxxl accszExk acctuvwj abdefghiHere, you start in the top-left corner; your goal is near the middle. You could start by moving down or right, but eventually you'll need to head toward the e at the bottom. From there, you can spiral around to the goal:
v..v<<<< >v.vv<<^ .>vv>E^^ ..v>>>^^ ..>>>>>^In the above diagram, the symbols indicate whether the path exits each square moving up (^), down (v), left (<), or right (>). The location that should get the best signal is still E, and . marks unvisited squares.
This path reaches the goal in 31 steps, the fewest possible.
My Advent of Code senses are tingling: we're gonna need a pathfinding algorithm! And what would be a better choice than A* (there might be better ones to be honest, A* is just the only one I know and it has a cool name).
I've implemented A* quite a few times in Advent of Code over the years. I still don't quite understand it but I'm able to implement it and get it right with surprising ease these days.
Read input
For today's map, we're using a dictionary to hold our values. This makes the path finding much simpler because we never need to worry about edge detection. To make it even easier, we're using defaultdict with a constant factory that makes the default value a positive infinity. This quarantees that we'll never be able to hike beyond the mountain.
To create the height map, we first read the input into a two-dimensional list (this is not strictly necessary, it just works best with my utils.read_input method. If you are parsing the input directly, you can skip that phase and just read the values into a dictionary.
For each item in the input, we add its coordinates into a dictionary, replacing the character with its corresponding number (a -> 0 and z -> 25) and when we run into a capital letter (S and E), we special case them and capture them as the start and goal points.
import math
from utils import read_input
from string import ascii_lowercase
from collections import defaultdict
def transformer(line):
return [char for char in line]
grid = read_input(12, transformer)
example = read_input(12, transformer, True)
def constant_factory(value):
return lambda: value
def create_height_map(grid):
height_map = defaultdict(constant_factory(math.inf))
start = None
goal = None
for y in range(len(grid)):
for x in range(len(grid[y])):
try:
height_map[(y, x)] = ascii_lowercase.index(grid[y][x])
except ValueError:
if grid[y][x] == 'S':
start = (y, x)
height_map[start] = 0
elif grid[y][x] == 'E':
goal = (y, x)
height_map[goal] = 25
else:
raise ValueError("Unknown height")
return height_map, start, goalThis is pretty much the 1:1 implementation of A* from Wikipedia's pseudocode.
A few helper functions to start with: reconstruct_path takes all the paths and current point and reverses the journey, giving us a linear path. get_neighbors finds all the viable neighboring spots - that is, anything max 1 value higher than current.
Finally, find_path starts with the start point, finds all viable neighbors, calculates the cost (in our case, the cost is always +1) and adds them to the path. It then eventually finds the result. How? I don't know, it's higher level computer science than I can explain to you.
I can follow the execution line by line but being able to explain why it works is bit murky to me.
import heapq
import math
def reconstruct_path(came_from, current):
total_path = [current]
while current in came_from:
current = came_from[current]
total_path.insert(0, current)
return total_path
def get_neighbors(current, height_map):
neighbors = []
top_neighbor = (current[0]-1, current[1])
if height_map[top_neighbor] <= height_map[current] + 1:
neighbors.append(top_neighbor)
right_neighbor = current[0], current[1] + 1
if height_map[right_neighbor] <= height_map[current] + 1:
neighbors.append(right_neighbor)
left_neighbor = current[0], current[1] - 1
if height_map[left_neighbor] <= height_map[current] + 1:
neighbors.append(left_neighbor)
bottom_neighbor = current[0] + 1, current[1]
if height_map[bottom_neighbor] <= height_map[current] + 1:
neighbors.append(bottom_neighbor)
return neighbors
def find_path(height_map, start, goal):
open_set = set([start])
came_from = dict()
g_score = defaultdict(constant_factory(math.inf))
g_score[start] = 0
while len(open_set) > 0:
current = open_set.pop()
if current == goal:
return reconstruct_path(came_from, current)
for neighbor in get_neighbors(current, height_map):
tentative_g_score = g_score[current] + 1
if tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
if neighbor not in open_set:
open_set.add(neighbor)
raise Exception("Did not reach goal")
def score_path(path):
# -1 because start point is included in the path
return len(path) - 1Part 1
What is the fewest steps required to move from your current position to the location that should get the best signal?
height_map, start, goal = create_height_map(grid)
shortest_climb = score_path(find_path(height_map, start, goal))
print(f'Part 1: {shortest_climb}')
assert shortest_climb == 534Part 2
As you walk up the hill, you suspect that the Elves will want to turn this into a hiking trail. The beginning isn't very scenic, though; perhaps you can find a better starting point.
To maximize exercise while hiking, the trail should start as low as possible: elevation a. The goal is still the square marked E. However, the trail should still be direct, taking the fewest steps to reach its goal. So, you'll need to find the shortest path from any square at elevation a to the square marked E.
Again consider the example from above:
Sabqponm abcryxxl accszExk acctuvwj abdefghiNow, there are six choices for starting position (five marked a, plus the square marked S that counts as being at elevation a). If you start at the bottom-left square, you can reach the goal most quickly:
...v<<<< ...vv<<^ ...v>E^^ .>v>>>^^ >^>>>>>^This path reaches the goal in only 29 steps, the fewest possible.
What is the fewest steps required to move starting from any square with elevation a to the location that should get the best signal?
There might be better ways to do this but since the input space is rather small, I just find all the possible start points first and then execute A* to all of them.
I figure it's probably possible to extract these different paths from A* directly if implemented slightly different so we wouldn't have to climb the same hills over and over again but I didn't do that.
I modified the neighbor finder from part 1 to only return neighbors with value of 0 (matching the a in input).
find_starting_points looks for valid neighbors (height of 0 and not previously checked) until it can't find any and then it returns them all.
def get_low_neighbors(current, height_map):
neighbors = []
top_neighbor = (current[0]-1, current[1])
if height_map[top_neighbor] == 0:
neighbors.append(top_neighbor)
right_neighbor = current[0], current[1] + 1
if height_map[right_neighbor] == 0:
neighbors.append(right_neighbor)
left_neighbor = current[0], current[1] - 1
if height_map[left_neighbor] == 0:
neighbors.append(left_neighbor)
bottom_neighbor = current[0]+1, current[1]
if height_map[bottom_neighbor] == 0:
neighbors.append(bottom_neighbor)
return set(neighbors)
def find_starting_points(height_map, start):
start_points = set([start])
to_check = get_low_neighbors(start, height_map)
start_points = start_points | to_check
checked = set([start])
while len(to_check) > 0:
current = to_check.pop()
checked.add(current)
neighbors = set(n for n in get_low_neighbors(current, height_map) if n not in checked)
to_check = to_check | neighbors
start_points.add(current)
return start_pointsFor every viable starting point, we run our A*, score it and find the smallest one.
height_map, start, goal = create_height_map(grid)
find_starting_points(height_map, start)
shortest = math.inf
for start_point in find_starting_points(height_map, start):
shortest_climb = score_path(find_path(height_map, start_point, goal))
if shortest_climb < shortest:
shortest = shortest_climb
print(f'Part 2: {shortest}')
assert shortest == 525