commit b0b0af461faa5613705241360c59e33741d28575
parent 09fc897885233cca0455911979cb1e31ef19731f
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Thu, 29 Dec 2022 13:20:41 -0800
Solution to day 24, part 1.
Diffstat:
| A | src/day_24.jl | | | 194 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 194 insertions(+), 0 deletions(-)
diff --git a/src/day_24.jl b/src/day_24.jl
@@ -0,0 +1,194 @@
+#!/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
+ oldmap = copy(blizzardmap.blizzards)
+ for y = 1:size(blizzardmap, 1), x = 1:size(blizzardmap, 2)
+ blizzardmap.blizzards[y, x, 1] = oldmap[
+ 1+mod(y-1+timeoffset, size(blizzardmap, 1)), x, 1
+ ]
+ blizzardmap.blizzards[y, x, 2] = oldmap[
+ 1+mod(y-1-timeoffset, size(blizzardmap, 1)), x, 2
+ ]
+ blizzardmap.blizzards[y, x, 3] = oldmap[
+ y, 1+mod(x-1+timeoffset, size(blizzardmap, 2)), 3
+ ]
+ blizzardmap.blizzards[y, x, 4] = oldmap[
+ y, 1+mod(x-1-timeoffset, size(blizzardmap, 2)), 4
+ ]
+ end
+ 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
+
+function reconstruct_path(camefrom::Dict{Node, Node}, current::Node)
+ totalpath = [current]
+ while current ∈ keys(camefrom)
+ current = camefrom[current]
+ pushfirst!(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's actually just breadth-first search. Might need to fix that
+depending on the non-example input and part 2 requirements.
+"""
+function navigatemap(blizzardmap::BlizzardMap, h::Function)
+ start = (0, 0, 1)
+ camefrom = Dict{Node, Node}()
+
+ # This is usually a map giving the lowest known cost path from start to
+ # each known. 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)
+ 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)
+ length(navigatemap(BlizzardMap(input), manhattandist))-1
+end
+@assert part_1(example) == 18
+@info part_1(input)
+
+function part_2(input)
+ nothing
+end
+@info part_2(input)
