diff options
| -rw-r--r-- | 2021/16.hs | 71 | ||||
| -rw-r--r-- | 2021/16.in | 1 |
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 |