# [Advent Of Code 2022] Day 12: Hill Climbing Algorithm [SPOILERS]

And as every year: a path finding puzzle.

Python Solution
``````def read_file(file: TextIO) -> tuple[list[list[int]], Pos, Pos]:
"""Read a grid from the `file`."""
lines = [line.rstrip() for line in file if line]

def char_to_height(char: str) -> int:
if char == 'S':
return 0
if char == 'E':
return 25
return ord(char) - ord('a')

grid = [[char_to_height(c) for c in line] for line in lines]

for pos, char in iter_grid_val(lines):
if char == 'S':
start = pos
elif char == 'E':
end = pos
return grid, start, end

def min_path_length(
start: Pos,
next_states: Callable[[Pos], Iterable[Pos]],
is_end: Callable[[Pos], bool]
) -> int:
"""Calculate the minimal steps to an end."""
visited = {start}
current_positions = [start]
count = 1
while current_positions:
next_positions = []
for pos in current_positions:
for neighbor in next_states(pos):
if neighbor in visited:
continue
if is_end(neighbor):
return count
next_positions.append(neighbor)
current_positions = next_positions
count += 1
return -1

def part1(file: TextIO) -> int:
"""Solve the first part of the puzzle."""

def next_states(pos):
height_pos = grid[pos.y][pos.x]
for neighbor, neighbor_height in neighbors4_val(pos, grid):
if height_pos + 1 >= neighbor_height:
yield neighbor

return min_path_length(start, next_states, lambda pos: pos == end)

def part2(file: TextIO) -> int:
"""Solve the second part of the puzzle."""

def next_states(pos):
height_pos = grid[pos.y][pos.x]
for neighbor, neighbor_height in neighbors4_val(pos, grid):
if height_pos <= neighbor_height + 1:
yield neighbor

return min_path_length(
start, next_states, lambda pos: grid[pos.y][pos.x] == 0)
``````

@IsaacG Were you prepared and achieved some small rank?

I learnt about Dijkstra’s algorithm last year, which I loved! Happy to be able to whip it out this year too.

Ruby Solution
``````require 'lazy_priority_queue'

grid = File.readlines('inputs/12.txt', chomp: true).each_with_index.inject({}) do|grid, (cols, row)|
grid.tap {cols.chars.each_with_index { |height, col| grid[[row, col]] = height.ord } }
end

start_coord = grid.key('S'.ord)
goal_coord  = grid.key('E'.ord)

grid[start_coord] = 'a'.ord
grid[goal_coord] = 'z'.ord

def neighbors(coord, steps, grid)
[[-1, 0], [1, 0], [0, -1], [0, 1]].filter_map do |dy, dx|
neighbor = [coord + dy, coord + dx]
[neighbor, steps + 1] if grid.key?(neighbor) && grid[neighbor] - grid[coord] <= 1
end
end

def fewest_steps(grid, goal_coord, start_coords)
queue = MinPriorityQueue.new
min_steps = Hash.new(Float::INFINITY)

start_coords.each do |coord|
queue.push [coord, 0], 0
min_steps[coord] = 0
end

while ((coord, steps) = queue.pop)
return min_steps[goal_coord] if coord == goal_coord

neighbors(coord, steps, grid).each do |neighbor, neighbor_steps|
if neighbor_steps < min_steps[neighbor]
min_steps[neighbor] = neighbor_steps
queue.push [neighbor, neighbor_steps], neighbor_steps
end
end
end
end

a = fewest_steps(grid, goal_coord, [start_coord])
b = fewest_steps(grid, goal_coord, grid.filter_map {|coord, height| coord if height == 'a'.ord })

require 'minitest/autorun'

describe 'day 12' do
it 'part a' do assert_equal 468, a end
it 'part b' do assert_equal 459, b end
end
``````

I’m not very good at implementing graph traversals. I tried to use a PriorityQueue at first, got lost in it somewhere and shot my ranking. Day 12 was not one of my better ranks Code: Get It WorkingLatest

Python Solver
``````    def solver(self, starts: list[complex], end: complex, board: aoc.Board) -> int:
"""Return the min steps from start to end."""
step_count = {point: 0 for point in starts}
to_visit = collections.deque(starts)

while to_visit:
point = to_visit.popleft()
for neighbor, height in board.neighbors(point).items():
# Cannot climb a steep hill.
if height - 1 > board[point]:
continue
if neighbor in step_count:
continue
if neighbor == end:
return step_count[point] + 1
step_count[neighbor] = step_count[point] + 1
to_visit.append(neighbor)