16, yay

10 files changed, 262 insertions, 182 deletions

diff --git a/.gitignore b/.gitignore
index 31158d2..3c3194f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,3 +3,4 @@
 /result-*
 **/*.rs.bk
 *.swp
+*.swo
diff --git a/15/src/main.rs.bak b/15/src/main.rs.bak
deleted file mode 100644
index 33f76e3..0000000
--- a/15/src/main.rs.bak
+++ /dev/null
@@ -1,181 +0,0 @@
-use advent_lib::prelude::*;
-
-
-fn main() -> Result<()> {
-  let mut args = std::env::args();
-  if args.len() != 2 {
-    eprintln!("Usage: advent input");
-  }
-  let _ = args.next();
-  let filename = args.next().unwrap();
-
-  let input = advent_lib::read_lines_file(&filename)?;
-
-  let mut value_grid = Vec::new();
-  let mut risk_grid: Vec<Vec<Option<i64>>> = Vec::new();
-  for line in &input{
-    let mut value_row = Vec::new();
-    let mut risk_row = Vec::new();
-    for c in line.chars() {
-      let value = c.to_digit(10).unwrap() as i64;
-      value_row.push(value);
-      risk_row.push(None);
-    }
-    value_grid.push(value_row);
-    risk_grid.push(risk_row);
-  }
-
-  let height = value_grid.len();
-  let width = value_grid[0].len();
-
-  /*
-  risk_grid[0][0] = Some(0);
-  find_path(0, 0, &value_grid, &mut risk_grid, false);
-  let risk = risk_grid[height - 1][width - 1].unwrap();
-  println!("{}", risk);
-  */
-
-  let mut big_risk_grid = Vec::new();
-  for _ in 0 .. height * 5 {
-    let mut big_risk_grid_row = Vec::new();
-    for _ in 0 .. width * 5 {
-      big_risk_grid_row.push(None);
-    }
-    big_risk_grid.push(big_risk_grid_row);
-  }
-  big_risk_grid[0][0] = Some(0);
-  find_path(0, 0, &value_grid, &mut big_risk_grid, true);
-  let big_risk = big_risk_grid[height * 5 - 1][width * 5 - 1].unwrap();
-  println!("{}", big_risk);
-
-  Ok(())
-}
-
-
-#[allow(dead_code)]
-fn debug_risk_grid(risk_grid: &Vec<Vec<Option<i64>>>) {
-  for row in risk_grid {
-    for cell in row {
-      match cell {
-        None => { print!(" ."); }
-        Some(n) => { print!(" {}", n); }
-      }
-    }
-    println!("");
-  }
-  println!("");
-}
-
-
-fn find_path(x: usize, y: usize, value_grid: &Vec<Vec<i64>>,
-    risk_grid: &mut Vec<Vec<Option<i64>>>, repeat: bool)
-{
-  let mut height = value_grid.len();
-  let mut width = value_grid[0].len();
-  if repeat {
-    width *= 5;
-    height *= 5;
-  }
-
-  let mut exploration_stack = Vec::new();
-  exploration_stack.push((x, y));
-
-  let mut counter = 0;
-
-  loop {
-    let (x, y) = match exploration_stack.pop() {
-      None => { return; }
-      Some(value) => { value }
-    };
-    let risk_so_far = risk_grid[y][x].unwrap();
-    counter += 1;
-    if counter % 100000 == 0 {
-      print!(" [{},{} {}]", x, y, risk_so_far);
-    }
-
-    if x > 0 {
-      let value_left = get_value(x - 1, y, value_grid);
-      let new_risk_left = risk_so_far + value_left;
-
-      let risk_left = risk_grid[y][x-1];
-      let should_move = match risk_left {
-        None => true,
-        Some(prior_best_risk) => {
-          new_risk_left < prior_best_risk
-        }
-      };
-      if should_move {
-        risk_grid[y][x-1] = Some(new_risk_left);
-
-        exploration_stack.push((x - 1, y));
-      }
-    }
-
-    if y > 0 {
-      let value_up = get_value(x, y - 1, value_grid);
-      let new_risk_up = risk_so_far + value_up;
-
-      let risk_up = risk_grid[y-1][x];
-      let should_move = match risk_up {
-        None => true,
-        Some(prior_best_risk) => {
-          new_risk_up < prior_best_risk
-        }
-      };
-      if should_move {
-        risk_grid[y-1][x] = Some(new_risk_up);
-
-        exploration_stack.push((x, y - 1));
-      }
-    }
-
-    if x + 1 < width {
-      let value_right = get_value(x + 1, y, value_grid);
-      let new_risk_right = risk_so_far + value_right;
-
-      let risk_right = risk_grid[y][x+1];
-      let should_move = match risk_right {
-        None => true,
-        Some(prior_best_risk) => {
-          new_risk_right < prior_best_risk
-        }
-      };
-      if should_move {
-        risk_grid[y][x+1] = Some(new_risk_right);
-
-        exploration_stack.push((x + 1, y));
-      }
-    }
-
-    if y + 1 < height {
-      let value_down = get_value(x, y + 1, value_grid);
-      let new_risk_down = risk_so_far + value_down;
-
-      let risk_down = risk_grid[y+1][x];
-      let should_move = match risk_down {
-        None => true,
-        Some(prior_best_risk) => {
-          new_risk_down < prior_best_risk
-        }
-      };
-      if should_move {
-        risk_grid[y+1][x] = Some(new_risk_down);
-
-        exploration_stack.push((x, y + 1));
-      }
-    }
-  }
-}
-
-
-fn get_value(x: usize, y: usize, value_grid: &Vec<Vec<i64>>) -> i64 {
-  let height = value_grid.len();
-  let width = value_grid[0].len();
-
-  let tile_x = x / width;
-  let tile_y = y / height;
-  let increment: i64 = (tile_x + tile_y) as i64;
-  let raw_value = value_grid[y % height][x % width];
-  (raw_value + increment - 1) % 9 + 1
-}
-
diff --git a/15/tests/main.rs b/15/tests/main.rs
index 3e205b0..09dddae 100644
--- a/15/tests/main.rs
+++ b/15/tests/main.rs
@@ -5,7 +5,7 @@ use std::process::Command;
 
 #[test]
 fn personal_input() -> Result<(), Box<dyn std::error::Error>> {
-  let mut command = Command::cargo_bin("advent_14")?;
+  let mut command = Command::cargo_bin("advent_15")?;
 
   command.arg("input");
   command.assert().success().stdout(
diff --git a/16/Cargo.toml b/16/Cargo.toml
new file mode 100644
index 0000000..a8b1866
--- /dev/null
+++ b/16/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "advent_16"
+version = "0.1.0"
+authors = ["Irene Knapp <ireneista@gmail.com>"]
+edition = "2018"
+
+[dependencies]
+advent_lib = { path = "../lib" }
+
+[dev-dependencies]
+assert_cmd = "0.10"
diff --git a/16/input b/16/input
new file mode 100644
index 0000000..019f19b
--- /dev/null
+++ b/16/input
@@ -0,0 +1 @@
+220D790065B2745FF004672D99A34E5B33439D96CEC80373C0068663101A98C406A5E7395DC1804678BF25A4093BFBDB886CA6E11FDE6D93D16A100325E5597A118F6640600ACF7274E6A5829B00526C167F9C089F15973C4002AA4B22E800FDCFD72B9351359601300424B8C9A00BCBC8EE069802D2D0B945002AB2D7D583E3F00016B05E0E9802BA00B4F29CD4E961491CCB44C6008E80273C393C333F92020134B003530004221347F83A200D47F89913A66FB6620016E24A007853BE5E944297AB64E66D6669FCEA0112AE06009CAA57006A0200EC258FB0440010A8A716A321009DE200D44C8E31F00010887B146188803317A3FC5F30056C0150004321244E88C000874468A91D2291802B25EB875802B28D13550030056C0169FB5B7ECE2C6B2EF3296D6FD5F54858015B8D730BB24E32569049009BF801980803B05A3B41F1007625C1C821256D7C848025DE0040E5016717247E18001BAC37930E9FA6AE3B358B5D4A7A6EA200D4E463EA364EDE9F852FF1B9C8731869300BE684649F6446E584E61DE61CD4021998DB4C334E72B78BA49C126722B4E009C6295F879002093EF32A64C018ECDFAF605989D4BA7B396D9B0C200C9F0017C98C72FD2C8932B7EE0EA6ADB0F1006C8010E89B15A2A90021713610C202004263E46D82AC06498017C6E007901542C04F9A0128880449A8014403AA38014C030B08012C0269A8018E007A801620058003C64009810010722EC8010ECFFF9AAC32373F6583007A48CA587E55367227A40118C2AC004AE79FE77E28C007F4E42500D10096779D728EB1066B57F698C802139708B004A5C5E5C44C01698D490E800B584F09C8049593A6C66C017100721647E8E0200CC6985F11E634EA6008CB207002593785497652008065992443E7872714
diff --git a/16/src/main.rs b/16/src/main.rs
new file mode 100644
index 0000000..f4f6253
--- /dev/null
+++ b/16/src/main.rs
@@ -0,0 +1,219 @@
+use advent_lib::prelude::*;
+
+#[derive(Debug)]
+struct Packet {
+  version: u8,
+  type_id: u8,
+  content: Vec<u8>,
+  subpackets: Vec<Packet>,
+}
+
+
+fn main() -> Result<()> {
+  let mut args = std::env::args();
+  if args.len() != 2 {
+    eprintln!("Usage: advent input");
+  }
+  let _ = args.next();
+  let filename = args.next().unwrap();
+
+  let input = advent_lib::read_lines_file(&filename)?;
+
+  let mut bit_string: Vec<u8> = Vec::new();
+  for c in input[0].chars() {
+    let value = c.to_digit(16).unwrap() as u8;
+    for i in 0 .. 4 {
+      let bit = (value >> (3 - i)) & 1;
+      bit_string.push(bit);
+    }
+  }
+
+  let mut iter = bit_string.iter().peekable();
+  let (version_total, _top_packet, result) = read_packet(&mut iter).unwrap();
+  println!("{}", version_total);
+  println!("{}", result);
+
+  Ok(())
+}
+
+
+fn read_packet<'a>(iter: &mut impl Iterator<Item=&'a u8>) -> Result<(u64, Packet, u128)>
+{
+  let mut version_total: u64 = 0;
+
+  let version = bits_to_u8(take_bits(iter, 3)?);
+  let type_id = bits_to_u8(take_bits(iter, 3)?);
+
+  version_total += version as u64;
+
+  if type_id == 4 {
+    let mut result = 0;
+    loop {
+      let bits = take_bits(iter, 5)?;
+
+      let bits_value = bits_to_u128(bits[1..].to_vec());
+      result = result << 4;
+      result += bits_value;
+
+      if bits[0] == 0 {
+        break;
+      }
+    }
+
+    Ok((version_total, Packet {
+      version,
+      type_id,
+      content: Vec::new(),
+      subpackets: Vec::new(),
+    }, result))
+  } else {
+    let mut subpackets = Vec::new();
+    let mut parameters = Vec::new();
+
+    let length_type_id = bits_to_u8(take_bits(iter, 1)?);
+    if length_type_id == 0 {
+      let length_in_bits = bits_to_u64(take_bits(iter, 15)?);
+
+      let mut content_bits: Vec<u8> = Vec::new();
+      for bit in iter.take(length_in_bits as usize) {
+        content_bits.push(*bit);
+      }
+
+      let mut content_bits = content_bits.iter().peekable();
+
+      loop {
+        match read_packet(&mut content_bits) {
+          Err(_) => {
+            break;
+          }
+          Ok((sub_version_total, subpacket, value)) => {
+            version_total += sub_version_total;
+            subpackets.push(subpacket);
+            parameters.push(value);
+          }
+        }
+      }
+    } else {
+      let n_subpackets = bits_to_u64(take_bits(iter, 11)?);
+
+      for _ in 0 .. n_subpackets {
+        match read_packet(iter) {
+          Err(_) => {
+            return Err(advent_lib::error::Error::Unspecified);
+          }
+          Ok((sub_version_total, subpacket, value)) => {
+            version_total += sub_version_total;
+            subpackets.push(subpacket);
+            parameters.push(value);
+          }
+        }
+      }
+    }
+
+    let mut result = 0;
+    match type_id {
+      0 => {
+        result = 0;
+        for parameter in &parameters {
+          result += parameter;
+        }
+      }
+      1 => {
+        result = 1;
+        for parameter in &parameters {
+          result *= parameter;
+        }
+      }
+      2 => {
+        result = parameters[0];
+        for parameter in &parameters {
+          if *parameter < result {
+            result = *parameter;
+          }
+        }
+      }
+      3 => {
+        result = parameters[0];
+        for parameter in &parameters {
+          if *parameter > result {
+            result = *parameter;
+          }
+        }
+      }
+      5 => {
+        result = if parameters[0] > parameters[1] { 1 } else { 0 };
+      }
+      6 => {
+        result = if parameters[0] < parameters[1] { 1 } else { 0 };
+      }
+      7 => {
+        result = if parameters[0] == parameters[1] { 1 } else { 0 };
+      }
+      _ => { }
+    }
+
+    Ok((version_total, Packet {
+      version,
+      type_id,
+      content: Vec::new(),
+      subpackets: subpackets,
+    }, result))
+  }
+}
+
+
+fn take_bits<'a>(iter: &mut impl Iterator<Item=&'a u8>, count: usize)
+  -> Result<Vec<u8>>
+{
+  let mut result: Vec<u8> = Vec::new();
+
+  for _ in 0 .. count {
+    match iter.next() {
+      None => {
+        return Err(advent_lib::error::Error::Unspecified);
+      }
+      Some(bit) => {
+        result.push(*bit);
+      }
+    }
+  }
+
+  Ok(result)
+}
+
+
+fn bits_to_u8(bits: Vec<u8>) -> u8 {
+  let mut result = 0;
+
+  for bit in &bits {
+    result *= 2;
+    result += bit;
+  }
+
+  result
+}
+
+
+fn bits_to_u64(bits: Vec<u8>) -> u64 {
+  let mut result = 0;
+
+  for bit in &bits {
+    result *= 2;
+    result += *bit as u64;
+  }
+
+  result
+}
+
+
+fn bits_to_u128(bits: Vec<u8>) -> u128 {
+  let mut result = 0;
+
+  for bit in &bits {
+    result *= 2;
+    result += *bit as u128;
+  }
+
+  result
+}
+
diff --git a/16/tests/main.rs b/16/tests/main.rs
new file mode 100644
index 0000000..ba7a189
--- /dev/null
+++ b/16/tests/main.rs
@@ -0,0 +1,18 @@
+use assert_cmd::prelude::*;
+//use predicates::prelude::*;
+use std::process::Command;
+
+
+#[test]
+fn personal_input() -> Result<(), Box<dyn std::error::Error>> {
+  let mut command = Command::cargo_bin("advent_16")?;
+
+  command.arg("input");
+  command.assert().success().stdout(
+      "989\n\
+      7936430475134\n");
+
+
+  Ok(())
+}
+
diff --git a/Cargo.lock b/Cargo.lock
index 751fe79..2c1fbd4 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -121,6 +121,14 @@ dependencies = [
 ]
 
 [[package]]
+name = "advent_16"
+version = "0.1.0"
+dependencies = [
+ "advent_lib",
+ "assert_cmd",
+]
+
+[[package]]
 name = "advent_lib"
 version = "0.1.0"
 dependencies = [
diff --git a/Cargo.toml b/Cargo.toml
index d8cc993..4a97c58 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -16,4 +16,5 @@ members = [
   "13",
   "14",
   "15",
+  "16",
 ]
diff --git a/lib/src/error.rs b/lib/src/error.rs
index 4f594b7..ccf01ee 100644
--- a/lib/src/error.rs
+++ b/lib/src/error.rs
@@ -2,6 +2,7 @@
 pub enum Error {
   IO(std::io::Error),
   Parse,
+  Unspecified,
 }
 
 impl std::error::Error for Error { }
@@ -11,6 +12,7 @@ impl std::fmt::Display for Error {
     match self {
       Error::IO(e) => e.fmt(f),
       Error::Parse => f.write_str("Parse error"),
+      Error::Unspecified => f.write_str("Unspecified error (bad luck!)"),
     }
   }
 }