From 120d53c0ff20574866ce10fa0538fb8b0dd2ef82 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Thu, 23 Jun 2022 19:06:22 +0100 Subject: Reorganize repository structure --- day16/src/main.rs | 239 ------------------------------------------------------ 1 file changed, 239 deletions(-) delete mode 100644 day16/src/main.rs (limited to 'day16/src/main.rs') diff --git a/day16/src/main.rs b/day16/src/main.rs deleted file mode 100644 index 9f8352c..0000000 --- a/day16/src/main.rs +++ /dev/null @@ -1,239 +0,0 @@ -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