day09.lisp

(in-package #:advent-of-code-2022.day09)

(defparameter *input*
  "U 1
R 2
D 2
U 2
L 1
U 1
R 1
U 2
R 1
D 1
U 2
L 1
R 1
U 1
L 1
D 1
L 1
D 1
U 2
R 2
U 1
L 1
R 2
U 2
L 2
U 2
R 2
D 2
R 1
U 2
L 2
U 1
R 1
L 2
U 2
R 2
L 1
R 2
L 1
D 1
R 2
L 2
D 2
L 1
D 1
L 2
U 1
R 2
L 2
U 2
D 2
R 2
D 2
L 2
D 2
L 1
D 2
L 1
R 2
L 2
R 1
D 2
U 1
R 2
L 1
R 2
D 1
U 1
R 1
U 2
D 2
R 1
D 1
U 1
L 2
D 2
U 1
R 2
L 2
R 1
D 2
L 1
U 1
D 1
U 2
D 1
U 1
D 2
R 2
L 1
D 1
U 1
R 1
L 2
D 1
L 2
R 1
L 2
U 2
R 1
L 2
D 2
L 2
U 2
L 1
U 2
R 2
L 2
R 2
L 2
U 1
L 1
U 1
D 1
U 3
R 2
L 3
R 2
D 2
U 3
R 1
L 3
D 1
U 3
R 2
D 1
U 3
R 2
L 3
R 3
L 2
R 1
U 2
R 2
U 3
D 1
U 3
L 2
D 1
R 2
U 3
R 3
L 3
D 3
R 3
U 3
L 3
U 1
L 2
U 3
L 1
U 1
D 3
R 3
U 1
R 1
U 1
L 3
R 2
U 2
L 3
D 1
L 2
D 2
L 2
R 2
U 3
D 3
R 2
U 3
L 2
U 1
D 2
R 3
L 1
U 1
R 2
D 3
L 1
R 1
U 1
D 3
R 2
D 3
R 2
U 1
L 2
U 1
R 2
U 1
R 2
L 2
U 2
R 3
L 3
D 2
L 1
R 3
D 1
U 1
L 2
R 1
D 3
U 3
D 3
U 1
R 2
L 3
R 1
L 3
R 2
D 2
U 1
D 1
L 3
R 1
L 3
R 3
L 1
D 2
L 3
U 2
D 1
L 1
U 2
R 3
L 2
R 3
U 3
L 2
D 4
U 4
R 3
U 2
L 1
U 3
D 4
L 2
U 3
L 4
D 4
R 3
D 3
R 1
D 2
L 1
R 2
D 3
L 1
R 2
U 3
D 4
R 4
L 2
R 4
U 3
R 4
U 4
L 4
D 3
R 4
D 1
U 3
L 3
R 1
U 2
R 3
U 4
D 2
U 3
D 2
L 2
D 3
L 4
R 2
U 2
L 2
U 4
D 2
U 4
L 4
U 2
R 3
D 4
U 4
L 3
D 3
R 4
L 3
R 2
L 4
U 3
D 2
L 4
R 1
U 2
L 3
D 1
R 2
U 2
D 4
R 1
U 1
R 2
D 2
L 3
R 1
U 2
R 1
D 4
U 1
R 1
U 3
D 1
U 2
D 3
U 3
L 2
U 4
R 1
L 2
D 2
L 2
D 3
U 3
L 3
U 1
D 1
R 1
D 2
L 2
U 2
D 3
R 1
L 4
U 3
L 5
R 5
L 4
D 4
R 4
L 4
R 4
L 2
R 3
D 3
R 2
L 4
R 2
U 5
D 5
U 1
R 4
U 2
R 3
L 4
D 2
U 3
D 4
U 2
D 5
L 5
R 2
U 3
R 1
D 1
R 4
U 5
R 3
L 3
U 3
L 1
U 5
D 2
U 3
R 1
D 5
L 4
U 3
D 1
L 3
R 2
U 1
L 2
R 2
D 4
R 2
L 3
U 2
D 1
L 1
R 4
L 1
D 2
R 1
L 5
R 4
U 2
R 2
U 1
D 3
R 3
L 1
U 5
R 2
D 3
U 3
R 1
U 4
R 1
D 2
L 1
D 4
L 1
R 5
L 5
R 5
L 1
U 5
R 2
U 5
L 2
D 3
U 5
L 4
D 5
U 2
R 2
D 2
R 4
L 4
D 5
R 2
L 2
R 5
U 2
L 1
U 2
D 2
R 5
U 1
L 5
R 1
L 4
D 4
L 3
D 4
U 2
L 2
D 5
U 4
R 3
L 6
D 3
R 2
U 2
L 2
U 1
R 6
U 5
R 2
U 2
R 1
U 5
L 3
U 2
R 5
L 3
U 3
D 2
U 5
L 5
U 4
R 6
D 2
L 6
U 1
L 5
D 4
U 3
D 3
U 5
L 6
U 4
D 3
U 4
D 6
R 1
U 4
L 1
D 4
U 5
R 2
L 3
R 2
U 2
D 1
L 3
R 6
L 2
U 5
L 3
D 1
L 2
D 4
U 4
L 4
D 1
L 2
D 2
R 5
L 2
R 2
L 3
R 2
U 2
L 1
U 4
D 4
R 5
L 3
U 2
D 3
R 6
D 3
R 3
L 4
U 5
D 3
R 5
U 4
R 2
U 4
L 1
U 6
D 6
L 1
R 2
U 6
D 5
L 1
U 3
L 1
D 6
L 3
U 4
D 6
U 4
D 3
L 3
U 5
R 2
L 5
D 3
R 2
D 2
U 1
D 2
R 2
U 5
R 4
U 1
R 5
D 2
R 2
U 5
L 6
U 3
L 7
D 1
R 4
D 4
R 7
L 7
U 7
D 4
L 4
R 6
U 6
L 7
R 3
L 6
U 6
R 5
D 4
L 6
U 1
R 6
D 3
U 5
D 3
U 2
R 7
U 5
D 5
L 2
D 2
U 4
L 3
D 1
L 1
R 2
L 2
R 6
D 4
L 7
D 7
R 4
L 6
R 3
L 3
U 7
R 3
L 5
D 6
R 3
U 5
D 3
L 4
U 7
R 6
D 6
U 5
R 3
L 3
R 6
L 3
D 1
L 3
U 5
D 2
L 3
R 4
L 7
R 5
U 3
L 7
D 5
U 6
D 5
L 6
R 6
L 1
R 3
D 4
L 5
R 2
U 4
R 2
D 4
R 3
D 2
L 3
R 2
L 4
R 5
U 7
L 7
D 3
R 5
L 1
U 4
R 5
U 4
R 6
L 1
R 4
D 8
L 2
U 7
L 3
R 3
U 1
D 8
U 5
D 3
R 3
L 2
U 2
D 8
R 3
U 4
L 6
D 7
R 7
U 6
L 7
U 5
R 1
L 2
U 4
D 1
L 6
D 5
R 7
U 7
R 8
L 7
U 7
D 3
L 3
D 4
L 1
R 6
D 5
U 1
D 8
R 1
L 2
U 1
D 2
L 3
R 7
L 2
D 8
R 5
U 6
D 4
L 1
U 6
R 1
D 4
R 4
L 2
D 4
R 1
U 2
R 8
L 6
R 8
U 8
L 3
R 6
D 3
R 2
L 3
U 6
D 6
U 4
R 7
L 3
R 2
L 4
U 3
R 7
D 8
R 1
D 6
U 7
R 2
U 2
L 6
U 5
R 1
D 1
R 6
L 2
U 3
D 2
L 2
D 5
R 4
L 1
D 7
R 6
D 4
U 2
D 5
U 3
D 8
U 6
R 5
L 6
U 7
L 3
R 8
U 3
L 2
R 3
L 5
R 3
L 2
U 9
D 2
U 5
R 7
U 9
L 9
R 6
L 7
D 1
L 4
D 3
R 7
L 6
R 9
D 6
R 4
D 8
L 1
U 5
R 9
D 9
U 6
L 5
R 4
D 2
R 5
D 1
R 6
D 3
R 8
L 1
U 2
R 5
U 3
L 1
R 8
D 6
L 5
D 7
R 3
U 2
L 7
U 3
D 4
L 2
R 8
D 6
L 3
U 5
L 1
U 5
L 4
R 7
U 6
R 1
D 3
U 3
D 2
R 4
L 5
U 2
R 6
L 8
U 6
L 9
D 3
R 3
U 9
D 8
L 2
R 7
D 6
R 1
D 8
U 8
D 2
U 4
D 8
L 9
R 8
D 8
R 7
U 8
L 8
U 8
R 7
L 8
U 3
D 6
R 7
D 2
L 5
U 8
D 7
U 6
R 3
D 7
U 9
L 7
R 3
L 1
U 9
L 7
U 2
D 7
L 5
R 9
D 2
R 7
U 6
D 7
U 3
R 8
U 9
L 8
R 8
D 10
L 7
R 3
U 5
R 5
D 9
U 10
L 2
D 4
L 2
U 1
D 3
L 3
U 7
D 6
L 6
D 7
L 8
U 1
D 9
L 7
U 4
L 3
U 6
D 2
L 5
U 10
D 9
U 8
D 1
R 10
U 4
L 1
R 7
U 2
L 5
D 5
R 7
D 1
R 4
U 2
D 6
L 7
U 10
R 3
L 9
D 7
L 2
R 5
U 10
D 10
R 9
D 5
U 3
L 7
D 5
U 6
D 7
L 6
D 10
R 7
U 8
L 4
D 9
L 4
U 5
R 9
U 9
R 3
U 2
R 2
D 1
R 1
U 6
R 8
D 10
U 2
D 9
L 8
R 1
D 1
L 9
R 8
D 9
R 5
L 9
U 10
D 4
R 7
U 4
L 3
U 8
L 2
U 9
D 9
L 1
R 4
U 2
L 4
U 3
D 7
U 11
R 6
U 9
D 6
R 7
L 1
D 7
R 2
D 6
U 2
L 2
U 4
R 6
U 6
L 11
D 7
R 9
L 2
D 10
L 10
U 4
L 6
D 11
U 9
L 1
R 10
L 7
R 4
D 5
L 3
U 2
R 9
L 9
D 1
L 11
D 5
U 6
D 5
U 9
R 1
L 7
U 3
R 7
L 2
D 6
R 3
U 2
D 5
R 9
L 3
D 11
U 9
D 11
R 2
D 7
R 9
U 4
D 6
U 7
R 10
D 3
L 4
R 9
D 3
L 7
R 7
L 11
D 6
R 9
D 9
R 3
U 3
R 3
L 6
D 11
R 2
L 10
U 2
R 2
D 11
R 7
D 8
R 2
D 10
U 5
D 3
L 10
R 1
D 5
R 4
L 10
U 5
D 9
U 2
L 3
U 3
R 5
D 4
L 1
D 1
R 10
L 4
D 8
L 5
D 5
L 3
D 5
L 3
R 1
L 3
R 4
U 9
R 4
D 12
L 5
R 4
L 11
D 10
U 3
R 2
U 5
L 6
D 5
U 5
D 10
R 12
L 2
R 10
D 11
R 12
U 5
R 4
L 4
U 2
R 12
L 6
D 3
R 2
D 1
U 9
L 6
U 6
L 10
D 8
R 9
L 1
U 1
D 5
U 4
R 10
U 5
R 10
D 12
U 6
D 9
U 3
L 8
R 8
D 7
L 6
U 7
R 1
U 6
D 9
R 2
U 11
D 7
L 12
D 6
L 5
U 8
R 8
L 8
D 3
R 7
L 11
D 1
L 5
D 5
U 8
D 2
R 8
L 6
D 7
L 3
D 3
U 9
L 1
U 8
D 7
L 8
U 4
R 12
U 7
L 10
D 4
U 7
D 7
U 5
L 4
R 9
D 5
R 4
U 2
R 1
D 9
U 7
R 9
U 12
D 4
R 8
U 4
D 10
L 10
D 11
L 8
R 11
U 5
D 4
L 3
D 1
U 7
L 5
R 13
L 2
R 9
L 6
R 6
L 2
U 10
D 11
U 13
R 11
U 6
L 7
D 11
R 7
U 4
L 1
D 9
R 7
L 11
U 13
L 8
R 12
U 5
R 9
U 11
R 3
D 11
U 9
L 8
U 6
D 6
L 11
U 4
D 3
U 11
D 1
L 6
U 5
R 10
L 10
R 8
L 12
R 4
U 3
R 8
L 8
U 4
L 10
U 9
R 8
U 3
D 2
U 4
D 10
L 6
R 10
U 8
L 9
R 13
D 8
U 10
D 10
L 13
U 1
R 4
U 11
D 12
L 1
R 2
U 12
D 7
U 9
R 13
U 5
D 6
R 4
L 6
U 9
L 5
U 8
D 4
L 5
U 6
L 8
U 1
R 3
U 8
R 2
D 5
U 12
D 9
L 2
U 3
R 11
U 9
R 7
D 10
U 2
L 3
D 3
U 9
D 6
U 1
R 9
L 5
R 2
L 2
R 11
D 7
L 10
U 13
L 6
R 11
U 6
D 11
U 4
R 10
D 5
R 4
L 6
U 3
L 8
D 6
U 14
R 3
U 1
L 6
R 7
U 9
L 9
D 10
U 10
D 12
R 9
D 12
R 4
D 12
U 9
R 9
U 2
L 11
D 13
U 12
L 7
D 14
R 4
D 14
U 11
D 5
R 10
L 2
D 11
L 3
U 9
R 4
L 8
U 8
R 7
U 7
D 5
R 8
U 5
L 3
R 7
D 6
R 12
U 3
D 8
L 8
U 3
L 8
R 7
L 13
U 2
L 8
U 14
R 5
L 1
D 14
R 10
U 14
R 6
U 14
D 5
U 13
D 1
U 12
R 7
L 2
U 4
R 10
U 8
R 12
L 2
U 7
D 9
L 6
D 3
U 7
L 11
U 8
R 7
D 5
U 5
R 13
D 9
R 14
U 8
R 14
D 8
U 1
L 13
R 12
D 7
L 6
R 3
D 10
R 10
L 6
D 12
L 5
U 14
D 1
U 8
R 5
D 15
R 11
D 10
L 11
D 13
L 5
D 3
U 15
R 6
L 12
R 12
L 15
U 5
D 8
R 13
D 10
R 4
L 6
U 8
R 6
D 15
U 6
L 13
D 15
U 11
D 6
U 7
L 1
R 5
L 1
U 7
D 15
L 1
D 7
U 6
R 14
D 4
R 5
U 4
D 5
R 13
D 5
L 1
D 11
L 3
D 3
R 13
L 15
D 4
R 4
U 5
L 10
U 14
D 2
R 9
U 8
R 1
U 13
L 5
U 12
R 10
U 8
L 9
D 7
R 10
L 8
R 13
D 12
L 2
R 4
D 14
R 14
D 2
U 4
D 14
U 1
L 3
R 7
L 2
D 10
R 10
L 1
R 5
D 6
L 5
R 11
U 15
L 6
D 4
R 14
D 6
R 1
L 12
R 15
L 10
U 1
D 3
R 2
D 2
L 8
U 9
D 14
L 4
R 2
U 14
L 11
D 12
U 5
L 11
R 5
U 14
R 9
U 12
L 12
D 9
R 10
D 4
L 3
U 4
R 2
D 9
U 5
L 13
U 5
R 15
L 4
R 10
U 8
R 3
U 13
D 4
U 4
L 8
U 1
D 13
R 10
U 13
L 5
U 7
D 2
U 15
R 10
U 12
D 9
R 12
L 3
D 7
R 7
L 3
R 14
L 9
D 4
R 8
D 1
R 1
U 1
R 14
L 7
R 10
D 14
L 1
U 12
D 8
U 1
R 13
U 12
D 4
U 8
L 8
D 8
L 4
R 2
D 6
R 2
L 3
D 16
R 6
L 16
D 16
L 2
R 16
D 15
L 1
D 4
U 3
L 5
U 4
L 4
D 9
L 2
R 8
D 7
U 7
R 12
U 12
R 3
D 8
L 12
D 12
R 13
U 8
R 5
U 2
D 3
U 11
L 13
R 4
L 5
R 9
D 9
U 14
R 15
L 16
R 13
D 11
U 13
L 10
D 11
L 10
R 4
U 7
D 17
U 7
R 10
U 11
L 2
D 8
U 3
R 14
U 13
D 8
U 6
L 2
D 9
L 1
D 4
U 16
D 4
L 13
U 1
D 13
U 12
R 17
L 6
R 17
L 17
R 13
L 9
U 12
L 15
R 17
U 3
R 2
L 12
U 7
L 12
U 9
L 15
R 9
U 3
L 13
R 8
L 3
R 2
L 17
U 14
D 16
L 13
D 2
U 17
D 6
U 8
L 5
D 10
L 3
D 3
R 7
L 16
R 8
U 13
L 17
U 16
L 9
U 8
D 12
R 10
U 11
D 10
L 17
R 3
D 7
U 13
D 11
R 7
D 16
U 4
R 12
D 12
U 11
D 2
L 9
D 6
L 4
R 5
L 13
U 7
L 12
D 1
L 15
U 8
R 4
U 15
R 15
D 7
R 8
U 9
R 5
D 12
R 12
U 2
D 13
U 2
L 6
D 8
U 12
R 6
D 16
U 4
R 9
L 6
U 18
L 7
R 15
U 8
D 18
L 11
R 16
D 2
R 7
D 8
L 10
U 15
L 13
D 7
R 13
D 14
R 2
L 14
D 4
L 10
R 13
L 18
U 15
L 17
R 18
D 2
U 7
R 18
D 4
L 1
U 12
L 1
U 16
D 6
R 7
U 9
L 1
U 13
R 2
L 8
D 5
R 18
D 16
R 8
D 2
R 13
L 16
R 18
L 10
D 6
U 4
D 15
U 3
D 9
R 17
D 8
L 4
R 17
D 15
R 1
D 18
U 1
R 5
L 7
D 18
U 16
D 2
L 11
R 7
L 12
D 2
U 8
L 17
U 18
L 10
R 16
L 5
R 1
L 10
R 14
L 4
D 15
R 8
D 15
L 12
D 5
U 11
L 1
R 8
D 11
U 5
L 12
D 11
U 9
D 12
R 7
D 11
U 2
R 15
L 2
R 8
U 2
D 8
R 14
L 4
D 1
U 4
R 4
D 2
R 5
D 9
L 10
U 8
R 13
D 15
R 18
D 5
U 5
L 1
U 1
R 9
D 2
U 6
R 5
U 5
R 17
L 2
D 1
R 3
D 5
U 13
R 10
D 10
R 13
D 5
L 1
U 14
D 17
U 15
R 16
L 9
U 12
L 17
R 19
U 1
D 4
U 14
L 7
R 16
L 5
D 4
L 14
U 13
R 10
L 19
D 1
R 17
D 6
L 19
U 11
L 14
U 15
D 10
U 17
R 16
U 12
L 13
D 1
R 11
D 10
L 4
D 15
L 18
R 2
U 5
L 2
U 9
D 16
R 8
D 13
R 19
U 14
L 10
R 13
U 3
R 2
U 11
L 2
R 2
U 12
L 14
U 15
R 6
D 10
R 8
U 14
D 9
L 2
U 3
D 8
U 7
R 10
U 16
R 3
U 9
L 16
D 1
R 1
U 12
R 12
U 8
L 19
U 14
R 9
U 5
L 15
U 7
L 17
U 16
R 19
U 17
L 1
D 7")

(defparameter *input-test*
  "R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2")

(defparameter *input-test-2*
  "R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20")

(defun dir-to-coord (dir)
  (ecase (alexandria:make-keyword dir)
    (:U '(0 . 1))
    (:D '(0 . -1))
    (:R '(1 . 0))
    (:L '(-1 . 0))))

(defun process-input (input)
  (loop
    for (dir mag) on (cl-ppcre::split "\\s+" input) by #'cddr
    for steps = (parse-integer mag)
    for delta = (dir-to-coord dir) 
    append (loop repeat steps collect delta)))

(defun advance-tail (head tail)
  (let* ((hx (car head))
	 (hy (cdr head))
	 (tx (car tail))
	 (ty (cdr tail))
	 (dx (- hx tx))
	 (dy (- hy ty)))
    (cond
      ((and (= (abs dx) 2) (= (abs dy) 2))
       (cons (+ tx (/ dx (abs dx))) (+ ty (/ dy (abs dy)))))
      ((and (= (abs dx) 2) (= (abs dy) 1))
       (cons (+ tx (/ dx (abs dx))) (+ ty dy)))
      ((and (= (abs dx) 1) (= (abs dy) 2))
       (cons (+ tx dx) (+ ty (/ dy (abs dy)))))
      ((= (abs dx) 2)
       (cons (+ tx (/ dx (abs dx))) ty))
      ((= (abs dy) 2)
       (cons tx (+ ty (/ dy (abs dy)))))
      (t tail))))

(defun puzzle-01 (&key (input *input*))
  (loop
    with visited = (make-hash-table :test #'equal)
    with (head tail) = (copy-tree '((0 . 0) (0 . 0))) ;; Initial coordinates of head and tail
      initially (setf (gethash '(0 . 0) visited) t)
    for (dx . dy) in (process-input input)
    do (incf (car head) dx)
       (incf (cdr head) dy)
       (setf tail (advance-tail head tail))
       (setf (gethash tail visited) t)
    finally (return (hash-table-count visited))))

(defun advance-segments (coords)
  (loop
    for head = (car coords) then tail
    for tail in (cdr coords)
    do (setf tail (advance-tail head tail))
    collect tail into c
    finally (return (cons (car coords) c))
    ))

(defun puzzle-02 (&key (input *input*))
  (loop
    with visited = (make-hash-table :test #'equal)
      initially (setf (gethash '(0 . 0) visited) t)
    with coords = (loop repeat 10 collect (cons 0 0))
    for (dx . dy) in (process-input input)
    for head = (car coords)
    do (incf (car head) dx)
       (incf (cdr head) dy)
       (setf coords (advance-segments coords))
       (setf (gethash (car (last coords)) visited) t)
    finally (return (hash-table-count visited))))