# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1639635831 18000
# Node ID 3895878bfe72a3c804c58d62306bc321561b1762
# Parent  e41337e3b59b7817c7323493e770c8f89ebed98c
2021/16

diff -r e41337e3b59b -r 3895878bfe72 data/2021/16.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2021/16.txt	Thu Dec 16 01:23:51 2021 -0500
@@ -0,0 +1,1 @@
+0052E4A00905271049796FB8872A0D25B9FB746893847236200B4F0BCE5194401C9B9E3F9C63992C8931A65A1CCC0D222100511A00BCBA647D98BE29A397005E55064A9DFEEC86600BD002AF2343A91A1CCE773C26600D126B69D15A6793BFCE2775D9E4A9002AB86339B5F9AB411A15CCAF10055B3EFFC00BCCE730112FA6620076268CE5CDA1FCEB69005A3800D24F4DB66E53F074F811802729733E0040E5C5E5C5C8015F9613937B83F23B278724068018014A00588014005519801EC04B220116CC0402000EAEC03519801A402B30801A802138801400170A0046A800C10001AB37FD8EB805D1C266963E95A4D1A5FF9719FEF7FDB4FB2DB29008CD2BAFA3D005CD31EB4EF2EBE4F4235DF78C66009E80293AE9310D3FCBFBCA440144580273BAEE17E55B66508803C2E0087E630F72BCD5E71B32CCFBBE2800017A2C2803D272BCBCD12BD599BC874B939004B5400964AE84A6C1E7538004CD300623AC6C882600E4328F710CC01C82D1B228980292ECD600B48E0526E506F700760CCC468012E68402324F9668028200C41E8A30E00010D8B11E62F98029801AB88039116344340004323EC48873233E72A36402504CB75006EA00084C7B895198001098D91AE2190065933AA6EB41AD0042626A93135681A400804CB54C0318032200E47B8F71C0001098810D61D8002111B228468000E5269324AD1ECF7C519B86309F35A46200A1660A280150968A4CB45365A03F3DDBAE980233407E00A80021719A1B4181006E1547D87C6008E0043337EC434C32BDE487A4AE08800D34BC3DEA974F35C20100BE723F1197F59E662FDB45824AA1D2DDCDFA2D29EBB69005072E5F2EDF3C0B244F30E0600AE00203229D229B342CC007EC95F5D6E200202615D000FB92CE7A7A402354EE0DAC0141007E20C5E87A200F4318EB0C
diff -r e41337e3b59b -r 3895878bfe72 src/2021/days/day-16.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2021/days/day-16.lisp	Thu Dec 16 01:23:51 2021 -0500
@@ -0,0 +1,59 @@
+(advent:defpackage* :advent/2021/16)
+(in-package :advent/2021/16)
+
+(defun parse (stream)
+  (let ((line (read-line stream)))
+    (values (parse-integer line :radix 16)
+            (* 4 (length line)))))
+
+(defun-inline rldb (size pos byte)
+  (ldb (byte size (- pos (1- size))) byte))
+
+(defun gt (a b) (if (> a b) 1 0))
+(defun lt (a b) (if (< a b) 1 0))
+(defun == (a b) (if (= a b) 1 0))
+
+(defun packets (data length &aux (i (1- length)))
+  (labels ((pop-bits (size)
+             (prog1 (rldb size i data) (decf i size)))
+           (parse-literal ()
+             (iterate (for marker = (pop-bits 1))
+                      (for chunk = (pop-bits 4))
+                      (collect chunk :into result)
+                      (until (zerop marker))
+                      (finally (return (digits->number result :radix 16)))))
+           (parse-operator ()
+             (ecase (pop-bits 1)
+               (0 (loop :with subpacket-length = (pop-bits 15)
+                        :with end = (- i subpacket-length)
+                        :while (> i end)
+                        :collect (parse-packet)))
+               (1 (loop :with number-of-subpackets = (pop-bits 11)
+                        :repeat number-of-subpackets
+                        :collect (parse-packet)))))
+           (op (type-id)
+             (aref #(+ * min max quote gt lt ==) type-id))
+           (parse-packet ()
+             (let ((version (pop-bits 3))
+                   (type-id (pop-bits 3)))
+               (list* :version version :op (op type-id)
+                      (case type-id
+                        (4 (list :value (parse-literal)))
+                        (t (list :contents (parse-operator))))))))
+    (parse-packet)))
+
+(defun version-sum (packet)
+  (reduce #'+ (getf packet :contents)
+          :key #'version-sum :initial-value (getf packet :version)))
+
+(defun packet-sum (packet &aux (op (getf packet :op)))
+  (case op
+    (quote (getf packet :value))
+    (t (reduce (getf packet :op) (getf packet :contents) :key #'packet-sum))))
+
+(define-problem (2021 16) (stream) (986 18234816469452)
+  (multiple-value-bind (data length) (parse stream)
+    (let ((packets (packets data length)))
+      (values (version-sum packets) (packet-sum packets)))))
+
+#; Scratch --------------------------------------------------------------------