From e7249a6e7d90c4c1fef7e998302304c4283a45b6 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Fri, 17 Dec 2021 13:41:24 +0000 Subject: Day 16 --- day16/src/main.rs | 239 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 239 insertions(+) create mode 100644 day16/src/main.rs (limited to 'day16/src') diff --git a/day16/src/main.rs b/day16/src/main.rs new file mode 100644 index 0000000..9f8352c --- /dev/null +++ b/day16/src/main.rs @@ -0,0 +1,239 @@ +use std::fs; +use std::path::Path; + +#[derive(Debug)] +struct BITS { + version: u8, + body: Box +} + +#[derive(Debug)] +enum BITSPacket { + Literal(u64), + Operator(u8, Vec>) +} + +/* AOC21 Day 16: https://adventofcode.com/2021/day/16 */ +fn main() { + let input = Path::new("resources").join("input.txt"); + let content = fs::read_to_string(input).expect("Unable to read input file"); + let bits = to_bits(&content); + let (packet,_) = parse_packet(&bits); + println!("Ex1: the result is {}", sum_versions(&packet)); + println!("Ex2: the result is {}", evaluate(&packet)); +} + +fn to_bits(input: &str) -> Vec { + input.chars().fold(vec![], |mut bits,c| { + let c = c.to_digit(16).expect("Malformed input"); + for i in 0..4 { bits.push(((c>>(3-i))&1) as u8) } + bits + }) +} + +fn decimal(bits: &[u8]) -> u64 { + // NOTE: using `acc<<1` will potentially overflow *silently*. Use `2*acc` instead. + bits.iter().fold(0, |acc,&b| 2*acc + b as u64) +} + + +fn parse_packets_by_length(bits: &[u8], len: usize) -> Vec> { + let mut vec = vec![]; + let mut cur = 0; + while cur < len { + let (pkg,size) = parse_packet(&bits[cur..]); + vec.push(Box::new(pkg)); + cur += size; + } + vec +} + +fn parse_packets_by_number(bits: &[u8], num: usize) -> (Vec>, usize) { + let mut vec = vec![]; + let mut cur = 0; + for _ in 0..num { + let (pkg,size) = parse_packet(&bits[cur..]); + vec.push(Box::new(pkg)); + cur += size; + } + (vec,cur) +} + +fn parse_packet(bits: &[u8]) -> (BITS, usize) { + let version = decimal(&bits[..3]) as u8; + let typeid = decimal(&bits[3..6]) as u8; + match typeid { + 4 => { + let blocks = (0..).find(|b| bits[6+5*b] == 0).unwrap(); + let lit = (0..=blocks).fold(0, |acc,blk| 16*acc + decimal(&bits[6+5*blk+1..6+5*(blk+1)])); + let body = Box::new(BITSPacket::Literal(lit)); + (BITS { version, body }, 6+5*(blocks+1)) + }, + _ if bits[6] == 0 => { + let len = decimal(&bits[7..22]) as usize; + let subpkgs = parse_packets_by_length(&bits[22..], len); + let body = Box::new(BITSPacket::Operator(typeid, subpkgs)); + (BITS { version, body }, 7+15+len) + }, + _ => { + let num = decimal(&bits[7..18]) as usize; + let (subpkgs,len) = parse_packets_by_number(&bits[18..], num); + let body = Box::new(BITSPacket::Operator(typeid, subpkgs)); + (BITS { version, body }, 7+11+len) + } + } +} + +fn sum_versions(packet: &BITS) -> u32 { + packet.version as u32 + match packet.body.as_ref() { + BITSPacket::Literal(_) => 0, + BITSPacket::Operator(_,packets) => packets.iter().map(|p| sum_versions(p)).sum() + } +} + +fn evaluate(packet: &BITS) -> u64 { + match packet.body.as_ref() { + BITSPacket::Literal(l) => *l, + BITSPacket::Operator(t,ps) => { + let evals: Vec = ps.iter().map(|p| evaluate(p)).collect(); + match t { + 0 => evals.iter().sum(), + 1 => evals.iter().product(), + 2 => *evals.iter().min().unwrap(), + 3 => *evals.iter().max().unwrap(), + 5 => (evals[0] > evals[1]) as u64, + 6 => (evals[0] < evals[1]) as u64, + 7 => (evals[0] == evals[1]) as u64, + _ => unreachable!() + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn literal() { + let input = "D2FE28"; + let bits = to_bits(input); + let (packet,size) = parse_packet(&bits); + assert_eq!(21, size); + assert_eq!(6, packet.version); + matches!(*packet.body, BITSPacket::Literal(2021)); + } + + #[test] + fn bit_literal() { + let input = "3232D42BF9400"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(5000000000, evaluate(&packet)); + } + + #[test] + fn operator_t0() { + let input = "38006F45291200"; + let bits = to_bits(input); + let (packet,size) = parse_packet(&bits); + assert_eq!(49, size); + assert_eq!(1, packet.version); + matches!(*packet.body, BITSPacket::Operator(6,_)); + if let BITSPacket::Operator(_,packets) = *packet.body { + assert_eq!(2, packets.len()); + let packet = packets[0].as_ref(); + assert_eq!(6, packet.version); + matches!(*packet.body, BITSPacket::Literal(10)); + let packet = packets[1].as_ref(); + assert_eq!(2, packet.version); + matches!(*packet.body, BITSPacket::Literal(20)); + } + } + + #[test] + fn operator_t1() { + let input = "EE00D40C823060"; + let bits = to_bits(input); + let (packet,size) = parse_packet(&bits); + assert_eq!(51, size); + assert_eq!(7, packet.version); + matches!(*packet.body, BITSPacket::Operator(3,_)); + if let BITSPacket::Operator(_,packets) = *packet.body { + assert_eq!(3, packets.len()); + let packet = packets[0].as_ref(); + assert_eq!(2, packet.version); + matches!(*packet.body, BITSPacket::Literal(1)); + let packet = packets[1].as_ref(); + assert_eq!(4, packet.version); + matches!(*packet.body, BITSPacket::Literal(2)); + let packet = packets[2].as_ref(); + assert_eq!(1, packet.version); + matches!(*packet.body, BITSPacket::Literal(3)); + } + } + + #[test] + fn sum() { + let input = "C200B40A82"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(3, evaluate(&packet)); + } + + #[test] + fn product() { + let input = "04005AC33890"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(54, evaluate(&packet)); + } + + #[test] + fn min() { + let input = "880086C3E88112"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(7, evaluate(&packet)); + } + + #[test] + fn max() { + let input = "CE00C43D881120"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(9, evaluate(&packet)); + } + + #[test] + fn less_then() { + let input = "D8005AC2A8F0"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(1, evaluate(&packet)); + } + + #[test] + fn greater_then() { + let input = "F600BC2D8F"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(0, evaluate(&packet)); + } + + #[test] + fn equals1() { + let input = "9C005AC2F8F0"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(0, evaluate(&packet)); + } + + #[test] + fn equals2() { + let input = "9C0141080250320F1802104A08"; + let bits = to_bits(input); + let (packet,_) = parse_packet(&bits); + assert_eq!(1, evaluate(&packet)); + } +} -- cgit v1.2.3