Day 16

3 files changed, 221 insertions, 1 deletions

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<dyn std::error::Error>> {
     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<dyn std::error::Error>> {
+    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<Packet>,
+}
+
+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<u8> for OperatorType {
+    type Error = OperatorError;
+    fn try_from(num: u8) -> Result<Self, OperatorError> {
+        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<Packet>> {
+    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<Packet>> {
+    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))
+}