lisp try day 16

1 files changed, 64 insertions, 0 deletions

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