3 files changed, 249 insertions, 0 deletions

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 <git@federicoigne.com>"]
+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<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));
+    }
+}