--- a/src/2018/main.lisp Fri Dec 07 20:58:35 2018 -0500
+++ b/src/2018/main.lisp Sun Dec 09 20:59:39 2018 -0500
@@ -207,7 +207,7 @@
(let ((graph (make-graph (mapcar #'parse-line data))))
;; (digraph.dot:draw graph)
(recursively ((result nil))
- (if (digraph:emptyp graph)
+ (if (emptyp graph)
(coerce (nreverse result) 'string)
(let ((next (extremum (digraph:leafs graph) 'char<)))
(digraph:remove-vertex graph next)
@@ -230,5 +230,36 @@
(when (null worker)
(when-let ((task (pop available-tasks)))
(setf worker (cons task (task-length task))))))
- (when (and (digraph:emptyp graph) (every #'null workers))
+ (when (and (emptyp graph) (every #'null workers))
(return elapsed))))))
+
+
+(define-problem (2018 8) (data)
+ (labels
+ ((make-node (children metadata) (cons metadata children))
+ (children (node) (cdr node))
+ (metadata (node) (car node))
+ (read-node (stream)
+ (let* ((children-count (read stream))
+ (metadata-count (read stream))
+ (children (iterate
+ (repeat children-count)
+ (collect (read-node stream) :result-type vector)))
+ (metadata (iterate
+ (repeat metadata-count)
+ (collect (read stream)))))
+ (make-node children metadata)))
+ (node-value (node &aux (children (children node)))
+ (if (emptyp children)
+ (summation (metadata node))
+ (iterate
+ (for meta :in (metadata node))
+ (for index = (1- meta))
+ (when (array-in-bounds-p children index)
+ (summing (node-value (aref children index))))))))
+ (let ((root (read-node data)))
+ (values
+ (recursively ((node root))
+ (+ (summation (metadata node))
+ (summation (children node) :key #'recur)))
+ (node-value root)))))
--- a/src/utils.lisp Fri Dec 07 20:58:35 2018 -0500
+++ b/src/utils.lisp Sun Dec 09 20:59:39 2018 -0500
@@ -2,14 +2,18 @@
;;;; Problems -----------------------------------------------------------------
(defmacro define-problem ((year day &optional part)
- (data-symbol reader)
+ (data-symbol &optional reader)
&body body)
(let ((function-name (if part
(symb 'advent- year '- day '/ part)
- (symb 'advent- year '- day))))
+ (symb 'advent- year '- day)))
+ (path (format nil "data/~D/~2,'0D.txt" year day)))
`(defun ,function-name ()
- (let ((,data-symbol (,reader ,(format nil "data/~D/~2,'0D.txt" year day))))
- ,@body))))
+ ,(if (null reader)
+ `(with-open-file (,data-symbol ,path)
+ ,@body)
+ `(let ((,data-symbol (,reader ,path)))
+ ,@body)))))
;;;; Readers ------------------------------------------------------------------
@@ -155,3 +159,22 @@
(+ point #c(1 0))
(+ point #c(0 -1))
(+ point #c(-1 0))))
+
+
+(defgeneric emptyp (collection)
+ (:documentation "Return whether `collection` is empty."))
+
+(defmethod emptyp ((list list))
+ (null list))
+
+(defmethod emptyp ((vector vector))
+ (zerop (length vector)))
+
+(defmethod emptyp ((hash-table hash-table))
+ (zerop (hash-table-count hash-table)))
+
+(defmethod emptyp ((digraph digraph:digraph))
+ (digraph:emptyp digraph))
+
+(defmethod emptyp ((hset hash-set))
+ (hset-empty-p hset))