main.rs (4377B)
1 #[derive(Debug, Clone)]
2 enum PacketContent {
3 Literal(u64),
4 SubPackets(Vec<Packet>),
5 }
6
7 #[derive(Debug, Clone)]
8 struct Packet {
9 version: u32,
10 type_id: u32,
11 content: PacketContent,
12 }
13
14 fn read_bits(buf: &[u8], cursor: &mut usize, span: usize) -> u32 {
15 let mut value: u32 = 0;
16 for _ in 0..span {
17 let buf_idx = *cursor / 4;
18 let offset = 3 - *cursor % 4;
19 value <<= 1;
20 value += (buf[buf_idx] & (1 << offset)) as u32 >> offset;
21 *cursor += 1;
22 }
23 value
24 }
25
26 impl Packet {
27 fn parse(buf: &[u8], start: usize) -> (Packet, usize) {
28 let mut cursor = start;
29 let version = read_bits(buf, &mut cursor, 3);
30 let type_id = read_bits(buf, &mut cursor, 3);
31 match type_id {
32 4 => {
33 let mut value = 0;
34 loop {
35 let is_last = read_bits(buf, &mut cursor, 1);
36 value = (value << 4) + read_bits(buf, &mut cursor, 4) as u64;
37 if is_last == 0 {
38 return (
39 Packet {
40 version,
41 type_id,
42 content: PacketContent::Literal(value),
43 },
44 cursor,
45 );
46 }
47 }
48 }
49 _ => {
50 let mut sub_packets = Vec::new();
51 let length_type_id = read_bits(buf, &mut cursor, 1);
52 match length_type_id {
53 0 => {
54 let parse_span = read_bits(buf, &mut cursor, 15);
55 let parse_end = cursor + parse_span as usize;
56 while cursor < parse_end {
57 let (sub_packet, cursor_new) = Self::parse(buf, cursor);
58 sub_packets.push(sub_packet);
59 cursor = cursor_new;
60 }
61 }
62 1 => {
63 let subpacket_count = read_bits(buf, &mut cursor, 11) as usize;
64 while sub_packets.len() < subpacket_count {
65 let (sub_packet, cursor_new) = Self::parse(buf, cursor);
66 sub_packets.push(sub_packet);
67 cursor = cursor_new;
68 }
69 }
70 _ => unreachable!(),
71 }
72 return (
73 Packet {
74 version,
75 type_id,
76 content: PacketContent::SubPackets(sub_packets),
77 },
78 cursor,
79 );
80 }
81 }
82 }
83 }
84
85 fn main() {
86 let input = std::fs::read_to_string("input.txt")
87 .unwrap()
88 .trim()
89 .chars()
90 .map(|c| c.to_digit(16).unwrap() as u8)
91 .collect::<Vec<u8>>();
92 // 866
93 println!("Part 1: {}", part_1(&input));
94 // 1392637195518
95 println!("Part 2: {}", part_2(&input));
96 }
97
98 fn calc_version_sum(packet: &Packet) -> u32 {
99 let mut version_sum = packet.version;
100 if let PacketContent::SubPackets(sub_packets) = &packet.content {
101 version_sum += sub_packets.iter().map(calc_version_sum).sum::<u32>();
102 }
103 version_sum
104 }
105
106 fn part_1(buf: &[u8]) -> u32 {
107 let (packet, _) = Packet::parse(buf, 0);
108 calc_version_sum(&packet)
109 }
110
111 fn eval_packet(packet: &Packet) -> u64 {
112 match &packet.content {
113 PacketContent::Literal(value) => *value as u64,
114 PacketContent::SubPackets(sub_packets) => match packet.type_id {
115 0 => sub_packets.iter().map(eval_packet).sum(),
116 1 => sub_packets.iter().map(eval_packet).product(),
117 2 => sub_packets.iter().map(eval_packet).min().unwrap(),
118 3 => sub_packets.iter().map(eval_packet).max().unwrap(),
119 5 => (eval_packet(&sub_packets[0]) > eval_packet(&sub_packets[1])) as u64,
120 6 => (eval_packet(&sub_packets[0]) < eval_packet(&sub_packets[1])) as u64,
121 7 => (eval_packet(&sub_packets[0]) == eval_packet(&sub_packets[1])) as u64,
122 _ => unreachable!(),
123 },
124 }
125 }
126
127 fn part_2(buf: &[u8]) -> u64 {
128 let (packet, _) = Packet::parse(buf, 0);
129 eval_packet(&packet)
130 }