2 files changed, 102 insertions, 0 deletions
diff --git a/2021/16/code.tl b/2021/16/code.tl
new file mode 100644
index 0000000..8f2016e
--- /dev/null
+++ b/2021/16/code.tl
@@ -0,0 +1,101 @@
+(defstruct bitstream ()
+  bf
+  st
+  pfx
+  (count 0))
+
+(defstruct packet ()
+  version
+  type
+  payload)
+
+(defmeth bitstream read-file (bs : (name "input"))
+  bs.(read-string (file-get-string name)))
+
+(defmeth bitstream read-string (bs s)
+  (set bs.bf (buf-uint (toint s 16))
+       bs.st (make-buf-stream bs.bf))
+  bs.(ensure-prefix 24))
+
+(defmeth bitstream ensure-prefix (bs n)
+  (whilet ((b (and (< (len bs.pfx) n) (get-byte bs.st))))
+    (upd bs.pfx (nconc @1 (flow b (+ 256) (digits @1 2) cdr))))
+  bs)
+
+(defmeth bitstream set-pfx (bs npfx)
+  (placelet ((pfx (read-once bs.pfx))
+             (count (read-once bs.count)))
+    (while (neq pfx npfx)
+      (inc count)
+      (upd pfx cdr)))
+  bs.(ensure-prefix 24))
+
+(defmeth bitstream drop-zeros (bs)
+  (while-match (0 . @rest) bs.pfx
+    bs.(set-pfx rest))
+  bs)
+
+(defmacro val (. bits)
+  ^(poly 2 (list ,*bits)))
+
+(defmeth bitstream parse-header (bs)
+  (match (@v2 @v1 @v0 @t2 @t1 @t0 . @rest)
+         bs.pfx
+    bs.(set-pfx rest)
+    (new packet
+         version (val v2 v1 v0)
+         type (val t2 t1 t0))))
+
+(defmeth packet parse-payload (pk bs)
+  (caseq pk.type
+    (4 (let ((value 0))
+         (while-match (@more @v3 @v2 @v1 @v0 . @rest) bs.pfx
+           bs.(set-pfx rest)
+           (upd value (* 16) (+ (val v3 v2 v1 v0)))
+           (if (zerop more)
+             (return)))
+         (set pk.payload value)))
+    (t (match-case bs.pfx
+         ((0 . @rest)
+          bs.(set-pfx (drop 15 rest))
+          (let ((nbits (poly 2 (take 15 rest)))
+                (count bs.count))
+            (set pk.payload
+                 (build
+                   (while (< (- bs.count count) nbits)
+                     (add bs.(parse-header).(parse-payload bs)))))))
+         ((1 . @rest)
+          bs.(set-pfx (drop 11 rest))
+          (let ((npkt (poly 2 (take 11 rest))))
+            (set pk.payload
+                 (build
+                   (dotimes (i npkt)
+                     (add bs.(parse-header).(parse-payload bs))))))))))
+  pk)
+
+(defmeth packet version-sum (pk)
+  (+ pk.version
+     (ifa (listp pk.payload)
+       (sum it .(version-sum))
+       0)))
+
+(defun get-packet (: (name "input"))
+  (let* ((bs (new bitstream).(read-file name).(drop-zeros)))
+    bs.(parse-header).(parse-payload bs)))
+
+(defun compile-packet (pk)
+  (let ((mathfun (relate '(0 1 2 3) '(+ * min max) nil))
+        (relfun (relate '(5 6 7) '(> < =) nil)))
+    (match-case pk
+      (@(struct packet type 4 payload @(integerp @literal)) literal)
+      (@(struct packet type @(@fun [mathfun]) payload @args) ^(,fun ,*[mapcar compile-packet args]))
+      (@(struct packet type @(@fun [relfun]) payload @args) ^(if (,fun ,*[mapcar compile-packet args]) 1 0))
+      (@else (error "invalid syntax ~s" else)))))
+
+(defun solve-one (: (name :))
+  (let ((pk (get-packet name)))
+    pk.(version-sum)))
+
+(defun solve-two (: (name :))
+  (let ((pk (get-packet name)))
+    (eval (compile-packet pk))))
diff --git a/2021/16/input b/2021/16/input
new file mode 100644
index 0000000..10fa873
--- /dev/null
+++ b/2021/16/input
@@ -0,0 +1 @@
+820D4100A1000085C6E8331F8401D8E106E1680021708630C50200A3BC01495B99CF6852726A88014DC9DBB30798409BBDF5A4D97F5326F050C02F9D2A971D9B539E0C93323004B4012960E9A5B98600005DA7F11AFBB55D96AFFBE1E20041A64A24D80C01E9D298AF0E22A98027800BD4EE3782C91399FA92901936E0060016B82007B0143C2005280146005300F7840385380146006900A72802469007B0001961801E60053002B2400564FFCE25FEFE40266CA79128037500042626C578CE00085C718BD1F08023396BA46001BF3C870C58039587F3DE52929DFD9F07C9731CC601D803779CCC882767E668DB255D154F553C804A0A00DD40010B87D0D6378002191BE11C6A914F1007C8010F8B1122239803B04A0946630062234308D44016CCEEA449600AC9844A733D3C700627EA391EE76F9B4B5DA649480357D005E622493112292D6F1DF60665EDADD212CF8E1003C29193E4E21C9CF507B910991E5A171D50092621B279D96F572A94911C1D200FA68024596EFA517696EFA51729C9FB6C64019250034F3F69DD165A8E33F7F919802FE009880331F215C4A1007A20C668712B685900804ABC00D50401C89715A3B00021516E164409CE39380272B0E14CB1D9004632E75C00834DB64DB4980292D3918D0034F3D90C958EECD8400414A11900403307534B524093EBCA00BCCD1B26AA52000FB4B6C62771CDF668E200CC20949D8AE2790051133B2ED005E2CC953FE1C3004EC0139ED46DBB9AC9C2655038C01399D59A3801F79EADAD878969D8318008491375003A324C5A59C7D68402E9B65994391A6BCC73A5F2FEABD8804322D90B25F3F4088F33E96D74C0139CF6006C0159BEF8EA6FBE3A9CEC337B859802B2AC9A0084C9DCC9ECD67DD793004E669FA2DE006EC00085C558C5134001088E308A20