commit f432e372d1ce4ab00e3de4ff340e810c2e3e0ee1
parent 040054052d4ae34c19d6d0cabfd515183af4a918
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Thu, 16 Dec 2021 22:24:55 -0600
Add 2021 day 16
Diffstat:
2 files changed, 131 insertions(+), 0 deletions(-)
diff --git a/2021/day16/input.txt b/2021/day16/input.txt
@@ -0,0 +1 @@
+420D50000B318100415919B24E72D6509AE67F87195A3CCC518CC01197D538C3E00BC9A349A09802D258CC16FC016100660DC4283200087C6485F1C8C015A00A5A5FB19C363F2FD8CE1B1B99DE81D00C9D3002100B58002AB5400D50038008DA2020A9C00F300248065A4016B4C00810028003D9600CA4C0084007B8400A0002AA6F68440274080331D20C4300004323CC32830200D42A85D1BE4F1C1440072E4630F2CCD624206008CC5B3E3AB00580010E8710862F0803D06E10C65000946442A631EC2EC30926A600D2A583653BE2D98BFE3820975787C600A680252AC9354FFE8CD23BE1E180253548D057002429794BD4759794BD4709AEDAFF0530043003511006E24C4685A00087C428811EE7FD8BBC1805D28C73C93262526CB36AC600DCB9649334A23900AA9257963FEF17D8028200DC608A71B80010A8D50C23E9802B37AA40EA801CD96EDA25B39593BB002A33F72D9AD959802525BCD6D36CC00D580010A86D1761F080311AE32C73500224E3BCD6D0AE5600024F92F654E5F6132B49979802129DC6593401591389CA62A4840101C9064A34499E4A1B180276008CDEFA0D37BE834F6F11B13900923E008CF6611BC65BCB2CB46B3A779D4C998A848DED30F0014288010A8451062B980311C21BC7C20042A2846782A400834916CFA5B8013374F6A33973C532F071000B565F47F15A526273BB129B6D9985680680111C728FD339BDBD8F03980230A6C0119774999A09001093E34600A60052B2B1D7EF60C958EBF7B074D7AF4928CD6BA5A40208E002F935E855AE68EE56F3ED271E6B44460084AB55002572F3289B78600A6647D1E5F6871BE5E598099006512207600BCDCBCFD23CE463678100467680D27BAE920804119DBFA96E05F00431269D255DDA528D83A577285B91BCCB4802AB95A5C9B001299793FCD24C5D600BC652523D82D3FCB56EF737F045008E0FCDC7DAE40B64F7F799F3981F2490
diff --git a/2021/day16/main.rs b/2021/day16/main.rs
@@ -0,0 +1,130 @@
+#[derive(Debug, Clone)]
+enum PacketContent {
+ Literal(u64),
+ SubPackets(Vec<Packet>),
+}
+
+#[derive(Debug, Clone)]
+struct Packet {
+ version: u32,
+ type_id: u32,
+ content: PacketContent,
+}
+
+fn read_bits(buf: &[u8], cursor: &mut usize, span: usize) -> u32 {
+ let mut value: u32 = 0;
+ for _ in 0..span {
+ let buf_idx = *cursor / 4;
+ let offset = 3 - *cursor % 4;
+ value <<= 1;
+ value += (buf[buf_idx] & (1 << offset)) as u32 >> offset;
+ *cursor += 1;
+ }
+ value
+}
+
+impl Packet {
+ fn parse(buf: &[u8], start: usize) -> (Packet, usize) {
+ let mut cursor = start;
+ let version = read_bits(buf, &mut cursor, 3);
+ let type_id = read_bits(buf, &mut cursor, 3);
+ match type_id {
+ 4 => {
+ let mut value = 0;
+ loop {
+ let is_last = read_bits(buf, &mut cursor, 1);
+ value = (value << 4) + read_bits(buf, &mut cursor, 4) as u64;
+ if is_last == 0 {
+ return (
+ Packet {
+ version,
+ type_id,
+ content: PacketContent::Literal(value),
+ },
+ cursor,
+ );
+ }
+ }
+ }
+ _ => {
+ let mut sub_packets = Vec::new();
+ let length_type_id = read_bits(buf, &mut cursor, 1);
+ match length_type_id {
+ 0 => {
+ let parse_span = read_bits(buf, &mut cursor, 15);
+ let parse_end = cursor + parse_span as usize;
+ while cursor < parse_end {
+ let (sub_packet, cursor_new) = Self::parse(buf, cursor);
+ sub_packets.push(sub_packet);
+ cursor = cursor_new;
+ }
+ }
+ 1 => {
+ let subpacket_count = read_bits(buf, &mut cursor, 11) as usize;
+ while sub_packets.len() < subpacket_count {
+ let (sub_packet, cursor_new) = Self::parse(buf, cursor);
+ sub_packets.push(sub_packet);
+ cursor = cursor_new;
+ }
+ }
+ _ => unreachable!(),
+ }
+ return (
+ Packet {
+ version,
+ type_id,
+ content: PacketContent::SubPackets(sub_packets),
+ },
+ cursor,
+ );
+ }
+ }
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .chars()
+ .map(|c| c.to_digit(16).unwrap() as u8)
+ .collect::<Vec<u8>>();
+ // 866
+ println!("Part 1: {}", part_1(&input));
+ // 1392637195518
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn calc_version_sum(packet: &Packet) -> u32 {
+ let mut version_sum = packet.version;
+ if let PacketContent::SubPackets(sub_packets) = &packet.content {
+ version_sum += sub_packets.iter().map(calc_version_sum).sum::<u32>();
+ }
+ version_sum
+}
+
+fn part_1(buf: &[u8]) -> u32 {
+ let (packet, _) = Packet::parse(buf, 0);
+ calc_version_sum(&packet)
+}
+
+fn eval_packet(packet: &Packet) -> u64 {
+ match &packet.content {
+ PacketContent::Literal(value) => *value as u64,
+ PacketContent::SubPackets(sub_packets) => match packet.type_id {
+ 0 => sub_packets.iter().map(eval_packet).sum(),
+ 1 => sub_packets.iter().map(eval_packet).product(),
+ 2 => sub_packets.iter().map(eval_packet).min().unwrap(),
+ 3 => sub_packets.iter().map(eval_packet).max().unwrap(),
+ 5 => (eval_packet(&sub_packets[0]) > eval_packet(&sub_packets[1])) as u64,
+ 6 => (eval_packet(&sub_packets[0]) < eval_packet(&sub_packets[1])) as u64,
+ 7 => (eval_packet(&sub_packets[0]) == eval_packet(&sub_packets[1])) as u64,
+ _ => unreachable!(),
+ },
+ }
+}
+
+fn part_2(buf: &[u8]) -> u64 {
+ let (packet, _) = Packet::parse(buf, 0);
+ eval_packet(&packet)
+}