lisp try day 16

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))