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/Cargo.toml | 9 ++ day16/resources/input.txt | 1 + day16/src/main.rs | 239 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 249 insertions(+) create mode 100644 day16/Cargo.toml create mode 100644 day16/resources/input.txt create mode 100644 day16/src/main.rs diff --git a/day16/Cargo.toml b/day16/Cargo.toml new file mode 100644 index 0000000..da61ec5 --- /dev/null +++ b/day16/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "day16" +version = "0.1.0" +authors = ["Federico Igne "] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/day16/resources/input.txt b/day16/resources/input.txt new file mode 100644 index 0000000..bcdd198 --- /dev/null +++ b/day16/resources/input.txt @@ -0,0 +1 @@ +4054460802532B12FEE8B180213B19FA5AA77601C010E4EC2571A9EDFE356C7008E7B141898C1F4E50DA7438C011D005E4F6E727B738FC40180CB3ED802323A8C3FED8C4E8844297D88C578C26008E004373BCA6B1C1C99945423798025800D0CFF7DC199C9094E35980253FB50A00D4C401B87104A0C8002171CE31C41201062C01393AE2F5BCF7B6E969F3C553F2F0A10091F2D719C00CD0401A8FB1C6340803308A0947B30056803361006615C468E4200E47E8411D26697FC3F91740094E164DFA0453F46899015002A6E39F3B9802B800D04A24CC763EDBB4AFF923A96ED4BDC01F87329FA491E08180253A4DE0084C5B7F5B978CC410012F9CFA84C93900A5135BD739835F00540010F8BF1D22A0803706E0A47B3009A587E7D5E4D3A59B4C00E9567300AE791E0DCA3C4A32CDBDC4830056639D57C00D4C401C8791162380021108E26C6D991D10082549218CDC671479A97233D43993D70056663FAC630CB44D2E380592FB93C4F40CA7D1A60FE64348039CE0069E5F565697D59424B92AF246AC065DB01812805AD901552004FDB801E200738016403CC000DD2E0053801E600700091A801ED20065E60071801A800AEB00151316450014388010B86105E13980350423F447200436164688A4001E0488AC90FCDF31074929452E7612B151803A200EC398670E8401B82D04E31880390463446520040A44AA71C25653B6F2FE80124C9FF18EDFCA109275A140289CDF7B3AEEB0C954F4B5FC7CD2623E859726FB6E57DA499EA77B6B68E0401D996D9C4292A881803926FB26232A133598A118023400FA4ADADD5A97CEEC0D37696FC0E6009D002A937B459BDA3CC7FFD65200F2E531581AD80230326E11F52DFAEAAA11DCC01091D8BE0039B296AB9CE5B576130053001529BE38CDF1D22C100509298B9950020B309B3098C002F419100226DC \ No newline at end of file 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