11

1 files changed, 275 insertions, 0 deletions

diff --git a/11/src/main.rs b/11/src/main.rs
new file mode 100644
index 0000000..1ea6365
--- /dev/null
+++ b/11/src/main.rs
@@ -0,0 +1,275 @@
+use advent_lib::prelude::*;
+
+use std::convert::TryFrom;
+
+
+#[derive(Clone,Debug,PartialEq)]
+pub enum CellState {
+  Floor,
+  EmptySeat,
+  FullSeat,
+}
+
+
+pub fn debug_grid(grid: &Vec<Vec<CellState>>) {
+  let mut output = String::new();
+
+  for row in grid {
+    for cell in row {
+      match cell {
+        CellState::Floor => {
+          output.push_str(".");
+        }
+        CellState::EmptySeat => {
+          output.push_str("L");
+        }
+        CellState::FullSeat => {
+          output.push_str("#");
+        }
+      }
+    }
+    output.push_str("\n");
+  }
+  output.push_str("\n");
+  println!("{}", output);
+}
+
+
+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 original_grid: Vec<Vec<CellState>> = Vec::new();
+
+  for line in &input {
+    let mut row: Vec<CellState> = Vec::new();
+
+    for c in line.chars() {
+      if c == 'L' {
+        row.push(CellState::EmptySeat);
+      } else {
+        row.push(CellState::Floor);
+      }
+    }
+
+    original_grid.push(row);
+  }
+
+  let mut grid = original_grid.clone();
+  let nearby_seats = compute_nearby_seats(&original_grid);
+
+  loop {
+    let (any_changed, new_grid) = simulate_one(&grid);
+    if !any_changed {
+      break;
+    }
+    grid = new_grid;
+  }
+
+  println!("{}", count_full_seats(&grid));
+
+  let mut grid = original_grid.clone();
+
+  let mut n_iterations = 0;
+
+  loop {
+    let (any_changed, new_grid) = simulate_distancey_one(&grid, &nearby_seats);
+    if !any_changed {
+      break;
+    }
+    grid = new_grid;
+    n_iterations += 1;
+    if n_iterations % 1000 == 0 {
+      println!("iteration {}", n_iterations);
+      debug_grid(&grid);
+    }
+  }
+
+  println!("{}", count_full_seats(&grid));
+
+  Ok(())
+}
+
+
+fn simulate_one(input_grid: &Vec<Vec<CellState>>) -> (bool, Vec<Vec<CellState>>) {
+  let mut output_grid: Vec<Vec<CellState>> = Vec::new();
+  let mut any_changed = false;
+
+  for y in 0 .. input_grid.len() {
+    let mut output_row: Vec<CellState> = Vec::new();
+
+    for x in 0 .. input_grid[y].len() {
+      let mut adjacent_count = 0;
+
+      let mut nearby_x_min = x;
+      if nearby_x_min > 0 {
+        nearby_x_min -= 1;
+      }
+
+      let mut nearby_x_max = x;
+      if nearby_x_max + 1 < input_grid[y].len() {
+        nearby_x_max += 1;
+      }
+
+      let mut nearby_y_min = y;
+      if nearby_y_min > 0 {
+        nearby_y_min -= 1;
+      }
+
+      let mut nearby_y_max = y;
+      if nearby_y_max + 1 < input_grid.len() {
+        nearby_y_max += 1;
+      }
+
+      for nearby_x in nearby_x_min .. nearby_x_max + 1 {
+        for nearby_y in nearby_y_min .. nearby_y_max + 1 {
+          if nearby_x == x && nearby_y == y {
+            continue;
+          }
+
+          let nearby_cell = &input_grid[nearby_y][nearby_x];
+
+          if *nearby_cell == CellState::FullSeat {
+            adjacent_count += 1;
+          }
+        }
+      }
+
+      let input_cell = &input_grid[y][x];
+      if *input_cell == CellState::Floor {
+        output_row.push(CellState::Floor);
+      } else if *input_cell == CellState::EmptySeat && adjacent_count == 0 {
+        output_row.push(CellState::FullSeat);
+        any_changed = true;
+      } else if *input_cell == CellState::FullSeat && adjacent_count >= 4 {
+        output_row.push(CellState::EmptySeat);
+        any_changed = true;
+      } else {
+        output_row.push(input_cell.clone());
+      }
+    }
+
+    output_grid.push(output_row);
+  }
+
+  (any_changed, output_grid)
+}
+
+
+fn simulate_distancey_one(
+    input_grid: &Vec<Vec<CellState>>,
+    nearby_seats: &Vec<Vec<Vec<(usize, usize)>>>)
+  -> (bool, Vec<Vec<CellState>>)
+{
+  let mut output_grid: Vec<Vec<CellState>> = Vec::new();
+  let mut any_changed = false;
+
+  for y in 0 .. input_grid.len() {
+    let mut output_row: Vec<CellState> = Vec::new();
+
+    for x in 0 .. input_grid[y].len() {
+      let mut adjacent_count = 0;
+
+      for (nearby_x, nearby_y) in &nearby_seats[y][x] {
+        let nearby_cell = &input_grid[*nearby_y][*nearby_x];
+
+        if *nearby_cell == CellState::FullSeat {
+          adjacent_count += 1;
+        }
+      }
+
+      let input_cell = &input_grid[y][x];
+      if *input_cell == CellState::Floor {
+        output_row.push(CellState::Floor);
+      } else if *input_cell == CellState::EmptySeat && adjacent_count == 0 {
+        output_row.push(CellState::FullSeat);
+        any_changed = true;
+      } else if *input_cell == CellState::FullSeat && adjacent_count >= 5 {
+        output_row.push(CellState::EmptySeat);
+        any_changed = true;
+      } else {
+        output_row.push(input_cell.clone());
+      }
+    }
+
+    output_grid.push(output_row);
+  }
+
+  (any_changed, output_grid)
+}
+
+
+fn compute_nearby_seats(input_grid: &Vec<Vec<CellState>>)
+  -> Vec<Vec<Vec<(usize, usize)>>>
+{
+  let mut nearby_seats: Vec<Vec<Vec<(usize, usize)>>> = Vec::new();
+
+  let mut max_dimension: isize = isize::try_from(input_grid.len()).unwrap();
+  if isize::try_from(input_grid[0].len()).unwrap() > max_dimension {
+    max_dimension = isize::try_from(input_grid[0].len()).unwrap();
+  }
+
+  for y in 0 .. input_grid.len() {
+    let mut nearby_seats_row: Vec<Vec<(usize, usize)>> = Vec::new();
+
+    for x in 0 .. input_grid[y].len() {
+      let mut nearby_seats_one: Vec<(usize, usize)> = Vec::new();
+
+      for (dx, dy) in [
+        (-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1) ].iter()
+      {
+        for distance in 1 .. max_dimension {
+          let nearby_y = isize::try_from(y).unwrap() + dy * distance;
+          let nearby_x = isize::try_from(x).unwrap() + dx * distance;
+
+          if nearby_y < 0 || usize::try_from(nearby_y).unwrap() >= input_grid.len() {
+            break;
+          }
+
+          if nearby_x < 0 || usize::try_from(nearby_x).unwrap()
+              >= input_grid[usize::try_from(nearby_y).unwrap()].len()
+          {
+            break;
+          }
+
+          let nearby_cell = &input_grid[usize::try_from(nearby_y).unwrap()]
+            [usize::try_from(nearby_x).unwrap()];
+
+          if *nearby_cell == CellState::FullSeat || *nearby_cell == CellState::EmptySeat {
+            nearby_seats_one.push((usize::try_from(nearby_x).unwrap(),
+                usize::try_from(nearby_y).unwrap()));
+            break;
+          }
+        }
+      }
+
+      nearby_seats_row.push(nearby_seats_one);
+    }
+
+    nearby_seats.push(nearby_seats_row);
+  }
+
+  nearby_seats
+}
+
+
+fn count_full_seats(grid: &Vec<Vec<CellState>>) -> i64 {
+  let mut count = 0;
+
+  for row in grid {
+    for cell in row {
+      if *cell == CellState::FullSeat {
+        count += 1;
+      }
+    }
+  }
+
+  count
+}
+