advent_of_code_2022

commit 1452c97c449d7c66ccc7010cd3fa88efca38e1d6
parent ac59777db333e40d23938c9148d5f0953515dcbc
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Fri,  9 Dec 2022 19:11:55 -0800

Solution to day 9, part 2.

This was the first one that really got gnarly. I had to totally rewrite
my part 1 solution for it to extend to part 2, and my first "solution"
to the latter was off, so I had to break down and write the map-drawing
code (which helped).

Diffstat:
M
src/day_9.jl
 | 
124
+++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------------

1 file changed, 84 insertions(+), 40 deletions(-)
diff --git a/src/day_9.jl b/src/day_9.jl
@@ -13,51 +13,65 @@ example = readlines(IOBuffer("""
     R 2"""))
 input = readlines("data/day_9.txt")
 
-function increment_head_tail(head_position::Tuple{Int,Int},
-                             tail_position::Tuple{Int,Int},
-                             direction::Char)
-    if direction == 'L'
-        if head_position[1] - tail_position[1] < 0
-            tail_position = head_position
-        end
-        head_position = (head_position[1] - 1, head_position[2])
-    elseif direction == 'R'
-        if head_position[1] - tail_position[1] > 0
-            tail_position = head_position
-        end
-        head_position = (head_position[1] + 1, head_position[2])
-    elseif direction == 'D'
-        if head_position[2] - tail_position[2] < 0
-            tail_position = head_position
-        end
-        head_position = (head_position[1], head_position[2] - 1)
-    elseif direction == 'U'
-        if head_position[2] - tail_position[2] > 0
-            tail_position = head_position
-        end
-        head_position = (head_position[1], head_position[2] + 1)
-    else
-        error("invalid direction")
-    end
+"""
+Shift the head one left, right, up, or down as directed.
+"""
+function shift_head(head_position::Tuple{Int,Int},
+                    direction::Char)
+    offset = Dict(
+        'L' => (-1, 0),
+        'R' => (1, 0),
+        'U' => (0, 1),
+        'D' => (0, -1)
+    )
+    head_position .+ offset[direction]
+end
 
-    (head_position, tail_position)
+"""
+Return true if the knots are touching, and the difference vector (as a tuple)
+"""
+function touching(head_position, tail_position)
+    diff_vec = head_position .- tail_position
+    (maximum(abs.(diff_vec)) <= 1, diff_vec)
 end
 
-function move_head_tail(instructions)
-    head_position, tail_position = ((0,0), (0,0))
+"""
+Shift the tail one step based on the difference vector
+
+The tail can move up/down, left/right, or diagonally.
+"""
+function shift_tail(diff_vec, head_position, tail_position)
+    tail_position .+ sign.(diff_vec)
+end
+ 
+function move_knots(instructions, num_knots=2)
+    knot_positions = [(0, 0) for _ in 1:num_knots]
     tail_visits = Set{Tuple{Int,Int}}()
-    push!(tail_visits, tail_position)
+    push!(tail_visits, knot_positions[end])
 
     for instruction = instructions
-        direction = instruction[1]
         steps = parse(Int, instruction[3:end])
-        for _ = 1:steps
-            head_position, tail_position = increment_head_tail(
-                head_position,
-                tail_position,
-                direction
+        for _ in 1:steps
+            knot_positions[1] = shift_head(
+                knot_positions[1],
+                instruction[1]
             )
-            push!(tail_visits, tail_position)
+
+            for i = 2:lastindex(knot_positions)
+                aretouching, diff_vec = touching(knot_positions[i-1],
+                                                 knot_positions[i])
+                while !aretouching
+                    knot_positions[i] = shift_tail(diff_vec,
+                                                   knot_positions[i-1],
+                                                   knot_positions[i])
+                    if i == lastindex(knot_positions)
+                        push!(tail_visits, knot_positions[i])
+                    end
+
+                    aretouching, diff_vec = touching(knot_positions[i-1],
+                                                     knot_positions[i])
+                end
+            end
         end
     end
 
@@ -65,13 +79,43 @@ function move_head_tail(instructions)
 end
 
 function part_1(input)
-    length(move_head_tail(input))
+    length(move_knots(input))
 end
 @assert part_1(example) == 13
 @info part_1(input)
 
+# Part 2 stuff below
+
+example2 = readlines(IOBuffer("""
+    R 5
+    U 8
+    L 8
+    D 3
+    R 17
+    D 10
+    L 25
+    U 20"""))
+
+# Looks like I need help: my first attempt worked for the example but not the
+# puzzle input (argh). So here's a helper function to draw the map
+function draw_map(tail_visits)
+    tail_visits = [tup[k] for tup in tail_visits, k in 1:2]
+    tail_visits[:,1] .-= minimum(tail_visits[:,1]) - 1
+    tail_visits[:,2] .-= minimum(tail_visits[:,2]) - 1
+
+    tailmap = fill('.',
+                   maximum(tail_visits[:,2]),
+                   maximum(tail_visits[:,1]))
+    for coord = eachrow(tail_visits)
+        tailmap[coord[2], coord[1]] = '#'
+    end
+
+    println(join(reverse([join(x, "") for x in eachrow(tailmap)]), "\n"))
+end
+
+draw_map(move_knots(example2, 10))
 function part_2(input)
-    nothing
+    length(move_knots(input, 10))
 end
-@assert part_2(example) == nothing
+@assert part_2(example2) == 36
 @info part_2(input)