aoc2021 day12

aoc2021-day12.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2021                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2021/day12
  (:use #:cl)
  (:import-from
   #:alexandria)
  (:import-from
   #:split-sequence)
  (:export
   #:day12))

(in-package #:snippets/aoc2021/day12)

(defstruct path
  nodes
  small-cave-twice-p)

(defun make-graph (lines)
  (let ((graph (make-hash-table)))
    (dolist (line lines)
      (destructuring-bind (node1 node2)
          (mapcar #'alexandria:make-keyword
                  (split-sequence:split-sequence #\- line))
        (pushnew node2 (gethash node1 graph))
        (pushnew node1 (gethash node2 graph))))
    graph))

(defun bigp (node)
  (every #'upper-case-p (symbol-name node)))

(defun current-node (path)
  (car (path-nodes path)))

(defun visit (path node)
  (make-path
   :nodes (cons node (path-nodes path))
   :small-cave-twice-p (or (path-small-cave-twice-p path)
                           (and (not (bigp node))
                                (member node (path-nodes path))))))

(defun count-paths (graph visit-small-p)
  (let ((paths 0)
        (agenda (list (make-path :nodes (list :|start|)))))
    (loop until (null agenda)
          do (let* ((path (pop agenda))
                    (node (current-node path)))
               (if (eq node :|end|)
                   (incf paths)
                   (dolist (adjacent-node (gethash node graph))
                     (when (or (bigp adjacent-node)
                               (eq adjacent-node :|end|)
                               (and (not (eq adjacent-node :|start|))
                                    (funcall visit-small-p path adjacent-node)))
                       (push (visit path adjacent-node) agenda))))))
    paths))

(defun hasty-visit-small-p (path node)
  (not (member node (path-nodes path))))

(defun wasty-visit-small-p (path node)
  (< (count node (path-nodes path))
     (if (path-small-cave-twice-p path) 1 2)))

(defun day12 (input)
  (let ((graph (make-graph input)))
    (list (count-paths graph #'hasty-visit-small-p)
          (count-paths graph #'wasty-visit-small-p))))