commit c8bc42ff2d9e9aa8eaa1c067d1a9fbf85af1254b
parent cf1948d3dd6efeea04d89a81adb9c71cf3f76132
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 13 Apr 2023 23:38:39 -0400
Add day 16 solution
Diffstat:
6 files changed, 477 insertions(+), 1 deletion(-)
diff --git a/src/16/Cargo.toml b/src/16/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "day16"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
+num = "0.4.0"
+num-derive = "0.3.3"
+num-traits = "0.2.15"
diff --git a/src/16/input b/src/16/input
@@ -0,0 +1,2 @@
+60556F980272DCE609BC01300042622C428BC200DC128C50FCC0159E9DB9AEA86003430BE5EFA8DB0AC401A4CA4E8A3400E6CFF7518F51A554100180956198529B6A700965634F96C0B99DCF4A13DF6D200DCE801A497FF5BE5FFD6B99DE2B11250034C00F5003900B1270024009D610031400E70020C0093002980652700298051310030C00F50028802B2200809C00F999EF39C79C8800849D398CE4027CCECBDA25A00D4040198D31920C8002170DA37C660009B26EFCA204FDF10E7A85E402304E0E60066A200F4638311C440198A11B635180233023A0094C6186630C44017E500345310FF0A65B0273982C929EEC0000264180390661FC403006E2EC1D86A600F43285504CC02A9D64931293779335983D300568035200042A29C55886200FC6A8B31CE647880323E0068E6E175E9B85D72525B743005646DA57C007CE6634C354CC698689BDBF1005F7231A0FE002F91067EF2E40167B17B503E666693FD9848803106252DFAD40E63D42020041648F24460400D8ECE007CBF26F92B0949B275C9402794338B329F88DC97D608028D9982BF802327D4A9FC10B803F33BD804E7B5DDAA4356014A646D1079E8467EF702A573FAF335EB74906CF5F2ACA00B43E8A460086002A3277BA74911C9531F613009A5CCE7D8248065000402B92D47F14B97C723B953C7B22392788A7CD62C1EC00D14CC23F1D94A3D100A1C200F42A8C51A00010A847176380002110EA31C713004A366006A0200C47483109C0010F8C10AE13C9CA9BDE59080325A0068A6B4CF333949EE635B495003273F76E000BCA47E2331A9DE5D698272F722200DDE801F098EDAC7131DB58E24F5C5D300627122456E58D4C01091C7A283E00ACD34CB20426500BA7F1EBDBBD209FAC75F579ACEB3E5D8FD2DD4E300565EBEDD32AD6008CCE3A492F98E15CC013C0086A5A12E7C46761DBB8CDDBD8BE656780
+
diff --git a/src/16/part1 b/src/16/part1
@@ -0,0 +1,165 @@
+--- Day 16: Packet Decoder ---
+
+As you leave the cave and reach open waters, you receive a transmission from the Elves back on the
+ship.
+
+The transmission was sent using the Buoyancy Interchange Transmission System (BITS), a method of
+packing numeric expressions into a binary sequence. Your submarine's computer has saved the
+transmission in hexadecimal (your puzzle input).
+
+The first step of decoding the message is to convert the hexadecimal representation into binary.
+Each character of hexadecimal corresponds to four bits of binary data:
+
+0 = 0000
+1 = 0001
+2 = 0010
+3 = 0011
+4 = 0100
+5 = 0101
+6 = 0110
+7 = 0111
+8 = 1000
+9 = 1001
+A = 1010
+B = 1011
+C = 1100
+D = 1101
+E = 1110
+F = 1111
+
+The BITS transmission contains a single [1m[97mpacket[0m at its outermost layer which itself contains many
+other packets. The hexadecimal representation of this packet might encode a few extra 0 bits at the
+end; these are not part of the transmission and should be ignored.
+
+Every packet begins with a standard header: the first three bits encode the packet
+[1m[97mversion[0m, and the next three bits encode the packet [1m[97mtype ID[0m. These two values are numbers; all
+numbers encoded in any packet are represented as binary with the most significant bit first. For
+example, a version encoded as the binary sequence 100 represents the number 4.
+
+Packets with type ID 4 represent a [1m[97mliteral value[0m. Literal value packets encode a single binary
+number. To do this, the binary number is padded with leading zeroes until its length is a multiple
+of four bits, and then it is broken into groups of four bits. Each group is prefixed by a 1 bit
+except the last group, which is prefixed by a 0 bit. These groups of five bits immediately follow
+the packet header. For example, the hexadecimal string D2FE28 becomes:
+
+110100101111111000101000
+VVVTTTAAAAABBBBBCCCCC
+
+Below each bit is a label indicating its purpose:
+
+
+ - The three bits labeled V (110) are the packet version, 6.
+
+ - The three bits labeled T (100) are the packet type ID, 4, which means the packet is a literal
+value.
+
+ - The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the
+first four bits of the number, 0111.
+
+ - The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain
+four more bits of the number, 1110.
+
+ - The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last
+four bits of the number, 0101.
+
+ - The three unlabeled 0 bits at the end are extra due to the hexadecimal representation and should
+be ignored.
+
+
+So, this packet represents a literal value with binary representation 011111100101, which is 2021 in
+decimal.
+
+Every other type of packet (any packet with a type ID other than 4) represent an
+[1m[97moperator[0m that performs some calculation on one or more sub-packets contained within. Right now, the
+specific operations aren't important; focus on parsing the hierarchy of sub-packets.
+
+An operator packet contains one or more packets. To indicate which subsequent binary data represents
+its sub-packets, an operator packet can use one of two modes indicated by the bit immediately after
+the packet header; this is called the [1m[97mlength type ID[0m:
+
+
+ - If the length type ID is 0, then the next [1m[97m15[0m bits are a number that represents the [1m[97mtotal length
+in bits[0m of the sub-packets contained by this packet.
+
+ - If the length type ID is 1, then the next [1m[97m11[0m bits are a number that represents the
+[1m[97mnumber of sub-packets immediately contained[0m by this packet.
+
+
+Finally, after the length type ID bit and the 15-bit or 11-bit field, the sub-packets appear.
+
+For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0
+that contains two sub-packets:
+
+00111000000000000110111101000101001010010001001000000000
+VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB
+
+
+ - The three bits labeled V (001) are the packet version, 1.
+
+ - The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
+
+ - The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number
+representing the number of bits in the sub-packets.
+
+ - The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
+
+ - The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
+
+ - The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.
+
+
+After reading 11 and 16 bits of sub-packet data, the total length indicated in L (27) is reached,
+and so parsing of this packet stops.
+
+As another example, here is an operator packet (hexadecimal string EE00D40C823060) with length type
+ID 1 that contains three sub-packets:
+
+11101110000000001101010000001100100000100011000001100000
+VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC
+
+
+ - The three bits labeled V (111) are the packet version, 7.
+
+ - The three bits labeled T (011) are the packet type ID, 3, which means the packet is an operator.
+
+ - The bit labeled I (1) is the length type ID, which indicates that the length is a 11-bit number
+representing the number of sub-packets.
+
+ - The 11 bits labeled L (00000000011) contain the number of sub-packets, 3.
+
+ - The 11 bits labeled A contain the first sub-packet, a literal value representing the number 1.
+
+ - The 11 bits labeled B contain the second sub-packet, a literal value representing the number 2.
+
+ - The 11 bits labeled C contain the third sub-packet, a literal value representing the number 3.
+
+
+After reading 3 complete sub-packets, the number of sub-packets indicated in L (3) is reached, and
+so parsing of this packet stops.
+
+For now, parse the hierarchy of the packets throughout the transmission and [1m[97madd up all of the
+version numbers[0m.
+
+Here are a few more examples of hexadecimal-encoded transmissions:
+
+
+ - 8A004A801A8002F478 represents an operator packet (version 4) which contains an operator packet
+(version 1) which contains an operator packet (version 5) which contains a literal value (version
+6); this packet has a version sum of [1m[97m16[0m.
+
+ - 620080001611562C8802118E34 represents an operator packet (version 3) which contains two
+sub-packets; each sub-packet is an operator packet that contains two literal values. This packet has
+a version sum of [1m[97m12[0m.
+
+ - C0015000016115A2E0802F182340 has the same structure as the previous example, but the outermost
+packet uses a different length type ID. This packet has a version sum of [1m[97m23[0m.
+
+ - A0016C880162017C3686B18A3D4780 is an operator packet that contains an operator packet that
+contains an operator packet that contains five literal values; it has a version sum of
+[1m[97m31[0m.
+
+
+Decode the structure of your hexadecimal-encoded BITS transmission; [1m[97mwhat do you get if you add up
+the version numbers in all packets?[0m
+
+
diff --git a/src/16/part2 b/src/16/part2
@@ -0,0 +1,61 @@
+--- Part Two ---
+
+Now that you have the structure of your transmission decoded, you can calculate the value of the
+expression it represents.
+
+Literal values (type ID 4) represent a single number as described above. The remaining type IDs are
+more interesting:
+
+
+ - Packets with type ID 0 are [1m[97msum[0m packets - their value is the sum of the values of their
+sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.
+
+ - Packets with type ID 1 are [1m[97mproduct[0m packets - their value is the result of multiplying together
+the values of their sub-packets. If they only have a single sub-packet, their value is the value of
+the sub-packet.
+
+ - Packets with type ID 2 are [1m[97mminimum[0m packets - their value is the minimum of the values of their
+sub-packets.
+
+ - Packets with type ID 3 are [1m[97mmaximum[0m packets - their value is the maximum of the values of their
+sub-packets.
+
+ - Packets with type ID 5 are [1m[97mgreater than[0m packets - their value is [1m[97m1[0m if the value of the first
+sub-packet is greater than the value of the second sub-packet; otherwise, their value is
+[1m[97m0[0m. These packets always have exactly two sub-packets.
+
+ - Packets with type ID 6 are [1m[97mless than[0m packets - their value is [1m[97m1[0m if the value of the first
+sub-packet is less than the value of the second sub-packet; otherwise, their value is
+[1m[97m0[0m. These packets always have exactly two sub-packets.
+
+ - Packets with type ID 7 are [1m[97mequal to[0m packets - their value is [1m[97m1[0m if the value of the first
+sub-packet is equal to the value of the second sub-packet; otherwise, their value is [1m[97m0[0m. These
+packets always have exactly two sub-packets.
+
+
+Using these rules, you can now work out the value of the outermost packet in your BITS transmission.
+
+For example:
+
+
+ - C200B40A82 finds the sum of 1 and 2, resulting in the value [1m[97m3[0m.
+
+ - 04005AC33890 finds the product of 6 and 9, resulting in the value [1m[97m54[0m.
+
+ - 880086C3E88112 finds the minimum of 7, 8, and 9, resulting in the value [1m[97m7[0m.
+
+ - CE00C43D881120 finds the maximum of 7, 8, and 9, resulting in the value [1m[97m9[0m.
+
+ - D8005AC2A8F0 produces 1, because 5 is less than 15.
+
+ - F600BC2D8F produces 0, because 5 is not greater than 15.
+
+ - 9C005AC2F8F0 produces 0, because 5 is not equal to 15.
+
+ - 9C0141080250320F1802104A08 produces 1, because 1 + 3 = 2 * 2.
+
+
+[1m[97mWhat do you get if you evaluate the expression represented by your hexadecimal-encoded BITS
+transmission?[0m
+
+
diff --git a/src/16/src/main.rs b/src/16/src/main.rs
@@ -0,0 +1,238 @@
+use std::mem::ManuallyDrop;
+
+#[derive(PartialEq,Eq,Copy,Clone,num_derive::FromPrimitive)]
+enum PacketType {
+ Sum = 0,
+ Product = 1,
+ Minimum = 2,
+ Maximum = 3,
+ Literal = 4,
+ GreaterThan = 5,
+ LessThan = 6,
+ EqualTo = 7
+}
+
+#[derive(PartialEq,Eq,Clone)]
+enum PacketSizeType {
+ Count,
+ Len
+}
+
+#[derive(Clone)]
+struct LiteralPacket {
+ val: usize
+}
+
+#[derive(Clone,Copy)]
+union PacketSize {
+ cnt: usize,
+ len: usize
+}
+
+#[derive(Clone)]
+struct OperatorPacket {
+ sztype: PacketSizeType,
+ size: PacketSize,
+ sub: Vec<usize>
+}
+
+union PacketUnion {
+ lit: ManuallyDrop<LiteralPacket>,
+ op: ManuallyDrop<OperatorPacket>
+}
+
+struct Packet {
+ ver: u8,
+ typ: PacketType,
+ u: PacketUnion,
+}
+
+impl Clone for Packet {
+ fn clone(&self) -> Self {
+ let pkt_u: PacketUnion;
+ if self.typ == PacketType::Literal {
+ pkt_u = PacketUnion { lit: unsafe { self.u.lit.clone() } };
+ } else {
+ pkt_u = PacketUnion { op: unsafe { self.u.op.clone() } };
+ }
+ return Packet { ver: self.ver, typ: self.typ, u: pkt_u };
+ }
+}
+
+struct ParseState {
+ pkt: usize,
+ idx: usize,
+ start: usize
+}
+
+struct EvalState {
+ pkt: usize,
+ ins: Vec<usize>
+}
+
+fn bitstr(hexstr: &str) -> String {
+ let conv = |i| u8::from_str_radix(&hexstr[i..i+2], 16).unwrap();
+ let bytes: Vec<u8> = (0..hexstr.len()).step_by(2).map(conv).collect();
+ bytes.iter().map(|b| format!("{b:08b}")).collect::<Vec<String>>().join("")
+}
+
+fn decode_packet(bitstr: &str) -> (Packet, usize) {
+ aoc::debugln!("{}", bitstr);
+ let pver = u8::from_str_radix(&bitstr[0..3], 2).unwrap();
+ let ptype_val = u8::from_str_radix(&bitstr[3..6], 2).unwrap();
+ let pu: PacketUnion;
+ let mut cnt: usize = 0;
+ let ptype: PacketType = num::FromPrimitive::from_u8(ptype_val).unwrap();
+ if ptype == PacketType::Literal {
+ let mut imm: usize = 0;
+ for i in (6..bitstr.len()).step_by(5) {
+ imm = (imm << 4) | usize::from_str_radix(&bitstr[i+1..i+5], 2).unwrap();
+ if bitstr[i..].chars().next().unwrap() == '0' {
+ cnt = i + 5;
+ break;
+ }
+ }
+ let lit = ManuallyDrop::new(LiteralPacket { val: imm });
+ pu = PacketUnion { lit };
+ } else {
+ let szbit = bitstr[6..].chars().next().unwrap();
+ let sztype: PacketSizeType;
+ let size: PacketSize;
+ if szbit == '1' {
+ sztype = PacketSizeType::Count;
+ let imm = usize::from_str_radix(&bitstr[7..7+11], 2).unwrap();
+ size = PacketSize { cnt: imm };
+ cnt = 18;
+ } else {
+ sztype = PacketSizeType::Len;
+ let imm = usize::from_str_radix(&bitstr[7..7+15], 2).unwrap();
+ size = PacketSize { len: imm };
+ cnt = 22;
+ }
+ let op = ManuallyDrop::new(OperatorPacket { sztype, size, sub: Vec::new() });
+ pu = PacketUnion { op };
+ }
+ return (Packet { ver: pver, typ: ptype, u: pu }, cnt);
+}
+
+fn decode_packets(input: &str) -> Vec<Packet> {
+ let mut packets: Vec<Packet> = Vec::new();
+ let mut stack: Vec<ParseState> = Vec::new();
+
+ let bits = bitstr(input.lines().next().unwrap());
+ let mut pos: usize = 0;
+ while !stack.is_empty() || pos + 8 <= bits.len() {
+ if !stack.is_empty() {
+ let state = stack.last_mut().unwrap();
+ let op = unsafe { &*packets.get_mut(state.pkt).unwrap().u.op };
+ let done = op.sztype == PacketSizeType::Count
+ && state.idx >= unsafe { op.size.cnt }
+ || op.sztype == PacketSizeType::Len
+ && pos - state.start >= unsafe { op.size.len };
+ if done {
+ assert!(op.sztype == PacketSizeType::Count
+ && state.idx == unsafe { op.size.cnt }
+ || op.sztype == PacketSizeType::Len
+ && pos - state.start == unsafe { op.size.len });
+ stack.pop();
+ continue;
+ }
+ }
+
+ let pkt_idx: usize;
+ let (m_pkt, skip) = decode_packet(&bits[pos..]);
+ packets.push(m_pkt);
+ pkt_idx = packets.len() - 1;
+
+ let ptype = packets.last().unwrap().typ;
+ let pver = packets.last().unwrap().ver;
+ aoc::debugln!("PKT {} {}", ptype as u8, pver);
+
+ if !stack.is_empty() {
+ let mut state = stack.last_mut().unwrap();
+ /* we are not necessarily done with the packet at this point
+ * (for example if this is an OperatorPacket) but will be as
+ * soon as this state is at the top of the stack again */
+ state.idx += 1;
+ let pkt = packets.get_mut(state.pkt).unwrap();
+ assert!(pkt.typ != PacketType::Literal);
+ let op = unsafe { &mut pkt.u.op };
+ op.sub.push(pkt_idx);
+ }
+
+ if ptype != PacketType::Literal {
+ stack.push(ParseState { pkt: pkt_idx, idx: 0, start: pos + skip });
+ }
+
+ pos += skip;
+ }
+
+ aoc::debugln!("REST: {}", &bits[pos..]);
+
+ return packets;
+}
+
+fn eval_packet(ptype: PacketType, ins: &Vec<usize>) -> usize {
+ match ptype {
+ PacketType::Literal => ins[0],
+ PacketType::Sum => ins.iter().sum(),
+ PacketType::Product => ins.iter().fold(1, |a, b| a * b),
+ PacketType::Minimum => *ins.iter().min().unwrap(),
+ PacketType::Maximum => *ins.iter().max().unwrap(),
+ PacketType::LessThan => if ins[0] < ins[1] { 1 } else { 0 },
+ PacketType::GreaterThan => if ins[0] > ins[1] { 1 } else { 0 },
+ PacketType::EqualTo => if ins[0] == ins[1] { 1 } else { 0 },
+ }
+}
+
+fn eval_packets(packets: &Vec<Packet>) -> usize {
+ let mut stack: Vec<EvalState> = Vec::new();
+ stack.push(EvalState { pkt: 0, ins: Vec::new() });
+ while !stack.is_empty() {
+ let top = stack.last().unwrap();
+ let pkt = packets.get(top.pkt).unwrap();
+ aoc::debugln!("packet {}", pkt.typ as u8);
+ if pkt.typ == PacketType::Literal {
+ stack.pop();
+ assert!(!stack.is_empty());
+ let top = stack.last_mut().unwrap();
+ top.ins.push(unsafe { pkt.u.lit.val });
+ } else {
+ let op = unsafe { &pkt.u.op };
+ let len = op.sub.len();
+ let idx = top.ins.len();
+ aoc::debugln!("=> op {} {}", idx, len);
+ assert!(len != 0);
+ if idx < len {
+ let child = *op.sub.get(idx).unwrap();
+ stack.push(EvalState { pkt: child, ins: Vec::new() });
+ } else {
+ let res = eval_packet(pkt.typ, &top.ins);
+ stack.pop();
+ if stack.is_empty() { return res; }
+ let top = stack.last_mut().unwrap();
+ top.ins.push(res);
+ }
+ }
+ }
+ return 0;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let packets = decode_packets(&aoc.input);
+ let answer = packets.iter().map(|p| p.ver as usize).sum::<usize>();
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("871");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let packets = decode_packets(&aoc.input);
+ let answer = eval_packets(&packets);
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("68703010504");
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/Makefile b/src/Makefile
@@ -21,7 +21,7 @@ $1/run1: $1/main
$1/run2: $1/main
@cd $1 && time ./main 2
-$1/run:
+$1/run: $1/main
@echo "== day $1 =="
@echo -en "\npart 1: " && cd $1 && time ./main 1
@echo -en "\npart 2: " && cd $1 && time ./main 2
