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)); } }