1 files changed, 239 insertions, 0 deletions

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<BITSPacket>
+}
+
+#[derive(Debug)]
+enum BITSPacket {
+    Literal(u64),
+    Operator(u8, Vec<Box<BITS>>)
+}
+
+/* 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<u8> {
+    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<Box<BITS>> {
+    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<Box<BITS>>, 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<u64> = 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));
+    }
+}