diff options
Diffstat (limited to 'AoC2022')
| -rw-r--r-- | AoC2022/16/eg-in | 10 | ||||
| -rw-r--r-- | AoC2022/16/input | 51 | ||||
| -rw-r--r-- | AoC2022/16/solver.lisp | 64 |
3 files changed, 125 insertions, 0 deletions
diff --git a/AoC2022/16/eg-in b/AoC2022/16/eg-in new file mode 100644 index 0000000..9f30acc --- /dev/null +++ b/AoC2022/16/eg-in @@ -0,0 +1,10 @@ +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 diff --git a/AoC2022/16/input b/AoC2022/16/input new file mode 100644 index 0000000..2283d67 --- /dev/null +++ b/AoC2022/16/input @@ -0,0 +1,51 @@ +Valve JC has flow rate=0; tunnels lead to valves XS, XK +Valve TK has flow rate=0; tunnels lead to valves AA, RA +Valve PY has flow rate=0; tunnels lead to valves UB, MW +Valve XK has flow rate=15; tunnels lead to valves CD, JC, TP, UE +Valve EI has flow rate=6; tunnels lead to valves UB, HD +Valve OV has flow rate=0; tunnels lead to valves QC, WK +Valve CX has flow rate=3; tunnels lead to valves ZN, AM, OE, YS, QE +Valve YS has flow rate=0; tunnels lead to valves QC, CX +Valve DC has flow rate=0; tunnels lead to valves UE, NM +Valve EA has flow rate=5; tunnels lead to valves QE, XO, GX +Valve VE has flow rate=0; tunnels lead to valves YH, NM +Valve RN has flow rate=0; tunnels lead to valves WK, NU +Valve VJ has flow rate=0; tunnels lead to valves QC, CS +Valve HD has flow rate=0; tunnels lead to valves JI, EI +Valve UB has flow rate=0; tunnels lead to valves EI, PY +Valve XS has flow rate=17; tunnels lead to valves JC, CE +Valve AM has flow rate=0; tunnels lead to valves NU, CX +Valve GX has flow rate=0; tunnels lead to valves EA, RA +Valve UI has flow rate=0; tunnels lead to valves NC, ZG +Valve NM has flow rate=22; tunnels lead to valves DC, VE, DX +Valve CE has flow rate=0; tunnels lead to valves XS, WD +Valve NC has flow rate=25; tunnels lead to valves UI, VQ +Valve TP has flow rate=0; tunnels lead to valves XK, RA +Valve ZN has flow rate=0; tunnels lead to valves CX, XI +Valve CS has flow rate=0; tunnels lead to valves AA, VJ +Valve MW has flow rate=23; tunnel leads to valve PY +Valve AA has flow rate=0; tunnels lead to valves TK, WC, CS, AL, MS +Valve RA has flow rate=4; tunnels lead to valves WD, TP, TK, GX, JI +Valve NU has flow rate=10; tunnels lead to valves DU, AM, RN, HS, AL +Valve QE has flow rate=0; tunnels lead to valves CX, EA +Valve AH has flow rate=0; tunnels lead to valves WK, MS +Valve YH has flow rate=20; tunnels lead to valves VE, CD +Valve SH has flow rate=0; tunnels lead to valves DU, ZG +Valve OE has flow rate=0; tunnels lead to valves WC, CX +Valve XO has flow rate=0; tunnels lead to valves EA, ZG +Valve JI has flow rate=0; tunnels lead to valves RA, HD +Valve XI has flow rate=0; tunnels lead to valves WK, ZN +Valve HS has flow rate=0; tunnels lead to valves QC, NU +Valve VQ has flow rate=0; tunnels lead to valves WK, NC +Valve UE has flow rate=0; tunnels lead to valves XK, DC +Valve YP has flow rate=19; tunnel leads to valve DX +Valve WD has flow rate=0; tunnels lead to valves CE, RA +Valve DX has flow rate=0; tunnels lead to valves NM, YP +Valve ZG has flow rate=11; tunnels lead to valves UI, SH, XO +Valve MS has flow rate=0; tunnels lead to valves AA, AH +Valve QC has flow rate=9; tunnels lead to valves HS, VJ, OV, YS +Valve DU has flow rate=0; tunnels lead to valves NU, SH +Valve WK has flow rate=12; tunnels lead to valves RN, XI, VQ, OV, AH +Valve CD has flow rate=0; tunnels lead to valves YH, XK +Valve AL has flow rate=0; tunnels lead to valves AA, NU +Valve WC has flow rate=0; tunnels lead to valves OE, AA diff --git a/AoC2022/16/solver.lisp b/AoC2022/16/solver.lisp new file mode 100644 index 0000000..6c0a040 --- /dev/null +++ b/AoC2022/16/solver.lisp @@ -0,0 +1,64 @@ + +(ql:quickload '(fiveam cl-ppcre uiop arrows)) + +(defun data (filename) + (with-open-file (in filename) + (loop for line = (read-line in nil nil) + while line + collect (cl-ppcre:register-groups-bind (val (#'parse-integer flow) others) + ("Valve (\\w+) has flow rate=(\\d+); tunnels? leads? to valves? (.+)" line) + `(,(intern val) ,flow ,@(mapcar #'intern (cl-ppcre:split ", " others))))))) + + +(defun next-steps (current graph paths) + (flet ((appropriate (next) + (and (not (gethash next paths)) ;; not visited + (setf (gethash next paths) (cons next (gethash current paths)))))) + (remove-if-not #'appropriate (cddr (assoc current graph :test #'eq))))) + +(defun shortest-path (graph from to) + (let ((paths (make-hash-table :test #'eq))) + (setf (gethash from paths) (list from)) + (labels ((traverse (queue paths) + (unless (null queue) + (let ((next (next-steps (car queue) graph paths))) + (unless (member to next :test #'eq) + (traverse (append (cdr queue) next) paths)))))) + (traverse (list from) paths)) + ;; (loop for k being the hash-keys in paths using (hash-value v) + ;; do (format t "~a=>~a~%" k v)) + (gethash to paths))) + +(defun path-release (path) + (loop for ((name flow) . distance) in path + sum (1+ distance) into runtime + sum (* flow (- 30 runtime)) into release + finally (return release))) + +(= 340 (path-release '(((a 5) . 1) ((b 8) . 2)))) +(shortest-path (data "eg-in") 'AA 'CC) + +(defun next-options (current graph visited) + (flet ((appropriate (next) + (and (not (gethash next paths)) ;; not visited + (setf (gethash next paths) (cons next (gethash current paths)))))) + (remove-if-not #'appropriate (cddr (assoc current graph :test #'eq)))) + ) +q +(let* ((graph (data "eg-in")) + (interesting (remove-if #'zerop graph :key #'cadr)) + (open nil)) + + (sort + (mapcar (lambda (node) + (cons (subseq node 0 2) + (length (shortest-path graph 'aa (car node))))) + interesting) + #'> + :key (lambda (destination) + (destructuring-bind ((name flow) . distance) destination + ;; because start is in path take that as valve opening time + (- flow distance)))) + ) + +(adjoin 'c '(b c)) |