diff options
| -rw-r--r-- | data/2021/16.txt | 1 | ||||
| -rw-r--r-- | src/2021/16/mod.rs | 215 | ||||
| -rw-r--r-- | src/2021/mod.rs | 4 |
3 files changed, 220 insertions, 0 deletions
diff --git a/data/2021/16.txt b/data/2021/16.txt new file mode 100644 index 0000000..be656f0 --- /dev/null +++ b/data/2021/16.txt @@ -0,0 +1 @@ +E20D7880532D4E551A5791BD7B8C964C1548CB3EC1FCA41CC00C6D50024400C202A65C00C20257C008AF70024C00810039C00C3002D400A300258040F200D6040093002CC0084003FA52DB8134DE620EC01DECC4C8A5B55E204B6610189F87BDD3B30052C01493E2DC9F1724B3C1F8DC801E249E8D66C564715589BCCF08B23CA1A00039D35FD6AC5727801500260B8801F253D467BFF99C40182004223B4458D2600E42C82D07CC01D83F0521C180273D5C8EE802B29F7C9DA1DCACD1D802469FF57558D6A65372113005E4DB25CF8C0209B329D0D996C92605009A637D299AEF06622CE4F1D7560141A52BC6D91C73CD732153BF862F39BA49E6BA8C438C010E009AA6B75EF7EE53BBAC244933A48600B025AD7C074FEB901599A49808008398142013426BD06FA00D540010C87F0CA29880370E21D42294A6E3BCF0A080324A006824E3FCBE4A782E7F356A5006A587A56D3699CF2F4FD6DF60862600BF802F25B4E96BDD26049802333EB7DDB401795FC36BD26A860094E176006A0200FC4B8790B4001098A50A61748D2DEDDF4C6200F4B6FE1F1665BED44015ACC055802B23BD87C8EF61E600B4D6BAD5800AA4E5C8672E4E401D0CC89F802D298F6A317894C7B518BE4772013C2803710004261EC318B800084C7288509E56FD6430052482340128FB37286F9194EE3D31FA43BACAF2802B12A7B83E4017E4E755E801A2942A9FCE757093005A6D1F803561007A17C3B8EE0008442085D1E8C0109E3BC00CDE4BFED737A90DC97FDAE6F521B97B4619BE17CC01D94489E1C9623000F924A7C8C77EA61E6679F7398159DE7D84C015A0040670765D5A52D060200C92801CA8A531194E98DA3CCF8C8C017C00416703665A2141008CF34EF8019A080390962841C1007217C5587E60164F81C9A5CE0E4AA549223002E32BDCEA36B2E100A160008747D8B705C001098DB13A388803F1AE304600 diff --git a/src/2021/16/mod.rs b/src/2021/16/mod.rs new file mode 100644 index 0000000..7dd4837 --- /dev/null +++ b/src/2021/16/mod.rs @@ -0,0 +1,215 @@ +struct BitIter { + byte: u8, + pos: u8, +} + +impl BitIter { + fn new(byte: u8) -> Self { + Self { byte, pos: 0 } + } +} + +impl Iterator for BitIter { + type Item = bool; + + fn next(&mut self) -> Option<Self::Item> { + if self.pos >= 8 { + return None; + } + + let ret = self.byte.leading_ones() > 0; + self.byte <<= 1; + self.pos += 1; + Some(ret) + } +} + +fn bits(bytes: impl Iterator<Item = u8>) -> impl Iterator<Item = bool> { + bytes.flat_map(BitIter::new) +} + +struct LiteralU8(u8); + +impl FromIterator<bool> for LiteralU8 { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = bool>, + { + let mut ret = 0; + for b in iter { + ret = (ret << 1) | if b { 1 } else { 0 }; + } + Self(ret) + } +} + +struct LiteralU16(u16); + +impl FromIterator<bool> for LiteralU16 { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = bool>, + { + let mut ret = 0; + for b in iter { + ret = (ret << 1) | if b { 1 } else { 0 }; + } + Self(ret) + } +} + +struct Packet { + version: u8, + id: u8, + contents: PacketContents, +} + +enum PacketContents { + Literal { value: u64 }, + Operator { packets: Vec<Packet> }, +} + +impl Packet { + fn parse(bits: &mut impl Iterator<Item = bool>) -> (Self, usize) { + let LiteralU8(version) = bits.take(3).collect(); + let LiteralU8(id) = bits.take(3).collect(); + let mut nbits = 6; + let contents = if id == 4 { + let (value, size) = read_varnum(bits.by_ref()); + nbits += size; + PacketContents::Literal { value } + } else { + let mut packets = vec![]; + nbits += 1; + if bits.next().unwrap() { + let LiteralU16(subpacket_count) = bits.take(11).collect(); + nbits += 11; + for i in 0..subpacket_count { + let (packet, size) = Self::parse(bits); + packets.push(packet); + nbits += size; + } + } else { + let LiteralU16(remaining_bits) = bits.take(15).collect(); + nbits += 15; + let mut remaining_bits = usize::from(remaining_bits); + while remaining_bits > 0 { + let (packet, size) = Self::parse(bits); + packets.push(packet); + nbits += size; + remaining_bits -= size; + } + } + PacketContents::Operator { packets } + }; + ( + Self { + version, + id, + contents, + }, + nbits, + ) + } + + fn subpackets(&self) -> impl Iterator<Item = &Self> { + let mut to_return = std::collections::VecDeque::new(); + to_return.push_back(self); + Subpackets { to_return } + } + + fn eval(&self) -> i64 { + match &self.contents { + PacketContents::Literal { value } => (*value).try_into().unwrap(), + PacketContents::Operator { packets } => match self.id { + 0 => packets.iter().map(|packet| packet.eval()).sum(), + 1 => packets.iter().map(|packet| packet.eval()).product(), + 2 => { + packets.iter().map(|packet| packet.eval()).min().unwrap() + } + 3 => { + packets.iter().map(|packet| packet.eval()).max().unwrap() + } + 4 => unreachable!(), + 5 => { + if packets[0].eval() > packets[1].eval() { + 1 + } else { + 0 + } + } + 6 => { + if packets[0].eval() < packets[1].eval() { + 1 + } else { + 0 + } + } + 7 => { + if packets[0].eval() == packets[1].eval() { + 1 + } else { + 0 + } + } + _ => unreachable!(), + }, + } + } +} + +fn read_varnum(bits: &mut impl Iterator<Item = bool>) -> (u64, usize) { + let mut ret = 0; + let mut nbits = 0; + while bits.next().unwrap() { + let LiteralU8(chunk) = bits.take(4).collect(); + ret = (ret << 4) | u64::from(chunk); + nbits += 5; + } + let LiteralU8(chunk) = bits.take(4).collect(); + ret = (ret << 4) | u64::from(chunk); + nbits += 5; + (ret, nbits) +} + +struct Subpackets<'a> { + to_return: std::collections::VecDeque<&'a Packet>, +} + +impl<'a> Iterator for Subpackets<'a> { + type Item = &'a Packet; + + fn next(&mut self) -> Option<Self::Item> { + let next = self.to_return.pop_front(); + if let Some(next) = next { + match &next.contents { + PacketContents::Literal { .. } => {} + PacketContents::Operator { packets } => { + self.to_return.extend(packets.iter()); + } + } + } + next + } +} + +pub fn part1() -> anyhow::Result<i64> { + let line = data_lines!()?.next().unwrap()?; + let mut bits = bits(line.as_bytes().chunks(2).map(|bs| { + u8::from_str_radix(std::str::from_utf8(bs).unwrap(), 16).unwrap() + })); + let (packet, _) = Packet::parse(bits.by_ref()); + Ok(packet + .subpackets() + .map(|packet| i64::from(packet.version)) + .sum()) +} + +pub fn part2() -> anyhow::Result<i64> { + let line = data_lines!()?.next().unwrap()?; + let mut bits = bits(line.as_bytes().chunks(2).map(|bs| { + u8::from_str_radix(std::str::from_utf8(bs).unwrap(), 16).unwrap() + })); + let (packet, _) = Packet::parse(bits.by_ref()); + Ok(packet.eval()) +} diff --git a/src/2021/mod.rs b/src/2021/mod.rs index 73379e7..e11a0ee 100644 --- a/src/2021/mod.rs +++ b/src/2021/mod.rs @@ -28,6 +28,8 @@ mod day13; mod day14; #[path = "15/mod.rs"] mod day15; +#[path = "16/mod.rs"] +mod day16; // NEXT MOD pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> { @@ -62,6 +64,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> { (14, 2) => day14::part2(), (15, 1) => day15::part1(), (15, 2) => day15::part2(), + (16, 1) => day16::part1(), + (16, 2) => day16::part2(), // NEXT PART _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } |