# Advent of Code 2022, Day 24: Blizzard Basin

#ruby #advent of code 2022

## Part A

Description for Day 24 mentions minutes, so we can already brace for difficult problem to solve like on Day 16 and Day 19.

This one is actually different. There is no time limit. We need to find the shortest path from our starting point to our target. So we should be able to use usual graph algorithms to solve it. The difficult part is that our graph is changing every minute. To be precise the edges between nodes are changing, because there are blizzards moving between nodes and we need to avoid them.

Our input looks like this:

``````#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
``````

Dot represent empty space, hash is a wall and arrows represents blizzards’ positions and direction. In each minute blizzard is moving in the defined direction and wrapping to another side when reaching the border of the map. We start in top left empty space on the border and we need to reach bottom right empty space on the border.

``````@map = File.readlines("24.txt", chomp: true).map { |line| line.split("") }

class Blizzards
MOVEMENTS = {
right: [1, 0],
down: [0, 1],
left: [-1, 0],
up: [0, -1]
}

def initialize(map_x, map_y, blizzards)
@map_x = map_x
@map_y = map_y
@blizzards = blizzards
end

def self.from_map(map)
blizzards = []

map.each_with_index do |row, y|
row.each_with_index do |tile, x|
if %w{> < v ^}.include?(tile)
blizzards.push([x, y, tile_to_direction(tile)])
end
end
end

new(map[0].size, map.size, blizzards)
end

def move
moved_blizzards = @blizzards.each do |blizzard|
nx, ny = move_single(blizzard)

blizzard[0] = nx
blizzard[1] = ny
end

self.class.new(@map_x, @map_y, moved_blizzards)
end

def generate_map
blizzards_map = {}

@blizzards.each do |(x, y, direction)|
if blizzards_map[[x, y]].is_a?(String)
blizzards_map[[x, y]] = 2
elsif blizzards_map[[x, y]].is_a?(Integer)
blizzards_map[[x, y]] += 1
else
blizzards_map[[x, y]] = direction_to_tile(direction)
end
end

blizzards_map
end

def get_free_map
return @free_map if @free_map

blizzards_map = generate_map
free_map = []

1.upto(@map_y - 2) do |y|
1.upto(@map_x - 2) do |x|
free_map.push([x, y]) if blizzards_map[[x, y]].nil?
end
end

@free_map = free_map

@free_map
end

private

def move_single(blizzard)
x, y, direction = blizzard
dx, dy = MOVEMENTS[direction]

nx = x + dx
ny = y + dy

if direction == :right && nx == @map_x - 1
nx = 1
elsif direction == :down && ny == @map_y - 1
ny = 1
elsif direction == :left && nx == 0
nx = @map_x - 2
elsif direction == :up && ny == 0
ny = @map_y - 2
end

[nx, ny]
end
end

class BlizzardsCache
def initialize(blizzards)
@cache = [blizzards]
end

def get(minute)
if @cache[minute].nil?
(@cache.size).upto(minute) do |index|
@cache[index] = @cache[index - 1].move
end
end

@cache[minute]
end
end

def tile_to_direction(tile)
case tile
when ">"
:right
when "<"
:left
when "v"
:down
when "^"
:up
end
end

def direction_to_tile(direction)
case direction
when :right
">"
when :left
"<"
when :down
"v"
when :up
"^"
end
end
``````

`Blizzards` class can represent all blizzards and simulate their moves with `move` and `move_single` methods. `generate_map` generates a hash with positions that contain any blizzard currently. And `get_free_map` is the opposite, it returns positions that do not contain any blizzard.

We also have `BlizzardsCache` class which stores instances of `Blizzards` classes for all minutes.

For finding shortest path we can use Breadth-First Search (BFS) together with small optimization that we will explore neighbors that are closer to our target first.

Here is the code:

``````blizzards = Blizzards.from_map(@map)
@cache = BlizzardsCache.new(blizzards)
@map_x = @map[0].size
@map_y = @map.size

@start = [1, 0]
@finish = [@map_x - 2, @map_y - 1]
# @finish = [1, 0]
# @start = [@map_x - 2, @map_y - 1]

@queue = [[@start, 0]]

def neighbors(x, y)
candidates = [[x, y], [x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]

candidates.reject do |candidate|
candidate != @start && candidate != @finish && (candidate[0] <= 0 || candidate[0] >= @map_x - 1 || candidate[1] <= 0 || candidate[1] >= @map_y - 1)
end
end

def score(x, y)
(@finish[0] - x).abs + (@finish[1] - y).abs
end

closest = @start
closest_distance = score(*closest)

@visited = {}

while @queue.any?
position, time = @queue.shift

if score(*position) < closest_distance
closest_distance = score(*position)
closest = position

puts "Found new closest position = (#{closest[0]}, #{closest[1]}), time = #{time}, queue = #{@queue.size}"
end

if position == @finish
puts "Reached goal in #{time} moves"
break
end

free_map = @cache.get(time + 1).get_free_map

neighbors = neighbors(*position).select { |(x, y)| free_map.include?([x, y]) || [x, y] == @start || [x, y] == @finish }

if neighbors.any?
neighbors.sort_by { |neighbor| score(*neighbor) }.each do |neighbor|
if !@visited[[neighbor, time + 1]]
@queue.push([neighbor, time + 1])
@visited[[neighbor, time + 1]] = true
end
end
end
end
``````

So `neighbors` method is generating a list of possible neighbors to explore and rejects those that are outside of our map. `score` is used to calculate the Manhattan distance to our target. On our queue we will store pairs of values, our node positions plus current time. The same with already visited nodes, the key will be node position and time, because it is possible to visit given node multiple times. Sometimes we need to move back to avoid the blizzard.

In each iteration we pick first element from our queue, generate our free map for the current time and generate possible neighbors. It is only possible to move to neighbors that will not have blizzard in the next minute. We also sort neighbors by score, adding to the queue those that are closer to our target.

It is not the fastest solution. There are probably better heurestics, but my solution took less than a minute so it was fine with me.

Here is the full code:

``````@map = File.readlines("24.txt", chomp: true).map { |line| line.split("") }

class Blizzards
MOVEMENTS = {
right: [1, 0],
down: [0, 1],
left: [-1, 0],
up: [0, -1]
}

def initialize(map_x, map_y, blizzards)
@map_x = map_x
@map_y = map_y
@blizzards = blizzards
end

def self.from_map(map)
blizzards = []

map.each_with_index do |row, y|
row.each_with_index do |tile, x|
if %w{> < v ^}.include?(tile)
blizzards.push([x, y, tile_to_direction(tile)])
end
end
end

new(map[0].size, map.size, blizzards)
end

def move
moved_blizzards = @blizzards.each do |blizzard|
nx, ny = move_single(blizzard)

blizzard[0] = nx
blizzard[1] = ny
end

self.class.new(@map_x, @map_y, moved_blizzards)
end

def generate_map
blizzards_map = {}

@blizzards.each do |(x, y, direction)|
if blizzards_map[[x, y]].is_a?(String)
blizzards_map[[x, y]] = 2
elsif blizzards_map[[x, y]].is_a?(Integer)
blizzards_map[[x, y]] += 1
else
blizzards_map[[x, y]] = direction_to_tile(direction)
end
end

blizzards_map
end

def get_free_map
return @free_map if @free_map

blizzards_map = generate_map
free_map = []

1.upto(@map_y - 2) do |y|
1.upto(@map_x - 2) do |x|
free_map.push([x, y]) if blizzards_map[[x, y]].nil?
end
end

@free_map = free_map

@free_map
end

private

def move_single(blizzard)
x, y, direction = blizzard
dx, dy = MOVEMENTS[direction]

nx = x + dx
ny = y + dy

if direction == :right && nx == @map_x - 1
nx = 1
elsif direction == :down && ny == @map_y - 1
ny = 1
elsif direction == :left && nx == 0
nx = @map_x - 2
elsif direction == :up && ny == 0
ny = @map_y - 2
end

[nx, ny]
end
end

class BlizzardsCache
def initialize(blizzards)
@cache = [blizzards]
end

def get(minute)
if @cache[minute].nil?
(@cache.size).upto(minute) do |index|
@cache[index] = @cache[index - 1].move
end
end

@cache[minute]
end
end

def tile_to_direction(tile)
case tile
when ">"
:right
when "<"
:left
when "v"
:down
when "^"
:up
end
end

def direction_to_tile(direction)
case direction
when :right
">"
when :left
"<"
when :down
"v"
when :up
"^"
end
end

def draw_map(blizzards_map)
puts "#" * @map_x
1.upto(@map_y - 2) do |y|
row = "#"
1.upto(@map_x - 2) do |x|
if blizzards_map[[x, y]]
row += blizzards_map[[x, y]].to_s
else
row += "."
end
end
row += "#"
puts row
end
puts "#" * @map_x
end

blizzards = Blizzards.from_map(@map)
@cache = BlizzardsCache.new(blizzards)
@map_x = @map[0].size
@map_y = @map.size

@start = [1, 0]
@finish = [@map_x - 2, @map_y - 1]
# @finish = [1, 0]
# @start = [@map_x - 2, @map_y - 1]

@queue = [[@start, 0]]

def neighbors(x, y)
candidates = [[x, y], [x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]

candidates.reject do |candidate|
candidate != @start && candidate != @finish && (candidate[0] <= 0 || candidate[0] >= @map_x - 1 || candidate[1] <= 0 || candidate[1] >= @map_y - 1)
end
end

def score(x, y)
(@finish[0] - x).abs + (@finish[1] - y).abs
end

closest = @start
closest_distance = score(*closest)

@visited = {}

while @queue.any?
position, time = @queue.shift

if score(*position) < closest_distance
closest_distance = score(*position)
closest = position

puts "Found new closest position = (#{closest[0]}, #{closest[1]}), time = #{time}, queue = #{@queue.size}"
end

if position == @finish
puts "Reached goal in #{time} moves"
break
end

free_map = @cache.get(time + 1).get_free_map

neighbors = neighbors(*position).select { |(x, y)| free_map.include?([x, y]) || [x, y] == @start || [x, y] == @finish }

if neighbors.any?
neighbors.sort_by { |neighbor| score(*neighbor) }.each do |neighbor|
if !@visited[[neighbor, time + 1]]
@queue.push([neighbor, time + 1])
@visited[[neighbor, time + 1]] = true
end
end
end
end
``````

I added some debugging code to display how close we are to the target. It is just to give some indication when this program will end.

## Part B

In second part we need to go from start to the end, then move back because one of the elves forgot his snacks and then again from start to end.

I used the same code exactly. I was just flipping start and finish and adjusting the start time.