commit 8f85db82750e7cbe6721a11a71b3bf1c73dc1ebc
parent 878e6fe4752560168df28d7ec49fd08fa481c55b
Author: Lukas Henkel <lh@entf.net>
Date: Fri, 16 Dec 2022 18:37:34 +0100
Day 16 part 1
Diffstat:
4 files changed, 190 insertions(+), 3 deletions(-)
diff --git a/adventofcode2022.asd b/adventofcode2022.asd
@@ -9,7 +9,8 @@
"str"
"queues"
"queues.simple-queue"
- "binding-arrows")
+ "binding-arrows"
+ "cl-ppcre")
:components ((:file "main")
(:file "day01")
(:file "day02")
@@ -25,7 +26,8 @@
(:file "day12")
(:file "day13")
(:file "day14")
- (:file "day15")))
+ (:file "day15")
+ (:file "day16")))
(defsystem "adventofcode2022/test"
:description "My solutions to the advent of code 2022"
@@ -50,4 +52,5 @@
(:file "day12")
(:file "day13")
(:file "day14")
- (:file "day15")))
+ (:file "day15")
+ (:file "day16")))
diff --git a/input/day16.txt b/input/day16.txt
@@ -0,0 +1,51 @@
+Valve NV has flow rate=5; tunnels lead to valves ZV, CG, YB, HX, OY
+Valve NU has flow rate=6; tunnels lead to valves DA, MA, OA, DK
+Valve VU has flow rate=0; tunnels lead to valves PS, FX
+Valve JW has flow rate=0; tunnels lead to valves AA, MD
+Valve RI has flow rate=0; tunnels lead to valves OY, DG
+Valve DG has flow rate=9; tunnels lead to valves TG, RI, DF, EV, KW
+Valve PH has flow rate=7; tunnels lead to valves KW, OW, LT, LZ
+Valve KZ has flow rate=12; tunnels lead to valves ET, QV, CK, MS
+Valve IX has flow rate=0; tunnels lead to valves TS, DO
+Valve MS has flow rate=0; tunnels lead to valves LZ, KZ
+Valve IL has flow rate=0; tunnels lead to valves DO, ET
+Valve EJ has flow rate=20; tunnels lead to valves AV, JY
+Valve DK has flow rate=0; tunnels lead to valves NU, CG
+Valve YB has flow rate=0; tunnels lead to valves NV, PS
+Valve OA has flow rate=0; tunnels lead to valves YA, NU
+Valve DA has flow rate=0; tunnels lead to valves NU, RG
+Valve KO has flow rate=0; tunnels lead to valves AA, TG
+Valve RG has flow rate=4; tunnels lead to valves DF, DA, ZV, MD, LB
+Valve MA has flow rate=0; tunnels lead to valves AA, NU
+Valve OW has flow rate=0; tunnels lead to valves DO, PH
+Valve KW has flow rate=0; tunnels lead to valves DG, PH
+Valve DO has flow rate=14; tunnels lead to valves IX, IL, CZ, OW
+Valve DF has flow rate=0; tunnels lead to valves RG, DG
+Valve TG has flow rate=0; tunnels lead to valves DG, KO
+Valve LB has flow rate=0; tunnels lead to valves RG, FX
+Valve HX has flow rate=0; tunnels lead to valves AA, NV
+Valve GB has flow rate=0; tunnels lead to valves AV, XK
+Valve CG has flow rate=0; tunnels lead to valves DK, NV
+Valve LT has flow rate=0; tunnels lead to valves AO, PH
+Valve FX has flow rate=23; tunnels lead to valves LB, HY, VU
+Valve ET has flow rate=0; tunnels lead to valves IL, KZ
+Valve CK has flow rate=0; tunnels lead to valves UX, KZ
+Valve LZ has flow rate=0; tunnels lead to valves PH, MS
+Valve YA has flow rate=17; tunnels lead to valves JY, OA
+Valve TS has flow rate=0; tunnels lead to valves NO, IX
+Valve NO has flow rate=8; tunnel leads to valve TS
+Valve XK has flow rate=24; tunnel leads to valve GB
+Valve PS has flow rate=18; tunnels lead to valves EV, VU, YB
+Valve AA has flow rate=0; tunnels lead to valves JW, HX, MA, KO
+Valve MD has flow rate=0; tunnels lead to valves JW, RG
+Valve JM has flow rate=19; tunnels lead to valves QV, HY, AO
+Valve AV has flow rate=0; tunnels lead to valves EJ, GB
+Valve AO has flow rate=0; tunnels lead to valves JM, LT
+Valve JY has flow rate=0; tunnels lead to valves YA, EJ
+Valve OY has flow rate=0; tunnels lead to valves NV, RI
+Valve UX has flow rate=13; tunnels lead to valves CZ, CK
+Valve HY has flow rate=0; tunnels lead to valves JM, FX
+Valve EV has flow rate=0; tunnels lead to valves PS, DG
+Valve CZ has flow rate=0; tunnels lead to valves UX, DO
+Valve ZV has flow rate=0; tunnels lead to valves NV, RG
+Valve QV has flow rate=0; tunnels lead to valves JM, KZ
diff --git a/src/day16.lisp b/src/day16.lisp
@@ -0,0 +1,94 @@
+(defpackage #:adventofcode2022/day16
+ (:use #:cl #:adventofcode2022)
+ (:import-from #:alexandria
+ #:define-constant
+ #:hash-table-values)
+ (:import-from #:cl-ppcre
+ #:register-groups-bind)
+ (:import-from #:queues
+ #:make-queue
+ #:qpush
+ #:qpop))
+(in-package #:adventofcode2022/day16)
+
+(define-constant +input-line-regex+
+ "Valve ([^ ]+) .* rate=(\\d+); .* valves? (.*)"
+ :test 'equal)
+
+(defclass valve ()
+ ((vid :initarg :vid
+ :reader vid)
+ (rate :initarg :rate
+ :accessor rate)
+ (next-valves :accessor next-valves)))
+
+(defun make-graph (inputs)
+ (let ((valves (make-hash-table)))
+ (loop for input in inputs
+ do (setf (gethash (car input) valves)
+ (make-instance 'valve
+ :vid (car input)
+ :rate (cadr input))))
+ (loop for input in inputs
+ for valve = (gethash (car input) valves)
+ for next-valves = (mapcar (lambda (id)
+ (gethash id valves))
+ (caddr input))
+ do (setf (next-valves valve) next-valves))
+ (values (gethash :AA valves)
+ (remove-if (lambda (valve)
+ (= (rate valve) 0))
+ (hash-table-values valves)))))
+
+(defparameter *distance-cache* nil)
+
+(defun find-shortest-path (from to)
+ (let* ((key (cons (vid from) (vid to)))
+ (cached (gethash key *distance-cache*)))
+ (unless (null cached)
+ (return-from find-shortest-path cached))
+ (let ((shortest-path
+ (loop named outer
+ with queue = (make-queue :simple-queue)
+ initially (qpush queue (list 0 from))
+ while t
+ for (length node) = (qpop queue)
+ do (loop for next-node in (next-valves node)
+ when (eq to next-node)
+ do (return-from outer (1+ length))
+ do (qpush queue (list (1+ length) next-node))))))
+ (setf (gethash key *distance-cache*) shortest-path)
+ shortest-path)))
+
+(defun get-highest-pressure (current-valve unopened-valves remaining-minutes)
+ (if (or (<= remaining-minutes 0)
+ (= (length unopened-valves) 0))
+ 0
+ (loop for unopened-valve in unopened-valves
+ for path-length = (find-shortest-path current-valve unopened-valve)
+ for remaining-minutes-new = (- remaining-minutes path-length 1)
+ when (> remaining-minutes-new 0)
+ maximize (+ (* (rate unopened-valve) remaining-minutes-new)
+ (get-highest-pressure unopened-valve
+ (remove unopened-valve unopened-valves)
+ remaining-minutes-new)))))
+
+(defun task1 (inputs)
+ (let ((*distance-cache* (make-hash-table :test 'equal)))
+ (multiple-value-bind (start unopened-valves)
+ (make-graph inputs)
+ (get-highest-pressure start unopened-valves 30))))
+
+(defun parse-line (input)
+ (register-groups-bind (valve rate next-valves)
+ (+input-line-regex+ input)
+ (list (intern valve :keyword)
+ (parse-integer rate)
+ (mapcar (lambda (valve)
+ (intern valve :keyword))
+ (str:split ", " next-valves)))))
+
+(define-day 16
+ (:translate-input #'parse-line)
+ #'task1
+ nil)
diff --git a/t/day16.lisp b/t/day16.lisp
@@ -0,0 +1,39 @@
+(in-package #:adventofcode2022/test)
+
+(define-constant +testdata-day16+ "Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II"
+ :test 'equal)
+
+(def-test day16-find-shortest-path ()
+ (let ((adventofcode2022/day16::*distance-cache*
+ (make-hash-table :test 'equal)))
+ (multiple-value-bind (start unopened-valves)
+ (adventofcode2022/day16::make-graph
+ (mapcar #'adventofcode2022/day16::parse-line
+ (str:lines +testdata-day16+)))
+ (loop for unopened-valve in unopened-valves
+ for valve-id = (adventofcode2022/day16::vid unopened-valve)
+ for path-length = (adventofcode2022/day16::find-shortest-path start unopened-valve)
+ for expected = (case valve-id
+ (:BB 1)
+ (:CC 2)
+ (:DD 1)
+ (:EE 2)
+ (:HH 5)
+ (:JJ 2)
+ (otherwise 0))
+ do (is-true (= path-length expected))))))
+
+(def-test day16-task1 ()
+ (is-true
+ (= 1651
+ (run-task 16 1
+ (make-string-input-stream +testdata-day16+)))))
