commit 116f264f2da99e9881ac58ba4954afb454dae962
parent 635f4be6dcc2a8cc558e852cccbaf5657fe96928
Author: Lukas Henkel <lh@entf.net>
Date: Mon, 5 Dec 2022 18:37:48 +0100
Day 5
Diffstat:
4 files changed, 613 insertions(+), 3 deletions(-)
diff --git a/adventofcode2022.asd b/adventofcode2022.asd
@@ -5,11 +5,13 @@
:licence "AGPLv3"
:serial t
:pathname "src"
- :depends-on ("trivia")
+ :depends-on ("trivia" "str")
:components ((:file "main")
(:file "day01")
(:file "day02")
- (:file "day03")))
+ (:file "day03")
+ (:file "day04")
+ (:file "day05")))
(defsystem "adventofcode2022/test"
:description "My solutions to the advent of code 2022"
@@ -22,4 +24,6 @@
:components ((:file "package")
(:file "day01")
(:file "day02")
- (:file "day03")))
+ (:file "day03")
+ (:file "day04")
+ (:file "day05")))
diff --git a/input/day05.txt b/input/day05.txt
@@ -0,0 +1,511 @@
+[V] [B] [C]
+[C] [N] [G] [W] [P]
+[W] [C] [Q] [S] [C] [M]
+[L] [W] [B] [Z] [F] [S] [V]
+[R] [G] [H] [F] [P] [V] [M] [T]
+[M] [L] [R] [D] [L] [N] [P] [D] [W]
+[F] [Q] [S] [C] [G] [G] [Z] [P] [N]
+[Q] [D] [P] [L] [V] [D] [D] [C] [Z]
+ 1 2 3 4 5 6 7 8 9
+
+move 1 from 9 to 2
+move 4 from 6 to 1
+move 4 from 2 to 6
+move 5 from 8 to 7
+move 4 from 9 to 2
+move 1 from 5 to 8
+move 1 from 3 to 1
+move 2 from 3 to 1
+move 1 from 4 to 2
+move 11 from 7 to 2
+move 5 from 5 to 1
+move 1 from 6 to 8
+move 1 from 7 to 6
+move 3 from 6 to 7
+move 1 from 3 to 2
+move 1 from 6 to 8
+move 11 from 2 to 1
+move 1 from 9 to 8
+move 1 from 3 to 7
+move 4 from 7 to 9
+move 3 from 3 to 7
+move 4 from 8 to 2
+move 3 from 7 to 6
+move 2 from 6 to 3
+move 5 from 4 to 1
+move 1 from 6 to 5
+move 26 from 1 to 7
+move 1 from 4 to 6
+move 22 from 7 to 5
+move 4 from 9 to 1
+move 3 from 7 to 3
+move 1 from 6 to 3
+move 6 from 1 to 7
+move 2 from 7 to 5
+move 8 from 1 to 9
+move 4 from 3 to 4
+move 10 from 2 to 7
+move 6 from 7 to 4
+move 2 from 9 to 5
+move 1 from 5 to 1
+move 8 from 4 to 1
+move 2 from 5 to 9
+move 1 from 3 to 6
+move 1 from 9 to 1
+move 1 from 3 to 6
+move 2 from 5 to 2
+move 1 from 4 to 2
+move 1 from 2 to 3
+move 7 from 1 to 4
+move 9 from 7 to 4
+move 1 from 3 to 4
+move 2 from 2 to 4
+move 5 from 9 to 6
+move 1 from 4 to 5
+move 2 from 9 to 3
+move 1 from 1 to 6
+move 2 from 6 to 1
+move 2 from 6 to 5
+move 2 from 9 to 7
+move 1 from 3 to 9
+move 1 from 9 to 5
+move 2 from 7 to 3
+move 1 from 1 to 7
+move 7 from 4 to 5
+move 2 from 1 to 2
+move 3 from 3 to 8
+move 3 from 8 to 9
+move 31 from 5 to 8
+move 1 from 7 to 1
+move 1 from 2 to 1
+move 1 from 1 to 5
+move 1 from 5 to 6
+move 2 from 5 to 7
+move 10 from 4 to 9
+move 5 from 6 to 2
+move 3 from 2 to 6
+move 2 from 7 to 8
+move 1 from 6 to 3
+move 1 from 4 to 1
+move 1 from 3 to 6
+move 1 from 4 to 2
+move 2 from 1 to 2
+move 1 from 8 to 7
+move 10 from 8 to 2
+move 13 from 2 to 9
+move 1 from 1 to 5
+move 18 from 8 to 2
+move 21 from 9 to 6
+move 1 from 7 to 8
+move 2 from 9 to 7
+move 1 from 2 to 3
+move 1 from 7 to 8
+move 9 from 2 to 4
+move 1 from 7 to 8
+move 3 from 9 to 1
+move 1 from 8 to 1
+move 6 from 2 to 3
+move 5 from 4 to 7
+move 1 from 5 to 8
+move 2 from 4 to 3
+move 5 from 7 to 3
+move 2 from 2 to 7
+move 15 from 6 to 1
+move 12 from 1 to 2
+move 6 from 2 to 9
+move 4 from 9 to 5
+move 4 from 5 to 6
+move 14 from 3 to 9
+move 1 from 6 to 7
+move 1 from 7 to 2
+move 1 from 7 to 8
+move 9 from 2 to 6
+move 1 from 1 to 6
+move 2 from 9 to 8
+move 4 from 9 to 7
+move 1 from 1 to 5
+move 8 from 8 to 3
+move 1 from 5 to 4
+move 2 from 1 to 2
+move 3 from 1 to 4
+move 9 from 6 to 2
+move 1 from 7 to 4
+move 1 from 8 to 2
+move 1 from 6 to 4
+move 4 from 7 to 8
+move 12 from 6 to 8
+move 3 from 2 to 1
+move 6 from 8 to 7
+move 5 from 3 to 6
+move 3 from 3 to 6
+move 3 from 1 to 3
+move 8 from 2 to 9
+move 2 from 4 to 5
+move 2 from 7 to 2
+move 10 from 8 to 5
+move 3 from 3 to 2
+move 10 from 5 to 3
+move 1 from 4 to 3
+move 1 from 2 to 1
+move 1 from 1 to 7
+move 14 from 9 to 6
+move 5 from 2 to 4
+move 15 from 6 to 5
+move 3 from 9 to 3
+move 1 from 8 to 6
+move 1 from 3 to 8
+move 7 from 3 to 8
+move 16 from 5 to 1
+move 2 from 7 to 1
+move 1 from 5 to 9
+move 2 from 9 to 3
+move 15 from 1 to 5
+move 3 from 8 to 2
+move 3 from 3 to 1
+move 3 from 7 to 3
+move 8 from 4 to 6
+move 5 from 1 to 6
+move 9 from 5 to 7
+move 2 from 8 to 3
+move 2 from 2 to 7
+move 1 from 1 to 4
+move 2 from 5 to 8
+move 4 from 3 to 1
+move 4 from 8 to 1
+move 1 from 8 to 6
+move 9 from 7 to 6
+move 2 from 7 to 5
+move 3 from 1 to 8
+move 1 from 4 to 8
+move 1 from 2 to 4
+move 12 from 6 to 2
+move 3 from 8 to 6
+move 1 from 4 to 7
+move 2 from 6 to 8
+move 5 from 5 to 9
+move 13 from 2 to 9
+move 2 from 4 to 7
+move 13 from 9 to 5
+move 2 from 6 to 5
+move 1 from 3 to 9
+move 6 from 9 to 4
+move 5 from 1 to 3
+move 1 from 7 to 9
+move 15 from 5 to 8
+move 2 from 4 to 7
+move 2 from 4 to 6
+move 1 from 4 to 6
+move 1 from 5 to 7
+move 18 from 6 to 2
+move 2 from 7 to 3
+move 3 from 6 to 7
+move 3 from 2 to 8
+move 5 from 7 to 3
+move 1 from 9 to 6
+move 2 from 3 to 8
+move 11 from 3 to 2
+move 2 from 2 to 9
+move 1 from 6 to 2
+move 1 from 7 to 5
+move 1 from 5 to 9
+move 9 from 8 to 4
+move 1 from 4 to 6
+move 2 from 3 to 1
+move 2 from 1 to 5
+move 12 from 8 to 3
+move 1 from 8 to 2
+move 14 from 3 to 4
+move 1 from 6 to 4
+move 1 from 5 to 4
+move 20 from 2 to 7
+move 2 from 9 to 5
+move 1 from 5 to 3
+move 1 from 9 to 2
+move 1 from 2 to 8
+move 2 from 2 to 3
+move 5 from 4 to 5
+move 6 from 5 to 7
+move 2 from 8 to 2
+move 3 from 3 to 9
+move 5 from 4 to 5
+move 2 from 9 to 7
+move 2 from 2 to 3
+move 1 from 9 to 3
+move 22 from 7 to 3
+move 4 from 7 to 4
+move 24 from 3 to 6
+move 4 from 2 to 6
+move 18 from 6 to 9
+move 15 from 4 to 6
+move 8 from 6 to 3
+move 6 from 6 to 1
+move 7 from 9 to 6
+move 2 from 7 to 4
+move 8 from 3 to 9
+move 14 from 6 to 3
+move 2 from 3 to 9
+move 1 from 9 to 6
+move 13 from 9 to 1
+move 3 from 4 to 5
+move 1 from 9 to 6
+move 5 from 1 to 8
+move 3 from 3 to 9
+move 2 from 1 to 5
+move 8 from 5 to 8
+move 10 from 3 to 5
+move 3 from 4 to 6
+move 6 from 1 to 9
+move 4 from 5 to 3
+move 5 from 8 to 2
+move 6 from 6 to 3
+move 7 from 3 to 6
+move 1 from 3 to 4
+move 5 from 8 to 7
+move 5 from 2 to 6
+move 2 from 7 to 3
+move 3 from 7 to 3
+move 1 from 4 to 9
+move 9 from 6 to 9
+move 2 from 6 to 2
+move 1 from 8 to 2
+move 2 from 8 to 7
+move 5 from 1 to 5
+move 1 from 1 to 4
+move 13 from 5 to 7
+move 5 from 3 to 7
+move 1 from 5 to 6
+move 1 from 4 to 6
+move 3 from 2 to 8
+move 1 from 3 to 5
+move 1 from 3 to 8
+move 14 from 7 to 4
+move 1 from 5 to 6
+move 7 from 6 to 9
+move 6 from 7 to 9
+move 2 from 8 to 9
+move 2 from 8 to 1
+move 31 from 9 to 1
+move 13 from 4 to 2
+move 1 from 4 to 3
+move 10 from 2 to 7
+move 1 from 3 to 4
+move 1 from 2 to 7
+move 3 from 7 to 8
+move 1 from 4 to 1
+move 3 from 8 to 5
+move 32 from 1 to 5
+move 3 from 9 to 7
+move 4 from 9 to 6
+move 2 from 2 to 7
+move 2 from 1 to 7
+move 1 from 6 to 1
+move 1 from 9 to 4
+move 3 from 6 to 4
+move 1 from 1 to 8
+move 15 from 5 to 1
+move 1 from 8 to 4
+move 9 from 5 to 7
+move 1 from 9 to 8
+move 1 from 8 to 1
+move 10 from 1 to 9
+move 1 from 4 to 2
+move 2 from 9 to 5
+move 4 from 9 to 6
+move 1 from 2 to 7
+move 3 from 4 to 2
+move 1 from 1 to 5
+move 5 from 1 to 5
+move 1 from 4 to 9
+move 3 from 6 to 7
+move 23 from 7 to 6
+move 1 from 2 to 4
+move 1 from 2 to 5
+move 9 from 5 to 4
+move 1 from 2 to 5
+move 9 from 5 to 6
+move 1 from 9 to 7
+move 1 from 9 to 3
+move 3 from 9 to 4
+move 14 from 6 to 3
+move 5 from 7 to 4
+move 1 from 7 to 5
+move 1 from 5 to 9
+move 2 from 5 to 6
+move 16 from 6 to 2
+move 2 from 6 to 1
+move 7 from 4 to 8
+move 2 from 1 to 2
+move 4 from 3 to 5
+move 5 from 4 to 7
+move 2 from 6 to 7
+move 4 from 4 to 1
+move 4 from 8 to 9
+move 1 from 4 to 5
+move 1 from 6 to 8
+move 1 from 4 to 9
+move 4 from 1 to 7
+move 1 from 9 to 4
+move 2 from 2 to 7
+move 7 from 3 to 9
+move 15 from 2 to 3
+move 4 from 8 to 6
+move 1 from 4 to 7
+move 2 from 9 to 7
+move 1 from 6 to 8
+move 2 from 7 to 2
+move 5 from 7 to 2
+move 1 from 5 to 2
+move 6 from 2 to 9
+move 3 from 7 to 1
+move 3 from 1 to 2
+move 3 from 7 to 1
+move 2 from 2 to 9
+move 2 from 6 to 9
+move 1 from 8 to 3
+move 19 from 3 to 9
+move 1 from 6 to 3
+move 3 from 7 to 4
+move 1 from 2 to 5
+move 2 from 1 to 9
+move 2 from 2 to 3
+move 33 from 9 to 7
+move 1 from 1 to 7
+move 3 from 3 to 7
+move 1 from 3 to 2
+move 1 from 5 to 8
+move 4 from 9 to 7
+move 1 from 5 to 2
+move 2 from 4 to 9
+move 4 from 9 to 7
+move 3 from 2 to 1
+move 1 from 4 to 3
+move 1 from 9 to 7
+move 1 from 8 to 3
+move 7 from 7 to 3
+move 3 from 1 to 9
+move 4 from 9 to 7
+move 4 from 5 to 8
+move 3 from 3 to 4
+move 3 from 4 to 5
+move 3 from 3 to 6
+move 2 from 6 to 5
+move 38 from 7 to 5
+move 40 from 5 to 3
+move 4 from 8 to 9
+move 1 from 6 to 9
+move 1 from 5 to 1
+move 3 from 7 to 6
+move 1 from 7 to 5
+move 38 from 3 to 8
+move 1 from 1 to 9
+move 3 from 9 to 6
+move 5 from 3 to 9
+move 4 from 8 to 6
+move 1 from 7 to 1
+move 3 from 5 to 9
+move 1 from 1 to 2
+move 10 from 8 to 3
+move 5 from 8 to 1
+move 3 from 1 to 2
+move 9 from 6 to 7
+move 9 from 3 to 5
+move 1 from 7 to 6
+move 1 from 3 to 8
+move 1 from 7 to 9
+move 1 from 1 to 5
+move 1 from 1 to 3
+move 1 from 9 to 2
+move 4 from 2 to 3
+move 1 from 2 to 4
+move 9 from 8 to 1
+move 2 from 9 to 5
+move 2 from 1 to 2
+move 2 from 3 to 4
+move 6 from 8 to 6
+move 10 from 5 to 3
+move 7 from 3 to 2
+move 2 from 1 to 2
+move 5 from 1 to 7
+move 7 from 9 to 6
+move 7 from 6 to 5
+move 1 from 4 to 3
+move 7 from 7 to 4
+move 5 from 3 to 9
+move 7 from 2 to 6
+move 4 from 7 to 8
+move 5 from 8 to 9
+move 1 from 2 to 6
+move 1 from 3 to 5
+move 2 from 2 to 8
+move 8 from 4 to 6
+move 7 from 9 to 7
+move 4 from 7 to 9
+move 7 from 9 to 3
+move 8 from 3 to 1
+move 6 from 5 to 9
+move 8 from 1 to 8
+move 13 from 8 to 4
+move 3 from 9 to 6
+move 1 from 8 to 6
+move 1 from 7 to 3
+move 2 from 4 to 1
+move 5 from 9 to 1
+move 1 from 3 to 7
+move 15 from 6 to 1
+move 1 from 7 to 9
+move 10 from 4 to 7
+move 11 from 7 to 5
+move 17 from 1 to 6
+move 1 from 9 to 3
+move 6 from 6 to 1
+move 3 from 5 to 3
+move 2 from 4 to 5
+move 2 from 7 to 8
+move 12 from 5 to 3
+move 13 from 6 to 9
+move 2 from 8 to 2
+move 2 from 5 to 1
+move 16 from 3 to 8
+move 3 from 2 to 3
+move 2 from 3 to 7
+move 2 from 7 to 9
+move 1 from 3 to 7
+move 4 from 8 to 4
+move 2 from 4 to 8
+move 5 from 1 to 5
+move 2 from 4 to 7
+move 6 from 6 to 8
+move 2 from 8 to 5
+move 2 from 1 to 4
+move 5 from 8 to 7
+move 5 from 6 to 3
+move 6 from 9 to 8
+move 2 from 9 to 2
+move 1 from 1 to 7
+move 4 from 5 to 3
+move 2 from 2 to 3
+move 1 from 4 to 9
+move 10 from 3 to 6
+move 1 from 3 to 7
+move 10 from 7 to 2
+move 2 from 5 to 3
+move 1 from 4 to 2
+move 2 from 6 to 8
+move 3 from 6 to 5
+move 1 from 6 to 1
+move 7 from 2 to 3
+move 6 from 8 to 7
+move 4 from 6 to 3
+move 14 from 8 to 6
+move 11 from 6 to 8
+move 1 from 1 to 4
+move 6 from 7 to 2
+move 3 from 5 to 8
+move 4 from 1 to 7
+move 1 from 2 to 8
+move 1 from 2 to 6
+move 1 from 3 to 4
+move 1 from 5 to 6
+move 7 from 8 to 6
+move 9 from 3 to 2
+move 1 from 8 to 5
diff --git a/src/day05.lisp b/src/day05.lisp
@@ -0,0 +1,71 @@
+(defpackage #:adventofcode2022/day05
+ (:use #:cl #:adventofcode2022))
+(in-package #:adventofcode2022/day05)
+
+(defun parse-stack (stack-lines)
+ (let* ((indices (mapcar (lambda (x)
+ (parse-integer x))
+ (str:split " " (pop stack-lines) :omit-nulls t)))
+ (length (apply #'max indices))
+ (stacks (make-array length :initial-element nil)))
+ (loop for line in stack-lines
+ do (loop for i from 0 below length
+ for crate-index = (1+ (* i 4))
+ for crate-id = (aref line crate-index)
+ when (not (char= #\Space crate-id))
+ do (push crate-id
+ (aref stacks i))))
+ stacks))
+
+(defun parse-input (inputs)
+ (loop with stack-lines = nil
+ with rules = nil
+ with rules-p = nil
+ for input in inputs
+ if (= 0 (length input))
+ do (setf rules-p t)
+ else if rules-p
+ do (let ((parts (str:split " " input)))
+ (push (list (parse-integer (second parts))
+ (parse-integer (fourth parts))
+ (parse-integer (sixth parts)))
+ rules))
+ else
+ do (push input stack-lines)
+ finally (return (values (parse-stack stack-lines)
+ (reverse rules)))))
+
+(defun task1 (inputs)
+ (multiple-value-bind (stacks rules)
+ (parse-input inputs)
+ (loop for rule in rules
+ do (loop for i from 1 to (car rule)
+ for from = (1- (cadr rule))
+ for to = (1- (caddr rule))
+ for crate = (pop (aref stacks from))
+ do (push crate (aref stacks to))))
+ (coerce (loop for i from 0 below (length stacks)
+ collect (first (aref stacks i)))
+ 'string)))
+
+(defmacro popn (place n)
+ `(loop for i from 0 below ,n
+ collect (pop ,place)))
+
+(defun task2 (inputs)
+ (multiple-value-bind (stacks rules)
+ (parse-input inputs)
+ (loop for rule in rules
+ for from = (1- (cadr rule))
+ for to = (1- (caddr rule))
+ for crates = (popn (aref stacks from) (car rule))
+ do (setf (aref stacks to)
+ (nconc crates (aref stacks to))))
+ (coerce (loop for i from 0 below (length stacks)
+ collect (first (aref stacks i)))
+ 'string)))
+
+(define-day 5
+ ()
+ #'task1
+ #'task2)
diff --git a/t/day05.lisp b/t/day05.lisp
@@ -0,0 +1,24 @@
+(in-package #:adventofcode2022/test)
+
+(defconstant +testdata-day05+ " [D]
+[N] [C]
+[Z] [M] [P]
+ 1 2 3
+
+move 1 from 2 to 1
+move 3 from 1 to 3
+move 2 from 2 to 1
+move 1 from 1 to 2")
+
+(def-test day05-task1 ()
+ (is-true
+ (string= "CMZ"
+ (run-task 5 1
+ (make-string-input-stream +testdata-day05+)))))
+
+(def-test day05-task2 ()
+ (is-true
+ (string= "MCD"
+ (run-task 5 2
+ (make-string-input-stream +testdata-day05+)))))
+