From 0e776454e8c53c996f1bade2ccc59ad7e4b3ac92 Mon Sep 17 00:00:00 2001 From: Oscar Najera Date: Sun, 18 Dec 2022 21:14:07 +0100 Subject: ??graph to hashtable --- AoC2022/16/solver.lisp | 22 +++++++++++++--------- 1 file changed, 13 insertions(+), 9 deletions(-) (limited to 'AoC2022/16/solver.lisp') diff --git a/AoC2022/16/solver.lisp b/AoC2022/16/solver.lisp index 0366fc3..9bda6f2 100644 --- a/AoC2022/16/solver.lisp +++ b/AoC2022/16/solver.lisp @@ -31,12 +31,16 @@ (gethash to paths))) (defun worthwhile-graph (graph) - (let ((interesting (remove-if #'zerop graph :key #'cadr))) + (let ((interesting (remove-if #'zerop graph :key #'cadr)) + (htgraph (make-hash-table :test #'eq :size 16))) (loop for (from flow) in (cons '(aa 0) interesting) - collect (nconc (list from flow) + do + (setf (gethash from htgraph) + (cons flow (loop for (to) in interesting when (not (eq from to)) - collect (cons to (1- (length (shortest-path graph from to))))))))) + collect (cons to (1- (length (shortest-path graph from to)))))))) + htgraph)) (defun travel-time (path graph) (loop for (from to) on path @@ -51,7 +55,7 @@ (destructuring-bind (next-node-name . time-there) next (and (not (member next-node-name open :test #'eq)) (< (1+ time-there) time-left))))) - (remove-if-not #'appropriate (cddr (assoc current graph :test #'eq))))) + (remove-if-not #'appropriate (cdr (gethash current graph))))) (defun path-release-as (path graph start-time) (loop for (from to) on path @@ -65,11 +69,11 @@ (defun path-release (path graph start-time) (loop for (from to) on path - for node-from = (assoc from graph :test #'eq) then node-to - and node-to = (assoc to graph :test #'eq) + for node-from = (gethash from graph) then node-to + and node-to = (gethash to graph) while node-to - for neighbors = (cddr node-from) - for flow = (cadr node-to) + for neighbors = (cdr node-from) + for flow = (car node-to) for distance = (cdr (assoc to neighbors :test #'eq)) sum (1+ distance) into runtime sum (* flow (- start-time runtime)) into release @@ -96,7 +100,7 @@ (arrows:-> (lambda (next-node) (destructuring-bind (name . time-there) next-node - (let ((flow (cadr (assoc name graph :test #'eq))) + (let ((flow (car (gethash name graph))) (time-left (- time-left time-there 1))) (traverse graph name (cons name open) time-left -- cgit v1.2.3