advent_of_code_2022

day_24.jl (7150B)

---

 #!/usr/bin/env julia
 # https://adventofcode.com/2022/day/24
 using AdventOfCode
 using DataStructures
 
 example = readlines(IOBuffer("""
     #.######
     #>>.<^<#
     #.<..<<#
     #>v.><>#
     #<^v^^>#
     ######.#"""))
 input = readlines("data/day_24.txt")
 
 # Each node in our graph is represented by a three-tuple of time, y, and x
 Node = Tuple{Int,Int,Int}
 
 # The blizzard map is represented by 4 boolean matrices, each indicating the
 # blizzards at each location moving in a specific direction. We also bundle
 # with it the current timestep represented by the map
 mutable struct BlizzardMap
     blizzards::Array{Bool, 3}
     timestep::Int
 end
 
 """
 Read the puzzle input and return the blizzard positions.
 """
 function BlizzardMap(input::Vector{<:AbstractString})
     maparray = zeros(Bool,
         length(input)-2,
         length(input[1])-2,
         4
     )
 
     # Hardcoding the start and end positions, but checking that things look ok
     @assert input[1][2] == '.'
     @assert input[end][end-1] == '.'
 
     # Reading the rest of the map
     for (i, line) = enumerate(input[2:end-1])
         linechars = split(line, "")[2:end-1]
         maparray[i,:,1] = linechars .== "^"
         maparray[i,:,2] = linechars .== "v"
         maparray[i,:,3] = linechars .== "<"
         maparray[i,:,4] = linechars .== ">"
     end
 
     BlizzardMap(maparray, 0)
 end
 
 Base.size(blizzardmap::BlizzardMap, dim::Int) = size(blizzardmap.blizzards, dim)
 
 """
 Set the state of the blizzard map to a given time.
 """
 function setmaptime!(blizzardmap::BlizzardMap, newtime::Int)
     timeoffset = newtime - blizzardmap.timestep
     blizzardmap.timestep = newtime
 
     if timeoffset == 0
         blizzardmap
     else
         newmap = similar(blizzardmap.blizzards)
         for y = 1:size(blizzardmap, 1), x = 1:size(blizzardmap, 2)
             newmap[y, x, 1] = blizzardmap.blizzards[
                 1+mod(y-1+timeoffset, size(blizzardmap, 1)), x, 1
             ]
             newmap[y, x, 2] = blizzardmap.blizzards[
                 1+mod(y-1-timeoffset, size(blizzardmap, 1)), x, 2
             ]
             newmap[y, x, 3] = blizzardmap.blizzards[
                 y, 1+mod(x-1+timeoffset, size(blizzardmap, 2)), 3
             ]
             newmap[y, x, 4] = blizzardmap.blizzards[
                 y, 1+mod(x-1-timeoffset, size(blizzardmap, 2)), 4
             ]
         end
         blizzardmap.blizzards = newmap
         blizzardmap
     end
 end
 
 """
 Return true iff the node is the goal node
 """
 function isgoal(node::Node, blizzardmap::BlizzardMap)
     node[2] == size(blizzardmap, 1) + 1 &&
         node[3] == size(blizzardmap, 2)
 end
 
 """
 Return the neighbors (if any) of a given node in the blizzard map.
 
 This changes the time of the blizzard map.
 """
 function get_neighbors(node::Node, blizzardmap::BlizzardMap)::Vector{Node}
     if node[2] == size(blizzardmap, 1) && node[3] == size(blizzardmap, 2)
         # One tiny optimization/hack I'll use here is to only return the goal
         # node if we're next to it already.
         return([(node[1]+1, node[2]+1, node[3])])
     elseif isgoal(node, blizzardmap)
         # This is just defensive programming; if I do everything right before I
         # call this function, this branch will never be visited. Nevertheless!
         return([node])
     end
 
     setmaptime!(blizzardmap, node[1]+1)
     # nextmap shows where blizzards are, ie where we can't step
     # it's still a 3D array, but the third dimension length == 1
     nextmap = reduce(|, blizzardmap.blizzards, dims = 3)
     neighbors = Vector{Node}()
 
     if node[2] == 0 && node[3] == 1
         # We're at the start, where we always have the option to stay
         push!(neighbors, node .+ (1, 0, 0))
         !nextmap[1, 1, 1] && push!(neighbors, node .+ (1, 1, 0))
     else
         for (Δy, Δx) = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]
             (t, y, x) = node .+ (1, Δy, Δx)
             if y > 0 && x > 0 && 
                     y <= size(blizzardmap, 1) &&
                     x <= size(blizzardmap, 2) &&
                     !nextmap[y, x, 1]
                 push!(neighbors, (t, y, x))
             end
         end
     end
     neighbors
 end
 
 """
 Return the manhattan distance from the node to the goal.
 """
 function manhattandist(node::Node, blizzardmap::BlizzardMap)
     isgoal(node, blizzardmap) ? 0 :
         size(blizzardmap, 1) - node[2] + size(blizzardmap, 2) - node[3] + 1
 end
 
 """
 Reconstruct the path in reverse-chronological order.
 """
 function reconstruct_path(camefrom::Dict{Node, Node}, current::Node)
     totalpath = [current]
     while current ∈ keys(camefrom)
         current = camefrom[current]
         push!(totalpath, current)
     end
     totalpath
 end
 
 """
 Find the shortest path from the beginning to end of the map.
 
 This looks like A* search (I even cribbed from wikipedia's pseudocode, again),
 but I think it just reduces to a slightly smarter breadth-first search. Might
 need to fix that depending on the non-example input and part 2 requirements.
 This also changes blizzardmap.
 """
 function navigatemap!(blizzardmap::BlizzardMap, h::Function = manhattandist)
     start = (0, 0, 1)
     camefrom = Dict{Node, Node}()
 
     # This is usually a map giving the lowest known cost path from start to
     # each known node. Since the first element of each node codes that
     # implicitly, we can just use a set.
     gscore = Set([start])
 
     # The set of discovered nodes
     openset = PriorityQueue{Node, Int}(start => h(start, blizzardmap))
 
     while !isempty(openset)
         current = dequeue!(openset)
 
         if isgoal(current, blizzardmap)
             setmaptime!(blizzardmap, current[1])
             return reconstruct_path(camefrom, current)
         end
 
         for neighbor = get_neighbors(current, blizzardmap)
             if neighbor ∉ gscore
                 # We haven't found a path through this node before
                 openset[neighbor] = neighbor[1] + h(neighbor, blizzardmap)
                 camefrom[neighbor] = current
             end
         end
     end
     nothing
 end
 
 function part_1(input)
     navigatemap!(BlizzardMap(input))[1][1]
 end
 @assert part_1(example) == 18
 @info part_1(input)
 
 """
 Flip a map, as if you are turning around and retracing your steps.
 
 As hacks go, I'm not sure where this approach lands between 'clever' and
 'hideous', but if we can flip the map around, then solving part 2 is just a
 matter of solving part 1 two additional times.
 """
 function flipmap!(blizzardmap::BlizzardMap)
     newmap = similar(blizzardmap.blizzards)
 
     for y = 1:size(blizzardmap, 1), x = 1:size(blizzardmap, 2)
         oldy = size(blizzardmap, 1) - y + 1
         oldx = size(blizzardmap, 2) - x + 1
         for z = 1:4
             oldz = z % 2 == 1 ? z + 1 : z - 1
             newmap[y, x, z] = blizzardmap.blizzards[oldy, oldx, oldz]
         end
     end
 
     blizzardmap.blizzards = newmap
     blizzardmap.timestep = 0
     blizzardmap
 end
 
 function part_2(input)
     blizzardmap = BlizzardMap(input)
     steps = 0
     for i = 1:3
         steps += navigatemap!(blizzardmap)[1][1]
         i < 3 && flipmap!(blizzardmap)
     end
     steps
 end
 @assert part_2(example) == 54
 @info part_2(input)