Skip to content

Latest commit

 

History

History
303 lines (278 loc) · 9 KB

2018.08.org

File metadata and controls

303 lines (278 loc) · 9 KB

Day 8

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2018-08)
  4. Typing C-c C-c in the block answers.

Initial stuffs

Packages to load

(unless (find-package :cl-ppcre)
  (ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
  (ql:quickload "iterate"))
(unless (find-package :parseq)
  (ql:quickload "parseq"))
(unless (find-package :fiveam)
  (ql:quickload "fiveam"))

Create package for this day

<<packages>>
(defpackage :aoc-2018-08
  (:use
   :common-lisp
   :iterate
   :parseq
   :fiveam)
  (:export
   :problem-a
   :problem-b))
(in-package :aoc-2018-08)

Input

Using the stream to help with parsing. I was really trying to do this a different way (read the whole file into a list and then convert that into a tree). But I kept getting tripped up. Ultimately, I was able to gather the metadata doing that but I couldn’t quite restore the tree structure itself.

The code got really ugly, so this version is better. The code I had was recursive like this, but had multiple value returns: the newly constructed child node and a list with all the data used in constructing that node removed. It wasn’t very readable, and it was a bear to try to debug.

(defstruct node
  (children nil)
  (metadata nil))
(defun make-tree (stream)
  (let* ((child-count (read stream))
         (metadata-count (read stream))
         (children (iter (repeat child-count)
                         (collect (make-tree stream))))
         (metadata (iter (repeat metadata-count)
                         (collect (read stream)))))
    (make-node :children children :metadata metadata)))

The problem I ran into is illustrated here:

(defun do-something (list)
  (format t "~a~%" list)
  (pop list)
  (format t "~a~%" list))
(let ((list (list 1 2 3)))
  (format t "~a~%" list)
  (do-something list)
  (format t "~a~%" list))
(1 2 3)
(1 2 3)
(2 3)
(1 2 3)

So I originally had a recursive call like:

(defun make-tree-flawed (list)
  (let* ((child-count (pop list))
         (metadata-count (pop list))
         (children (iter (repeat child-count)
                         (collect (make-tree-flawed list))))
         (metadata (iter (repeat metadata-count)
                         (collect (pop list)))))
    (make-node :children children :metadata metadata)))

(NB: The original was more complicated, but amounted to the same logic).

The output of the above is garbage.

To have the effect I wanted, I needed the same list variable to be in the scope of all the recursive calls. This required a local recursive function:

(defun make-tree-list (list)
  (labels ((recurse ()
             (let* ((child-count (pop list))
                    (metadata-count (pop list))
                    (children (iter (repeat child-count)
                                    (collect (recurse))))
                    (metadata (iter (repeat metadata-count)
                                    (collect (pop list)))))
               (make-node :children children :metadata metadata))))
    (recurse)))

Now that recursive version, converting lists to trees, works just fine. Though I’m not using it.

(defun read-input (file)
  (with-open-file (s file)
    (make-tree s)))
<<read-input>>
(defparameter *input*
  (read-input "input/8.txt"))

Part 1

Part 1 wants the sum of the metadata of each node. This is a straightforward recursive solution.

(defun sum-tree (node)
  (+ (iter (for c in (node-children node))
           (sum (sum-tree c)))
     (reduce #'+ (node-metadata node))))
(defun problem-a () (format t "Problem 8a: ~a~%" (sum-tree *input*)))

Part 2

Node value is defined as either:

If the node has no children, the sum of its metadata.

If the node has children, the sum of the nodes referenced by the metadata. If the metadata refers to a non-existent node, its value is considered 0.

Another recursive solution. The only other complexity is that the input assumes sequence access starts at 1, while lisp uses 0 as the first element. So we have to decrement 1 from the metadata values to get the index.

(defun node-value (node)
  (let ((children (node-children node))
        (metadata (node-metadata node)))
    (cond ((null children) (reduce #'+ metadata))
          (t (iter (for m in metadata)
                   (unless (or (= 0 m) (> m (length children)))
                     (sum (node-value (elt children (1- m))))))))))
(defun problem-b () (format t "Problem 8b: ~a~%" (node-value *input*)))

Putting it all together

<<node>>
<<make-tree>>
<<node-value>>
<<sum-tree>>
<<structs>>
<<input>>
<<functions>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)

Answer

Problem 8a: 37439
Problem 8b: 20815

Thoughts

I had too much trouble on parsing this one. So I started playing around with a parsing library called parseq.

(with-local-rules
  (defrule node () (and child-count metadata-count children metadata)
    (:let (nc 0))
    (:let (nm 0))
    (:lambda (cc mc c m)
      (make-node :children c :metadata m)))
  (defrule child-count () integer (:external nc)
           (:lambda (x)
             (setf nc x)))
  (defrule metadata-count () integer (:external nm)
           (:lambda (x)
             (setf nm x)))
  (defrule children () (rep nc node) (:external nc))
  (defrule metadata () (rep nm integer) (:external nm))
  (parseq 'node (list 2  2 0 1 100 0 1 1000 1 3)))
;; => (2 2 ((0 1 NIL (100)) (0 1 NIL (1000))) (1 3))
;; => T

The above will parse the list (rather than the stream) of data as I was wanting it to do from the start. I’ll now take that and make it into a function.

(defun list-to-tree (list)
  (with-local-rules
    (defrule node () (and child-count metadata-count children metadata)
      (:let (nc 0))
      (:let (nm 0))
      (:Lambda (cc mc c m)
        (declare (ignore cc mc))
        (make-node :children c :metadata m)))
    (defrule child-count () integer (:external nc)
             (:lambda (x)
               (setf nc x)))
    (defrule metadata-count () integer (:external nm)
             (:lambda (x)
               (setf nm x)))
    (defrule children () (rep nc node) (:external nc))
    (defrule metadata () (rep nm integer) (:external nm))
    (parseq 'node list)))

Now we’ll load up the test data from the problem page:

(defvar *test-list* (list 2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2))

And let’s test the parser:

(list-to-tree *test-list*)
#S(NODE
   :CHILDREN (#S(NODE :CHILDREN NIL :METADATA (10 11 12))
              #S(NODE
                 :CHILDREN (#S(NODE :CHILDREN NIL :METADATA (99)))
                 :METADATA (2)))
   :METADATA (1 1 2))
T

That looks right, so now let’s test it against the expected results.

(def-suite day8-suite :description "Test cases for Day 8")
(in-suite day8-suite)
(test sum-tree-test
  (is (= (sum-tree (list-to-tree *test-list*)) 138)))
(test node-value-test
  (is (= (node-value (list-to-tree *test-list*)) 66)))
(run! 'day8-suite)
Running test suite DAY8-SUITE
 Running test SUM-TREE-TEST .
 Running test NODE-VALUE-TEST .
 Did 2 checks.
    Pass: 2 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)

I’ll attempt to use both 5am and parseq from the start on the next problem to cover testing and parsing.