blob: 6c0a0401a05a8394c5ce702a78f0d880fb849da4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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))
|
