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

Programming
1

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)
                visited.add(neighbor)
        current_positions = next_positions
        count += 1
    return -1


def part1(file: TextIO) -> int:
    """Solve the first part of the puzzle."""
    grid, start, end = read_file(file)

    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."""
    grid, _, start = read_file(file)

    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?

2

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[0] + dy, coord[1] + 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
3

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 :slight_smile:

Code: Get It Working – Latest

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)
        raise RuntimeError("Not found.")