aoc18/day8.lisp -rw-r--r-- 1.4 KiB View raw
                                                                                
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
(in-package :aoc18)

(defstruct node
  (children nil)
  (meta nil))

(defun read-header (in) (list (car in) (cadr in)))

(defun parse-nodes (in nodes)
  (let ((current in)
	(children nil))
    (loop for x from 0 below nodes do
	 (let* ((h (read-header current))
		(n (car h))
		(m (cadr h))
		(rest (cddr current))
		(subchildren nil))
	   (when (> n 0)
	     (multiple-value-bind (c r) (parse-nodes rest n)
	       (setf subchildren c rest r)))
	   (push (make-node :children subchildren :meta (subseq rest 0 m)) children)
	   (setf current (subseq rest m))))
    (values (reverse children) current)))

(defun sum-metadata (root)
  (+ (apply #'+ (node-meta root))
     (loop for n in (node-children root) summing (sum-metadata n))))

(defun solve-day8-part1 (input)
  (sum-metadata (car (parse-nodes input 1))))

(defun read-day8-input (path)
  (mapcar #'parse-integer (cl-ppcre:split " " (file-string path))))

(test day8-part1
  (is (= 42501 (solve-day8-part1 (read-day8-input "day8.input")))))

(defun sum-node (root)
  (cond
    ((null root) 0)
    ((empty-p (node-children root)) (apply #'+ (node-meta root)))
    (t (sum-nodes (mapcar #'1- (node-meta root)) (node-children root)))))

(defun sum-nodes (indexes nodes)
  (loop for i in indexes summing (sum-node (nth i nodes))))

(defun solve-day8-part2 (input)
  (sum-node (car (parse-nodes input 1))))

(test day8-part2
  (is (= 30857 (solve-day8-part2 (read-day8-input "day8.input")))))