(in-package :ca.mhcat.advent2022)

;; --- Day 9: Rope Bridge ---

;; This rope bridge creaks as you walk along it. You aren't
;; sure how old it is, or whether it can even support your
;; weight.

;; It seems to support the Elves just fine, though. The
;; bridge spans a gorge which was carved out by the massive
;; river far below you.

;; You step carefully; as you do, the ropes stretch and
;; twist. You decide to distract yourself by modeling rope
;; physics; maybe you can even figure out where not to step.

;; Consider a rope with a knot at each end; these knots mark
;; the head and the tail of the rope. If the head moves far
;; enough away from the tail, the tail is pulled toward the
;; head.

;; Due to nebulous reasoning involving Planck lengths, you
;; should be able to model the positions of the knots on a
;; two-dimensional grid. Then, by following a hypothetical
;; series of motions (your puzzle input) for the head, you
;; can determine how the tail will move.

;; Due to the aforementioned Planck lengths, the rope must
;; be quite short; in fact, the head (H) and tail (T) must
;; always be touching (diagonally adjacent and even
;; overlapping both count as touching):

;; ....
;; .TH.
;; ....

;; ....
;; .H..
;; ..T.
;; ....

;; ...
;; .H. (H covers T)
;; ...

;; If the head is ever two steps directly up, down, left, or
;; right from the tail, the tail must also move one step in
;; that direction so it remains close enough:

;; .....    .....    .....
;; .TH.. -> .T.H. -> ..TH.
;; .....    .....    .....

;; ...    ...    ...
;; .T.    .T.    ...
;; .H. -> ... -> .T.
;; ...    .H.    .H.
;; ...    ...    ...

;; Otherwise, if the head and tail aren't touching and
;; aren't in the same row or column, the tail always moves
;; one step diagonally to keep up:

;; .....    .....    .....
;; .....    ..H..    ..H..
;; ..H.. -> ..... -> ..T..
;; .T...    .T...    .....
;; .....    .....    .....

;; .....    .....    .....
;; .....    .....    .....
;; ..H.. -> ...H. -> ..TH.
;; .T...    .T...    .....
;; .....    .....    .....

;; You just need to work out where the tail goes as the head
;; follows a series of motions. Assume the head and the tail
;; both start at the same position, overlapping.

;; For example:

;; R 4
;; U 4
;; L 3
;; D 1
;; R 4
;; D 1
;; L 5
;; R 2

(defparameter day9/test-data
 '("R 4"
   "U 4"
   "L 3"
   "D 1"
   "R 4"
   "D 1"
   "L 5"
   "R 2"))

(defun day9/parse-data (lines)
 (mapcar (lambda (line)
           (with-input-from-string (s line)
             (list (read s) (read s))))
         lines))

;; This series of motions moves the head right four steps,
;; then up four steps, then left three steps, then down one
;; step, and so on. After each step, you'll need to update
;; the position of the tail if the step means the head is no
;; longer adjacent to the tail. Visually, these motions
;; occur as follows (s marks the starting position as a
;; reference point):

;; == Initial State ==

;; ......
;; ......
;; ......
;; ......
;; H.....  (H covers T, s)

;; == R 4 ==

;; ......
;; ......
;; ......
;; ......
;; TH....  (T covers s)

;; ......
;; ......
;; ......
;; ......
;; sTH...

;; ......
;; ......
;; ......
;; ......
;; s.TH..

;; ......
;; ......
;; ......
;; ......
;; s..TH.

;; == U 4 ==

;; ......
;; ......
;; ......
;; ....H.
;; s..T..

;; ......
;; ......
;; ....H.
;; ....T.
;; s.....

;; ......
;; ....H.
;; ....T.
;; ......
;; s.....

;; ....H.
;; ....T.
;; ......
;; ......
;; s.....

;; == L 3 ==

;; ...H..
;; ....T.
;; ......
;; ......
;; s.....

;; ..HT..
;; ......
;; ......
;; ......
;; s.....

;; .HT...
;; ......
;; ......
;; ......
;; s.....

;; == D 1 ==

;; ..T...
;; .H....
;; ......
;; ......
;; s.....

;; == R 4 ==

;; ..T...
;; ..H...
;; ......
;; ......
;; s.....

;; ..T...
;; ...H..
;; ......
;; ......
;; s.....

;; ......
;; ...TH.
;; ......
;; ......
;; s.....

;; ......
;; ....TH
;; ......
;; ......
;; s.....

;; == D 1 ==

;; ......
;; ....T.
;; .....H
;; ......
;; s.....

;; == L 5 ==

;; ......
;; ....T.
;; ....H.
;; ......
;; s.....

;; ......
;; ....T.
;; ...H..
;; ......
;; s.....

;; ......
;; ......
;; ..HT..
;; ......
;; s.....

;; ......
;; ......
;; .HT...
;; ......
;; s.....

;; ......
;; ......
;; HT....
;; ......
;; s.....

;; == R 2 ==

;; ......
;; ......
;; .H....  (H covers T)
;; ......
;; s.....

;; ......
;; ......
;; .TH...
;; ......
;; s.....

;; After simulating the rope, you can count up all of the
;; positions the tail visited at least once. In this
;; diagram, s again marks the starting position (which the
;; tail also visited) and # marks other positions the tail
;; visited:

;; ..##..
;; ...##.
;; .####.
;; ....#.
;; s###..

;; So, there are 13 positions the tail visited at least
;; once.

;; Simulate your complete hypothetical series of motions.
;; How many positions does the tail of the rope visit at
;; least once?

(defun day9/move-one (delta n)
 (cond
   ((minusp delta) (1- n))
   ((plusp delta) (1+ n))
   ((zerop delta) n)
   (t (error "poop"))))

(defun day9/move-tail (new-state old-state)
 (destructuring-bind ((hdx hdy) (tlx tly) &rest rest) old-state
   (let* ((xdelta (- hdx tlx))
          (ydelta (- hdy tly))
          (new-tl-hd
            (if (and (<= (abs xdelta) 1) (<= (abs ydelta) 1))
                ;; do nothing case
                (list tlx tly)
                ;; distance can only be 2
                (list (day9/move-one xdelta tlx) (day9/move-one ydelta tly))))
          (new-state (cons new-tl-hd new-state)))
     (if rest
         (day9/move-tail new-state (cons new-tl-hd rest))
         (nreverse new-state)))))

(defun day9/next-state (move state)
 (destructuring-bind ((hdx hdy) &rest rest) state
   (let* ((delta (case move ((r u) 1) ((l d) -1)))
          (new-hd (case move
                    ((l r) (list (+ delta hdx) hdy))
                    ((u d) (list hdx (+ delta hdy))))))
     (day9/move-tail (list new-hd) (cons new-hd rest)))))

(defun day9/compute-one-instruction (inst initial-state)
 (destructuring-bind (direction n) inst
   (do ((batch nil)
        (state initial-state (day9/next-state direction state))
        (counter (1+ n) (1- counter)))
       ((zerop counter) batch)
     (push state batch))))

(defun day9/compute-part1 (knot-count lst)
 (let ((instructions (day9/parse-data lst))
       (tl-places (list '(0 0))))
   (reduce (lambda (state inst)
             (let ((batch (day9/compute-one-instruction inst state)))
               (loop for next in batch
                     do (pushnew (car (reverse next)) tl-places :test #'equal))
               (car batch)))
           instructions
           :initial-value (make-list knot-count :initial-element (list 0 0)))
   (length tl-places)))

(defun day9/part1 ()
 (day9/compute-part1
  2
  (load-lines "day9.txt")))

;; --- Part Two ---

;; A rope snaps! Suddenly, the river is getting a lot closer
;; than you remember. The bridge is still there, but some of
;; the ropes that broke are now whipping toward you as you
;; fall through the air!

;; The ropes are moving too quickly to grab; you only have a
;; few seconds to choose how to arch your body to avoid
;; being hit. Fortunately, your simulation can be extended
;; to support longer ropes.

;; Rather than two knots, you now must simulate a rope
;; consisting of ten knots. One knot is still the head of
;; the rope and moves according to the series of motions.
;; Each knot further down the rope follows the knot in front
;; of it using the same rules as before.

;; Using the same series of motions as the above example,
;; but with the knots marked H, 1, 2, ..., 9, the motions
;; now occur as follows:

;; == Initial State ==

;; ......
;; ......
;; ......
;; ......
;; H.....  (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s)

;; == R 4 ==

;; ......
;; ......
;; ......
;; ......
;; 1H....  (1 covers 2, 3, 4, 5, 6, 7, 8, 9, s)

;; ......
;; ......
;; ......
;; ......
;; 21H...  (2 covers 3, 4, 5, 6, 7, 8, 9, s)

;; ......
;; ......
;; ......
;; ......
;; 321H..  (3 covers 4, 5, 6, 7, 8, 9, s)

;; ......
;; ......
;; ......
;; ......
;; 4321H.  (4 covers 5, 6, 7, 8, 9, s)

;; == U 4 ==

;; ......
;; ......
;; ......
;; ....H.
;; 4321..  (4 covers 5, 6, 7, 8, 9, s)

;; ......
;; ......
;; ....H.
;; .4321.
;; 5.....  (5 covers 6, 7, 8, 9, s)

;; ......
;; ....H.
;; ....1.
;; .432..
;; 5.....  (5 covers 6, 7, 8, 9, s)

;; ....H.
;; ....1.
;; ..432.
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == L 3 ==

;; ...H..
;; ....1.
;; ..432.
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ..H1..
;; ...2..
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; .H1...
;; ...2..
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == D 1 ==

;; ..1...
;; .H.2..
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == R 4 ==

;; ..1...
;; ..H2..
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ..1...
;; ...H..  (H covers 2)
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ...1H.  (1 covers 2)
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ...21H
;; ..43..
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == D 1 ==

;; ......
;; ...21.
;; ..43.H
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == L 5 ==

;; ......
;; ...21.
;; ..43H.
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ...21.
;; ..4H..  (H covers 3)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ...2..
;; ..H1..  (H covers 4; 1 covers 3)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ...2..
;; .H13..  (1 covers 4)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ......
;; H123..  (2 covers 4)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; == R 2 ==

;; ......
;; ......
;; .H23..  (H covers 1; 2 covers 4)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; ......
;; ......
;; .1H3..  (H covers 2, 4)
;; .5....
;; 6.....  (6 covers 7, 8, 9, s)

;; Now, you need to keep track of the positions the new
;; tail, 9, visits. In this example, the tail never moves,
;; and so it only visits 1 position. However, be careful:
;; more types of motion are possible than before, so you
;; might want to visually compare your simulated rope to the
;; one above.

;; Here's a larger example:

;; R 5
;; U 8
;; L 8
;; D 3
;; R 17
;; D 10
;; L 25
;; U 20

(defparameter day9/test-data2
 '("R 5"
   "U 8"
   "L 8"
   "D 3"
   "R 17"
   "D 10"
   "L 25"
   "U 20"))

;; These motions occur as follows (individual steps are not
;; shown):

;; == Initial State ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........H..............  (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s)
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == R 5 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........54321H.........  (5 covers 6, 7, 8, 9, s)
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == U 8 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ................H.........
;; ................1.........
;; ................2.........
;; ................3.........
;; ...............54.........
;; ..............6...........
;; .............7............
;; ............8.............
;; ...........9..............  (9 covers s)
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == L 8 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ........H1234.............
;; ............5.............
;; ............6.............
;; ............7.............
;; ............8.............
;; ............9.............
;; ..........................
;; ..........................
;; ...........s..............
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == D 3 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; .........2345.............
;; ........1...6.............
;; ........H...7.............
;; ............8.............
;; ............9.............
;; ..........................
;; ..........................
;; ...........s..............
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == R 17 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ................987654321H
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........s..............
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; == D 10 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........s.........98765
;; .........................4
;; .........................3
;; .........................2
;; .........................1
;; .........................H

;; == L 25 ==

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........s..............
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; H123456789................

;; == U 20 ==

;; H.........................
;; 1.........................
;; 2.........................
;; 3.........................
;; 4.........................
;; 5.........................
;; 6.........................
;; 7.........................
;; 8.........................
;; 9.........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ...........s..............
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................

;; Now, the tail (9) visits 36 positions (including s) at
;; least once:

;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; ..........................
;; #.........................
;; #.............###.........
;; #............#...#........
;; .#..........#.....#.......
;; ..#..........#.....#......
;; ...#........#.......#.....
;; ....#......s.........#....
;; .....#..............#.....
;; ......#............#......
;; .......#..........#.......
;; ........#........#........
;; .........########.........

;; Simulate your complete series of motions on a larger rope
;; with ten knots. How many positions does the tail of the
;; rope visit at least once?

(defun day9/part2 ()
 (day9/compute-part1
  10
  (load-lines "day9.txt")))

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.