2 files changed, 72 insertions, 0 deletions
diff --git a/2021/16.hs b/2021/16.hs
new file mode 100644
index 0000000..6432014
--- /dev/null
+++ b/2021/16.hs
@@ -0,0 +1,71 @@
+module Main where
+
+import Data.Bifunctor (first, second)
+import Data.Bits
+import Numeric.Natural
+
+import Input
+
+
+data Packet = Lit Int Natural | Op Int Int [Packet]
+  deriving (Show)
+
+dec :: [Bool] -> Natural
+dec l = sum (zipWith (*) (map (fromIntegral . fromEnum) (reverse l)) (iterate (*2) 1))
+
+parse :: [Bool] -> (Packet, [Bool])
+parse l =
+    let (ver, l1) = splitAt 3 l
+        (typ, l2) = splitAt 3 l1
+    in case dec typ of
+         4 -> let collectGroups m =
+                    let (g1, m1) = splitAt 5 m
+                    in case g1 of False : g1' -> (g1', m1)
+                                  True : g1' -> first (g1' ++) (collectGroups m1)
+                                  [] -> error "Unexpected EOF in literal"
+              in first (Lit (fromIntegral (dec ver)) . dec) (collectGroups l2)
+         typ' | False : l3 <- l2 ->
+                  let (bodylen, l4) = splitAt 15 l3
+                      (body, l5) = splitAt (fromIntegral (dec bodylen)) l4
+                  in (Op (fromIntegral (dec ver)) (fromIntegral typ') (parseMany body), l5)
+              | True : l3 <- l2 ->
+                  let (numpkt, l4) = splitAt 11 l3
+                      (pkts, l5) = parseN (dec numpkt) l4
+                  in (Op (fromIntegral (dec ver)) (fromIntegral typ') pkts, l5)
+              | otherwise -> error "Unexpected EOF before length ID bit in operator"
+
+parseMany :: [Bool] -> [Packet]
+parseMany [] = []
+parseMany l = uncurry (:) (second parseMany (parse l))
+
+parseN :: Natural -> [Bool] -> ([Packet], [Bool])
+parseN 0 l = ([], l)
+parseN n l = let (pkt, rest) = parse l
+                 (pkts, rest') = parseN (n - 1) rest
+             in (pkt : pkts, rest')
+
+operator :: Int -> [Natural] -> Natural
+operator 0 = sum
+operator 1 = product
+operator 2 = minimum
+operator 3 = maximum
+operator 5 = \[a,b] -> fromIntegral (fromEnum (a > b))
+operator 6 = \[a,b] -> fromIntegral (fromEnum (a < b))
+operator 7 = \[a,b] -> fromIntegral (fromEnum (a == b))
+operator n = error ("Invalid operator " ++ show n)
+
+eval :: Packet -> Natural
+eval (Lit _ n) = n
+eval (Op _ n ps) = operator n (map eval ps)
+
+main :: IO ()
+main = do
+    let decodeHex c | '0' <= c, c <= '9' = fromEnum c - fromEnum '0'
+                    | 'A' <= c, c <= 'F' = 10 + fromEnum c - fromEnum 'A'
+                    | otherwise = error "Invalid hex digit"
+        toBinary4 n = [testBit n i | i <- [3,2,1,0]]
+    bits <- concatMap (toBinary4 . decodeHex) . head <$> getInput 16
+    let addVers (Lit v _) = v
+        addVers (Op v _ ps) = v + sum (map addVers ps)
+    print (addVers (fst (parse bits)))
+    print (eval (fst (parse bits)))
diff --git a/2021/16.in b/2021/16.in
new file mode 100644
index 0000000..3c7410e
--- /dev/null
+++ b/2021/16.in
@@ -0,0 +1 @@
+620D49005AD2245800D0C9E72BD279CAFB0016B1FA2B1802DC00D0CC611A47FCE2A4ACE1DD144BFABBFACA002FB2C6F33DFF4A0C0119B169B013005F003720004263644384800087C3B8B51C26B449130802D1A0068A5BD7D49DE793A48B5400D8293B1F95C5A3005257B880F5802A00084C788AD0440010F8490F608CACE034401AB4D0F5802726B3392EE2199628CEA007001884005C92015CC8051800130EC0468A01042803B8300D8E200788018C027890088CE0049006028012AB00342A0060801B2EBE400424933980453EFB2ABB36032274C026E4976001237D964FF736AFB56F254CB84CDF136C1007E7EB42298FE713749F973F7283005656F902A004067CD27CC1C00D9CB5FDD4D0014348010C8331C21710021304638C513006E234308B060094BEB76CE3966AA007C6588A5670DC3754395485007A718A7F149CA2DD3B6E7B777800118E7B59C0ECF5AE5D3B6CB1496BAE53B7ADD78C013C00CD2629BF5371D1D4C537EA6E3A3E95A3E180592AC7246B34032CF92804001A1CCF9BA521782ECBD69A98648BC18025800F8C9C37C827CA7BEFB31EADF0AE801BA42B87935B8EF976194EEC426AAF640168CECAF84BC004AE7D1673A6A600B4AB65802D230D35CF81B803D3775683F3A3860087802132FB32F322C92A4C402524F2DE006E8000854378F710C0010D8F30FE224AE428C015E00D40401987F06E3600021D0CE3EC228DA000574E4C3080182931E936E953B200BF656E15400D3496E4A725B92998027C00A84EEEE6B347D30BE60094E537AA73A1D600B880371AA36C3200043235C4C866C018E4963B7E7AA2B379918C639F1550086064BB148BA499EC731004E1AC966BDBC7646600C080370822AC4C1007E38C428BE0008741689D0ECC01197CF216EA16802D3748FE91B25CAF6D5F11C463004E4FD08FAF381F6004D3232CC93E7715B463F780