129 lines
4.5 KiB
Common Lisp
129 lines
4.5 KiB
Common Lisp
;; https://adventofcode.com/2022/day/16
|
|
|
|
;; so. only idea i had is to build the graph, and then do random walk? ugh.
|
|
;; we could maybe potentially divide by 2 amount of recursion,
|
|
;;
|
|
;; since possible actions are
|
|
;; - go to next room
|
|
;; - open current valve & go to next room
|
|
;;
|
|
;; and that shared part is almost similar, but is 1 move shorter, but adds some turns of this valve being open
|
|
;; if i return info on which valves were open for how many turns from the recursion,
|
|
;; i could potentially calculate what is more - 1 less turn of all of these and + some amount of current room's valve
|
|
;; or just go to next turn.
|
|
;;
|
|
;; but this is kind of way too much, to wander aimlessly?
|
|
;; maybe I need to build closure, then could choose any desired vertice? and select only those which are not visited.
|
|
;; this seems much more sane
|
|
;;
|
|
;; maybe there's already good \ easy \ powerful graph library?
|
|
;;
|
|
;; i found two libraries for graphs.
|
|
;; https://cl-graph.common-lisp.dev/user-guide.html - this one seem to allow for calculating closures, and filtering.
|
|
;; (repo: https://github.com/gwkkwg/cl-graph )
|
|
;; so i could potentially filter the remaining graph for the walkthrough
|
|
;; https://github.com/kraison/graph-utils - this one visualization and primitives that could allow for writing algos
|
|
;;
|
|
;; i guess i'll try to install first. is it available in quicklisp?
|
|
;; (ql:quickload 'cl-graph)
|
|
|
|
(push #p"~/quicklisp/local-projects/cl-graph/" asdf:*central-registry*)
|
|
|
|
;; (ql:quickload "cl-graph")
|
|
(ql:quickload '(:cl-graph :moptilities))
|
|
(defclass my-graph (cl-graph:basic-graph)
|
|
())
|
|
(defparameter *test-graph* nil)
|
|
;; (:documentation "Stub for matrix based graph. Not implemented.")
|
|
;; OH NO
|
|
|
|
;; (cl-graph:add-vertex *test-graph* 6)
|
|
;; (cl-graph:vertex-count *test-graph*)
|
|
|
|
;; (cl-graph:graph->dot *test-graph* t)
|
|
|
|
;; (in-package #:cl-graph)
|
|
(in-package cl-user)
|
|
|
|
(make-graph 'basic-graph) ; still doesn' work
|
|
;; to allow export to DOT
|
|
;; https://github.com/gwkkwg/cl-graph/issues/12
|
|
;; (defclass* dot-graph (dot-graph-mixin graph-container)
|
|
;; ()
|
|
;; (:export-p t))
|
|
(let ((g (make-container 'dot-graph :default-edge-type :directed)))
|
|
(loop for (a b) in '((a b) (b c) (b d) (d e) (e f) (d f)) do
|
|
(add-edge-between-vertexes g a b))
|
|
(graph->dot g nil))
|
|
|
|
|
|
(setq *test-graph*
|
|
(let ((g (cl-graph:make-graph 'cl-graph:dot-graph)))
|
|
(loop for v in '(a b c d e) do
|
|
(cl-graph:add-vertex g v))
|
|
(loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
|
|
(cl-graph:add-edge-between-vertexes g v1 v2))
|
|
g))
|
|
|
|
(setq *test-graph*
|
|
(let ((g (make-graph 'graph-container)))
|
|
(loop for v in '(a b c d e) do
|
|
(add-vertex g v))
|
|
(loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
|
|
(add-edge-between-vertexes g v1 v2))
|
|
g))
|
|
|
|
(cl-graph:vertex-count *test-graph*)
|
|
(graph->dot *test-graph* nil)
|
|
(vertexes *test-graph*)
|
|
(make-graph-from-vertexes (vertexes *test-graph*))
|
|
|
|
(identity 1)
|
|
;; graph-container already subclass of basic-graph.
|
|
;; then why doesn't this method is dispatched?
|
|
(make-filtered-graph *test-graph* (lambda (v) t) )
|
|
|
|
;; maybe quicklisp doens't have a fresh enough version?
|
|
;; ok. how do i make quicklisp use cloned code?
|
|
|
|
;; well. too bad.
|
|
(cl-graph:make-graph-from-vertexes (cl-graph:vertexes *test-graph*))
|
|
(cl-graph:make-filtered-graph *test-graph* (lambda (v) t) )
|
|
((lambda (v) t) 1)
|
|
|
|
(ql:where-is-system :cl-graph)
|
|
;; => #P"/home/efim/quicklisp/dists/quicklisp/software/cl-graph-20171227-git/"
|
|
|
|
(ql:update-client)
|
|
(ql:update-all-dists)
|
|
;; Changes from quicklisp 2022-07-08 to quicklisp 2022-11-07:
|
|
|
|
(cl-graph:graph->dot *test-graph* nil)
|
|
|
|
;; required additional dependency
|
|
;; (ql:quickload '(:cl-graph :moptilities))
|
|
;; asdf system connections
|
|
;; https://github.com/gwkkwg/cl-graph/blob/3cb786797b24883d784b7350e7372e8b1e743508/cl-graph.asd#L84-L89
|
|
|
|
(setq *test-graph*
|
|
(let ((g (cl-graph:make-graph 'cl-graph:dot-graph)))
|
|
(loop for v in '(a b c d e) do
|
|
(cl-graph:add-vertex g v))
|
|
(loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
|
|
(cl-graph:add-edge-between-vertexes g v1 v2))
|
|
g))
|
|
|
|
(print (cl-graph:graph->dot *test-graph* nil))
|
|
|
|
(print (cl-graph:graph->dot
|
|
(cl-graph:make-filtered-graph *test-graph*
|
|
(lambda (v) (not (eq v 'a)))
|
|
:graph-completion-method nil)
|
|
nil))
|
|
|
|
;; well, that was all for nothing?
|
|
;; or do i still rather use that library?
|
|
;; because it would allow me to add data to vertices?
|
|
;;
|
|
;; and graph-utils allows for getting hashmap of all paths and lengts?
|