If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:
- Starting slime (
M-x slime) - Typing
C-c C-cin the block initialize. - In the repl type
(in-package :aoc-2022-16) - Typing
C-c C-cin the block answers
(unless (find-package :priority-queue)
(ql:quickload "priority-queue"))
(unless (find-package :cl-ppcre)
(ql:quickload "cl-ppcre"))
(unless (find-package :parseq)
(ql:quickload "parseq"))
(unless (find-package :lparallel)
(ql:quickload "lparallel"))
(unless (find-package :fiveam)
(ql:quickload "fiveam"))
(unless (find-package :series)
(ql:quickload "series"))
(unless (find-package :cl-permutation)
(ql:quickload "cl-permutation"))
(unless (find-package :bordeaux-threads)
(ql:quickload "bordeaux-threads"))<<packages>>
(defpackage :aoc-2022-16
(:use :common-lisp
:priority-queue
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2022-16)"Valve NA has flow rate=0; tunnels lead to valves MU, PH"
(defun parse-line (line)
(cl-ppcre:register-groups-bind
(valve (#'parse-integer rate) valves)
("Valve ([A-Z]+) has flow rate=(\\d+); tunnels? leads? to valves? (.+)" line)
(let ((valves (cl-ppcre:all-matches-as-strings "[A-Z][A-Z]" valves)))
(list valve rate valves))))
(defun process-stream (in)
(loop for line = (read-line in nil)
while line
collect (parse-line line)))
(defun read-input (file)
(with-open-file (in file)
(process-stream in)))(defparameter *input*
(read-input "input/16.txt")) (defun increase (open bit-map rates)
(loop for valve being the hash-keys of bit-map using (hash-value bit)
if (plusp (logand open bit))
sum (gethash valve rates)))
(defun maximize-pressure (paths rates bit-map &optional (initial-time 30) (initial-open 0))
(loop with fringe = (make-pqueue #'>)
with table = (make-hash-table :test #'equalp)
initially (pqueue-push (list "AA" initial-time 0 initial-open) 0 fringe)
for (position time pressure open) = (pqueue-pop fringe)
for state = (list position time open)
for rate = (gethash position rates)
for increase = (* (1- time) rate)
for next-pressure = (+ pressure increase)
when (zerop time)
maximizing pressure
if (and (< (gethash state table -1) pressure) (plusp time))
do (setf (gethash state table) pressure)
(loop for destination in (gethash position paths)
for next = (list destination (1- time) pressure open)
for next-rate = (gethash destination rates)
for estimate = (* (- time 2) next-rate)
do (pqueue-push
next
(+ estimate pressure)
fringe))
(if (and (zerop (logand (gethash position bit-map) open))
(plusp rate))
(pqueue-push (list position (1- time) next-pressure (logior open (gethash position bit-map)))
next-pressure
fringe))
until (pqueue-empty-p fringe)))
2
(defun valves-to-paths (data)
(loop with paths = (make-hash-table :test 'equalp)
with rates = (make-hash-table :test 'equalp)
with bit-map = (make-hash-table :test 'equalp)
for i from 0
for (valve rate valves) in data
do (setf (gethash valve rates) rate)
(setf (gethash valve paths) valves)
(setf (gethash valve bit-map) (expt 2 i))
finally (return (list paths rates bit-map))))
(defun solve-a (data &optional (initial-time 30) (initial-open 0))
(destructuring-bind (paths rates bit-map) (valves-to-paths data)
(maximize-pressure paths rates bit-map initial-time initial-open)))
(defun problem-a () (format t "Problem 16 A: ~a~%" (solve-a *input*)))(defun all-pressure (paths rates bit-map &optional (initial-time 30) (initial-open 0))
(loop with fringe = (make-pqueue #'>)
with table = (make-hash-table :test #'equalp)
initially (pqueue-push (list "AA" initial-time 0 initial-open) 0 fringe)
for (position time pressure open) = (pqueue-pop fringe)
for state = (list position time open)
for rate = (gethash position rates)
for increase = (* (1- time) rate)
for next-pressure = (+ pressure increase)
with result = (make-hash-table)
finally (return result)
when (zerop time)
do (setf (gethash open result) (max (gethash open result 0) pressure))
if (and (< (gethash state table -1) pressure) (plusp time))
do (setf (gethash state table) pressure)
(loop for destination in (gethash position paths)
for next = (list destination (1- time) pressure open)
for next-rate = (gethash destination rates)
for estimate = (* (- time 2) next-rate)
do (pqueue-push
next
(+ estimate pressure)
fringe))
(if (and (zerop (logand (gethash position bit-map) open))
(plusp rate))
(pqueue-push (list position (1- time) next-pressure (logior open (gethash position bit-map)))
next-pressure
fringe))
until (pqueue-empty-p fringe)))
(defun solve-b (data)
(destructuring-bind (paths rates bit-map) (valves-to-paths data)
(let ((pairs (all-pressure paths rates bit-map 26)))
(loop for o1 being the hash-key of pairs using (hash-value p1)
maximizing (loop for o2 being the hash-key of pairs using (hash-value p2)
if (zerop (logand o1 o2))
maximizing (+ p1 p2))))))
(defun problem-b () (format t "Problem 16 B: ~a~%" (solve-b *input*)))<<read-input>>
<<input>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 16 A: 2183 Problem 16 B: 2911
(def-suite aoc.2022.16)
(in-suite aoc.2022.16)
(defparameter *sample-input*
"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")
(defparameter *sample*
(with-input-from-string (in *sample-input*)
(process-stream in)))
(run! 'aoc.2022.16)Running test suite AOC.2022.16 Didn't run anything...huh?