From 1d780f776c1fd43604dac79691b6753fb69f2359 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Thu, 16 Dec 2021 21:36:40 +0200 Subject: Day 16 --- inputs/day_16.txt | 1 + src/bin/day_14.rs | 4 +- src/bin/day_16.rs | 217 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 221 insertions(+), 1 deletion(-) create mode 100644 inputs/day_16.txt create mode 100644 src/bin/day_16.rs diff --git a/inputs/day_16.txt b/inputs/day_16.txt new file mode 100644 index 0000000..57468d0 --- /dev/null +++ b/inputs/day_16.txt @@ -0,0 +1 @@ +A20D5CECBD6C061006E7801224AF251AEA06D2319904921880113A931A1402A9D83D43C9FFCC1E56FF29890E00C42984337BF22C502008C26982801009426937320124E602BC01192F4A74FD7B70692F4A74FD7B700403170400F7002DC00E7003C400B0023700082C601DF8C00D30038005AA0013F40044E7002D400D10030C008000574000AB958B4B8011074C0249769913893469A72200B42673F26A005567FCC13FE673004F003341006615421830200F4608E7142629294F92861A840118F1184C0129637C007C24B19AA2C96335400013B0C0198F716213180370AE39C7620043E0D4788B440232CB34D80260008645C86D16C401B85D0BA2D18025A00ACE7F275324137FD73428200ECDFBEFF2BDCDA70D5FE5339D95B3B6C98C1DA006772F9DC9025B057331BF7D8B65108018092599C669B4B201356763475D00480010E89709E090002130CA28C62300265C188034BA007CA58EA6FB4CDA12799FD8098021400F94A6F95E3ECC73A77359A4EFCB09CEF799A35280433D1BCCA666D5EFD6A5A389542A7DCCC010958D85EC0119EED04A73F69703669466A048C01E14FFEFD229ADD052466ED37BD8B4E1D10074B3FF8CF2BBE0094D56D7E38CADA0FA80123C8F75F9C764D29DA814E4693C4854C0118AD3C0A60144E364D944D02C99F4F82100607600AC8F6365C91EC6CBB3A072C404011CE8025221D2A0337158200C97001F6978A1CE4FFBE7C4A5050402E9ECEE709D3FE7296A894F4C6A75467EB8959F4C013815C00FACEF38A7297F42AD2600B7006A0200EC538D51500010B88919624CE694C0027B91951125AFF7B9B1682040253D006E8000844138F105C0010D84D1D2304B213007213900D95B73FE914CC9FCBFA9EEA81802FA0094A34CA3649F019800B48890C2382002E727DF7293C1B900A160008642B87312C0010F8DB08610080331720FC580 diff --git a/src/bin/day_14.rs b/src/bin/day_14.rs index c534b8c..4814855 100644 --- a/src/bin/day_14.rs +++ b/src/bin/day_14.rs @@ -13,10 +13,12 @@ fn main() -> Result<(), Box> { let mut polymer = parse_polymer_expansion(&input).unwrap().1; for _ in 0..10 { polymer.expand(); + dbg!(&polymer.element_counts); } dbg!(polymer.most_common_element_count() - polymer.least_common_element_count()); - for _ in 0..30 { + for _ in 10..40 { polymer.expand(); + dbg!(&polymer.element_counts); } dbg!(polymer.most_common_element_count() - polymer.least_common_element_count()); diff --git a/src/bin/day_16.rs b/src/bin/day_16.rs new file mode 100644 index 0000000..368ecc8 --- /dev/null +++ b/src/bin/day_16.rs @@ -0,0 +1,217 @@ +use nom::{ + branch::alt, + bytes::complete::take, + character::complete::{char as nom_char, one_of}, + combinator::{consumed, map, map_res}, + error::FromExternalError, + multi::many0, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_16.txt")?; + let binary = convert_to_binary(&input).unwrap().1; + let packet = parse_packet(&binary).unwrap().1; + dbg!(packet.version_sum()); + dbg!(packet.eval()); + + Ok(()) +} + +#[derive(Debug)] +struct Packet { + version: u8, + data: PacketData, +} + +impl Packet { + fn version_sum(&self) -> u32 { + self.version as u32 + + match &self.data { + PacketData::Literal(_) => 0, + PacketData::Operator(data) => { + data.sub_packets.iter().map(|p| p.version_sum()).sum() + } + } + } + + fn eval(&self) -> u64 { + match &self.data { + PacketData::Literal(val) => *val, + PacketData::Operator(data) => data.eval(), + } + } +} + +#[derive(Debug)] +enum PacketData { + Literal(u64), + Operator(OperatorData), +} + +#[derive(Debug)] +struct OperatorData { + type_id: OperatorType, + sub_packets: Vec, +} + +impl OperatorData { + fn eval(&self) -> u64 { + match &self.type_id { + OperatorType::Sum => self.sub_packets.iter().map(|p| p.eval()).sum(), + OperatorType::Product => self.sub_packets.iter().map(|p| p.eval()).product(), + OperatorType::Minimum => self.sub_packets.iter().map(|p| p.eval()).min().unwrap_or(0), + OperatorType::Maximum => self.sub_packets.iter().map(|p| p.eval()).max().unwrap_or(0), + OperatorType::GreaterThan => { + if self.sub_packets[0].eval() > self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + OperatorType::LessThan => { + if self.sub_packets[0].eval() < self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + OperatorType::EqualTo => { + if self.sub_packets[0].eval() == self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + } + } +} + +#[derive(Debug)] +enum OperatorType { + Sum, + Product, + Minimum, + Maximum, + GreaterThan, + LessThan, + EqualTo, +} + +#[derive(Debug, thiserror::Error)] +enum OperatorError { + #[error("type was not a valid operator")] + InvalidType, +} + +impl TryFrom for OperatorType { + type Error = OperatorError; + fn try_from(num: u8) -> Result { + match num { + 0 => Ok(Self::Sum), + 1 => Ok(Self::Product), + 2 => Ok(Self::Minimum), + 3 => Ok(Self::Maximum), + 5 => Ok(Self::GreaterThan), + 6 => Ok(Self::LessThan), + 7 => Ok(Self::EqualTo), + _ => Err(OperatorError::InvalidType), + } + } +} + +fn convert_to_binary(input: &str) -> IResult<&str, String> { + map( + many0(map(one_of("0123456789ABCDEF"), |hex_char| { + let digit = hex_char.to_digit(16).unwrap(); + format!("{:04b}", digit) + })), + |bin_strings| bin_strings.join(""), + )(input) +} + +fn parse_packet(input: &str) -> IResult<&str, Packet> { + let (input, version) = parse_bits3(input)?; + let (input, type_id) = parse_bits3(input)?; + if type_id == 4 { + let (input, literal) = parse_literal(input)?; + Ok(( + input, + Packet { + version, + data: PacketData::Literal(literal), + }, + )) + } else { + let (input, sub_packets) = + alt((parse_sub_packets_bits_mode, parse_sub_packets_count_mode))(input)?; + Ok(( + input, + Packet { + version, + data: PacketData::Operator(OperatorData { + type_id: type_id.try_into().expect("Invalid operator"), + sub_packets, + }), + }, + )) + } +} + +fn parse_bits3(input: &str) -> IResult<&str, u8> { + map_res(take(3usize), |bin_str| u8::from_str_radix(bin_str, 2))(input) +} + +fn parse_literal(input: &str) -> IResult<&str, u64> { + let (input, mut chunks) = many0(parse_literal_continuing_chunk)(input)?; + let (input, last_chunk) = parse_literal_last_chunk(input)?; + chunks.push(last_chunk); + let binary_num = chunks.join(""); + let num = u64::from_str_radix(&binary_num, 2).map_err(|e| { + nom::Err::Error(nom::error::Error::from_external_error( + input, + nom::error::ErrorKind::MapRes, + e, + )) + })?; + Ok((input, num)) +} + +fn parse_literal_continuing_chunk(input: &str) -> IResult<&str, &str> { + let (input, _) = nom_char('1')(input)?; + take(4usize)(input) +} + +fn parse_literal_last_chunk(input: &str) -> IResult<&str, &str> { + let (input, _) = nom_char('0')(input)?; + take(4usize)(input) +} + +fn parse_sub_packets_bits_mode(input: &str) -> IResult<&str, Vec> { + let (input, _) = nom_char('0')(input)?; + let (mut input, length_in_bits) = + map_res(take(15usize), |bin_str| usize::from_str_radix(bin_str, 2))(input)?; + let mut consumed_by_subpackets = String::new(); + let mut sub_packets = Vec::new(); + while consumed_by_subpackets.len() < length_in_bits { + let (next_input, (next_consumed, next_packet)) = consumed(parse_packet)(input)?; + input = next_input; + consumed_by_subpackets += next_consumed; + sub_packets.push(next_packet); + } + Ok((input, sub_packets)) +} + +fn parse_sub_packets_count_mode(input: &str) -> IResult<&str, Vec> { + let (input, _) = nom_char('1')(input)?; + let (mut input, number_of_packets) = + map_res(take(11usize), |bin_str| u16::from_str_radix(bin_str, 2))(input)?; + let mut sub_packets = Vec::new(); + for _ in 0..number_of_packets { + let (next_input, next_packet) = parse_packet(input)?; + input = next_input; + sub_packets.push(next_packet); + } + Ok((input, sub_packets)) +} -- cgit v1.2.3