advent_of_code_2022

commit c1f3cd0bf3859795b4ebce2aa04094990424224c
parent b0b0af461faa5613705241360c59e33741d28575
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Tue,  3 Jan 2023 22:16:50 -0800

Solution to day 24, part 2.

Only needed relatively minor updates to make part 2 work, but it's
pretty hacky (and slow). Oh well, a star's a star.

Diffstat:
M
src/day_24.jl
 | 
63
++++++++++++++++++++++++++++++++++++++++++++++++++-------------

1 file changed, 50 insertions(+), 13 deletions(-)
diff --git a/src/day_24.jl b/src/day_24.jl
@@ -61,21 +61,22 @@ function setmaptime!(blizzardmap::BlizzardMap, newtime::Int)
     if timeoffset == 0
         blizzardmap
     else
-        oldmap = copy(blizzardmap.blizzards)
+        newmap = similar(blizzardmap.blizzards)
         for y = 1:size(blizzardmap, 1), x = 1:size(blizzardmap, 2)
-            blizzardmap.blizzards[y, x, 1] = oldmap[
+            newmap[y, x, 1] = blizzardmap.blizzards[
                 1+mod(y-1+timeoffset, size(blizzardmap, 1)), x, 1
             ]
-            blizzardmap.blizzards[y, x, 2] = oldmap[
+            newmap[y, x, 2] = blizzardmap.blizzards[
                 1+mod(y-1-timeoffset, size(blizzardmap, 1)), x, 2
             ]
-            blizzardmap.blizzards[y, x, 3] = oldmap[
+            newmap[y, x, 3] = blizzardmap.blizzards[
                 y, 1+mod(x-1+timeoffset, size(blizzardmap, 2)), 3
             ]
-            blizzardmap.blizzards[y, x, 4] = oldmap[
+            newmap[y, x, 4] = blizzardmap.blizzards[
                 y, 1+mod(x-1-timeoffset, size(blizzardmap, 2)), 4
             ]
         end
+        blizzardmap.blizzards = newmap
         blizzardmap
     end
 end
@@ -136,11 +137,14 @@ function manhattandist(node::Node, blizzardmap::BlizzardMap)
         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]
-        pushfirst!(totalpath, current)
+        push!(totalpath, current)
     end
     totalpath
 end
@@ -149,16 +153,17 @@ 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.
+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)
+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. Since the first element of each node codes that implicitly,
-    # we can just use a set.
+    # 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
@@ -168,6 +173,7 @@ function navigatemap(blizzardmap::BlizzardMap, h::Function)
         current = dequeue!(openset)
 
         if isgoal(current, blizzardmap)
+            setmaptime!(blizzardmap, current[1])
             return reconstruct_path(camefrom, current)
         end
 
@@ -183,12 +189,43 @@ function navigatemap(blizzardmap::BlizzardMap, h::Function)
 end
 
 function part_1(input)
-    length(navigatemap(BlizzardMap(input), manhattandist))-1
+    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)
-    nothing
+    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)