From bf8e77441bb6ae200a29b32a04d8607a41c03e93 Mon Sep 17 00:00:00 2001
From: Ben Harris <ben@tilde.team>
Date: Thu, 16 Dec 2021 11:48:02 -0500
Subject: day 16

feeling glad for Enumerable.Chunk today so i didn't have to write my own
---
 aoc2021.test/DayTests.cs |  2 ++
 aoc2021/Day16.cs         | 87 ++++++++++++++++++++++++++++++++++++++++++++++++
 aoc2021/input/day16.in   |  1 +
 aoc2021/input/test16.in  |  1 +
 4 files changed, 91 insertions(+)
 create mode 100644 aoc2021/Day16.cs
 create mode 100644 aoc2021/input/day16.in
 create mode 100644 aoc2021/input/test16.in

diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs
index 8cc3484..09d2e89 100644
--- a/aoc2021.test/DayTests.cs
+++ b/aoc2021.test/DayTests.cs
@@ -36,6 +36,7 @@ public class DayTests
     [DataRow(typeof(Day13), "837", Day13Actual)]
     [DataRow(typeof(Day14), "5656", "12271437788530")]
     [DataRow(typeof(Day15), "702", "2955")]
+    [DataRow(typeof(Day16), "852", "19348959966392")]
     public void CheckAllDays(Type dayType, string part1, string part2)
     {
         var s = Stopwatch.StartNew();
@@ -81,6 +82,7 @@ public class DayTests
     [DataRow(typeof(Day13), "17", Day13Test)]
     [DataRow(typeof(Day14), "1588", "2188189693529")]
     [DataRow(typeof(Day15), "40", "315")]
+    [DataRow(typeof(Day16), "16", "15")]
     public void CheckTestInputs(Type dayType, string part1, string part2)
     {
         Day.UseTestInput = true;
diff --git a/aoc2021/Day16.cs b/aoc2021/Day16.cs
new file mode 100644
index 0000000..7e956f3
--- /dev/null
+++ b/aoc2021/Day16.cs
@@ -0,0 +1,87 @@
+namespace aoc2021;
+
+/// <summary>
+/// Day 16: <see href="https://adventofcode.com/2021/day/16"/>
+/// </summary>
+public sealed class Day16 : Day
+{
+    private readonly Packet _packet;
+
+    public Day16() : base(16, "Packet Decoder")
+    {
+        var bits = string.Join(string.Empty,
+            Input.First().Select(c => Convert.ToString(Convert.ToInt32(c.ToString(), 16), 2).PadLeft(4, '0')));
+        (_packet, _) = Packet.FromBinaryString(bits);
+    }
+
+    private record Packet(int Version, int TypeId, long Value, List<Packet> Packets)
+    {
+        public static (Packet packet, int offset) FromBinaryString(string input)
+        {
+            var index = 0;
+            var subPackets = new List<Packet>();
+            var version = Convert.ToInt32(input[..(index += 3)], 2);
+            var typeId = Convert.ToInt32(input[index..(index += 3)], 2);
+
+            if (typeId == 4)
+            {
+                // value packet, gather value bits and return right away
+                var literalBits = new StringBuilder();
+                foreach (var chunk in input.Skip(index).Chunk(5))
+                {
+                    literalBits.Append(chunk[1..5]);
+                    index += 5;
+                    if (chunk[0] == '0') break;
+                }
+
+                return (new(version, typeId, Convert.ToInt64(literalBits.ToString(), 2), new()), index);
+            }
+
+            switch (input[index++])
+            {
+                case '0':
+                    var subPacketLength = Convert.ToInt32(input[index..(index += 15)], 2);
+                    while (subPacketLength > 0)
+                    {
+                        var (packet, offset) = FromBinaryString(input[index..(index + subPacketLength)]);
+                        subPackets.Add(packet);
+                        subPacketLength -= offset;
+                        index += offset;
+                    }
+
+                    break;
+                case '1':
+                    foreach (var _ in Enumerable.Range(0, Convert.ToInt32(input[index..(index += 11)], 2)))
+                    {
+                        var (packet, offset) = FromBinaryString(input[index..]);
+                        subPackets.Add(packet);
+                        index += offset;
+                    }
+
+                    break;
+            }
+
+            return (new(version, typeId, 0, subPackets), index);
+        }
+
+        public long VersionTotal => Version + Packets.Sum(p => p.VersionTotal);
+
+        public long Eval =>
+            TypeId switch
+            {
+                0 => Packets.Sum(p => p.Eval),
+                1 => Packets.Aggregate(1L, (p, i) => p * i.Eval),
+                2 => Packets.Min(p => p.Eval),
+                3 => Packets.Max(p => p.Eval),
+                4 => Value,
+                5 => Packets[0].Eval > Packets[1].Eval ? 1 : 0,
+                6 => Packets[0].Eval < Packets[1].Eval ? 1 : 0,
+                7 => Packets[0].Eval == Packets[1].Eval ? 1 : 0,
+                _ => throw new ArgumentException("invalid packet type", nameof(TypeId))
+            };
+    }
+
+    public override object Part1() => _packet.VersionTotal;
+
+    public override object Part2() => _packet.Eval;
+}
\ No newline at end of file
diff --git a/aoc2021/input/day16.in b/aoc2021/input/day16.in
new file mode 100644
index 0000000..933fe91
--- /dev/null
+++ b/aoc2021/input/day16.in
@@ -0,0 +1 @@
+C20D718021600ACDC372CD8DE7A057252A49C940239D68978F7970194EA7CCB310088760088803304A0AC1B100721EC298D3307440041CD8B8005D12DFD27CBEEF27D94A4E9B033006A45FE71D665ACC0259C689B1F99679F717003225900465800804E39CE38CE161007E52F1AEF5EE6EC33600BCC29CFFA3D8291006A92CA7E00B4A8F497E16A675EFB6B0058F2D0BD7AE1371DA34E730F66009443C00A566BFDBE643135FEDF321D000C6269EA66545899739ADEAF0EB6C3A200B6F40179DE31CB7B277392FA1C0A95F6E3983A100993801B800021B0722243D00042E0DC7383D332443004E463295176801F29EDDAA853DBB5508802859F2E9D2A9308924F9F31700AA4F39F720C733A669EC7356AC7D8E85C95E123799D4C44C0109C0AF00427E3CC678873F1E633C4020085E60D340109E3196023006040188C910A3A80021B1763FC620004321B4138E52D75A20096E4718D3E50016B19E0BA802325E858762D1802B28AD401A9880310E61041400043E2AC7E8A4800434DB24A384A4019401C92C154B43595B830002BC497ED9CC27CE686A6A43925B8A9CFFE3A9616E5793447004A4BBB749841500B26C5E6E306899C5B4C70924B77EF254B48688041CD004A726ED3FAECBDB2295AEBD984E08E0065C101812E006380126005A80124048CB010D4C03DC900E16A007200B98E00580091EE004B006902004B00410000AF00015933223100688010985116A311803D05E3CC4B300660BC7283C00081CF26491049F3D690E9802739661E00D400010A8B91F2118803310A2F43396699D533005E37E8023311A4BB9961524A4E2C027EC8C6F5952C2528B333FA4AD386C0A56F39C7DB77200C92801019E799E7B96EC6F8B7558C014977BD00480010D89D106240803518E31C4230052C01786F272FF354C8D4D437DF52BC2C300567066550A2A900427E0084C254739FB8E080111E0
diff --git a/aoc2021/input/test16.in b/aoc2021/input/test16.in
new file mode 100644
index 0000000..0d2cbff
--- /dev/null
+++ b/aoc2021/input/test16.in
@@ -0,0 +1 @@
+8A004A801A8002F478
-- 
cgit 1.4.1