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.
We can start with blizzard mechanics:
@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.
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.