Day 18: Game of tree-life

3 files changed, 157 insertions, 1 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 6ba7437..b1342d1 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,6 +5,7 @@ authors = ["Justin Worthe <justin@worthe-it.co.za>"]
 
 [dependencies]
 im-rc = "12.2.0"
+arrayvec = "0.4.9"
 
 [profile.release]
 debug = true
diff --git a/inputs/18.txt b/inputs/18.txt
new file mode 100644
index 0000000..9e354bc
--- /dev/null
+++ b/inputs/18.txt
@@ -0,0 +1,50 @@
+#.#.|..#|.||.#...|...#.|.......##|##..#..||.||....
+#.......#.....|##..#|..#.##..##|.|.#..|.#...|....#
+.|..........#.|..|.....|..|#.#...##|#|.|#|##|...#|
+#|....#|##..#|.|||.#.|.#...#.##.......#||..#......
+.#|....|.|..#..||...#||...|......###.#.#...##..#..
+..||#...|.#.|||||.....|.......##...#.#....|..#....
+###|..##...|.#|..|.#|#...|.#.|....||.|...#|.|#...#
+|.#.|#.#.|###.|..#..|....#....#|.#..||.||.....#..#
+.#..|.#..#|##..|.....|.#.|.#.#|.......#..|...#..|.
+...|||##...|..#.#|#|..#.#..#|.|.|#..##........##.#
+|#.#..||....|...|#..|....|#|...#.#.#.##|.|.#......
+|..|...|.|#.........|..#|...|.#.|##....|..|..|#.||
+|....#..||..|...#|......|||||.|#....||....|.#|.#..
+......#||.#.#.||..|.......|....||#||#.|.#.|.##||#|
+.##.#....##.#.|....|...###..#...|.#....|.#...|..##
+.##..#|#.#.##.||..|.#|..|.|.##|....|...#||||.|..#.
+|.|..|#|....|.#.#..||.....|.....##....||....|.||..
+#|.|.##...||...........|..#.||.|.#..##..|#||......
+||..||.||..#.##.#...|.#|.....|###....#.....#...|..
+|.#.##|.|...||#.#...||....|.|#..|.#....##........#
+..|....|.#.##|....|||#....#.|.|.##....|##|.|#.....
+.|.....#|.#....|###|..#|||........||#.#..||..|..#.
+#..#...|#|.#...|.||##..#.|..|.|.#.|..#.#.|.....#.#
+|#||.##..#..|||.......#|..#...#..##....#||.#|.....
+.|.#.....|..#...#...##...|.#...|.#|.......|..#...|
+.||.......|..##..##.#|.|..|...#.|.#..#.|....#.|#.|
+....#..#|##|....#..|.#..|||..#....#.#|...||.#..|..
+#......#|.##..|..|....|.##.#|...#..#.|..|..|..|##.
+...|||.#|#.#.|..|||.#.#.#...||...||..##..#.....|..
+..#..|.|#.#..|..##|..#....#.|..|.......|||#.|.|.|#
+.##|..#...#..||..|.........|#.|#.....|...##.|..||#
+#.....||....#.....|#.||......|.#|.#|....||.||.#.#.
+#..|#..|......|.#.#.#.##..||.|.#.|......#|#||#.|.#
+..||..||.....|.#..###.#.|#..|.......|....#||.|..#.
+.#...###|#|#|||...|...#.#|.#|..|...#..#.|#|.#...|.
+...|..#||....##|..#...#....#||#.......|....#.|###.
+..#....|#..#|.....|.#|..#..|#....||......|.|.#.|#.
+..|##....#.|..#..#.|.#..||....#...|.....|..#.....|
+.......#||..#||...|.#.|#...#....|.|.||.#.|...#.##|
+.|.|||.....#............#..#..|..|..#.|.#..|......
+|...|.|####..#.....#..#..|#|#..#..|......|...|.#|#
+|.|...#..#..|....|.....#|#||..#.||..|#|..|||.|.|.|
+..#...|#.......||.#.#.#....#.........##|.|..#.##||
+#|#..|..|#|.##.|.|#......||......|.....#||###.|###
+....#..#.|..|...#|#|..|#..|.#|....||#|.||.|#|.....
+|..#.|..#.|#......#...#|.#|#|.....|#...###....##..
+...##..#..|..#..#.#...|.#..#|...|#.##|.#|..##..#.#
+|.|.|...#.|..##.|.|....|..#..|...|..##|...|..|....
+.#|..|..|..|.|..#...|.||#...#......||.#.#.........
+.#.##..|............|.||.....#||..|##.|..|.....#.|
diff --git a/src/bin/day_18.rs b/src/bin/day_18.rs
index 2eed528..3908ea7 100644
--- a/src/bin/day_18.rs
+++ b/src/bin/day_18.rs
@@ -1,18 +1,123 @@
 extern crate advent_of_code_2018;
 use advent_of_code_2018::*;
 
+extern crate arrayvec;
+use arrayvec::ArrayVec;
+
 use std::error::Error;
 use std::path::PathBuf;
 
+use std::collections::HashMap;
+
 // cargo watch -cs "cargo run --release --bin day_18"
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+enum State {
+    Open,
+    Trees,
+    Lumber
+}
+
 fn main() -> Result<(), Box<Error>> {
     let input = read_file(&PathBuf::from("inputs/18.txt"))?;
 
-    println!("Input: {:?}", input);
+//    println!("Input: {:?}", input);
 
+    let map = input.iter().map(|line| {
+        line.chars().map(|c| match c {
+            '.' => State::Open,
+            '|' => State::Trees,
+            '#' => State::Lumber,
+            _ => panic!("Unknown character {}", c)
+        }).collect::<Vec<_>>()
+    }).collect::<Vec<_>>();
+//    debug!(map);
 
+    let after_10 = simulate(&map, 10);
+    let trees_count_10: usize = after_10.iter().map(|row| row.iter().filter(|&&x| x == State::Trees).count()).sum();
+    let lumber_count_10: usize = after_10.iter().map(|row| row.iter().filter(|&&x| x == State::Lumber).count()).sum();
+    debug!(trees_count_10);
+    debug!(lumber_count_10);
+    debug!(trees_count_10 * lumber_count_10);
+
+    let after_many = simulate(&map, 1000000000);
+    let trees_count_many: usize = after_many.iter().map(|row| row.iter().filter(|&&x| x == State::Trees).count()).sum();
+    let lumber_count_many: usize = after_many.iter().map(|row| row.iter().filter(|&&x| x == State::Lumber).count()).sum();
+    debug!(trees_count_many);
+    debug!(lumber_count_many);
+    debug!(trees_count_many * lumber_count_many);
 
 
     Ok(())
 }
+
+
+fn simulate(start_map: &Vec<Vec<State>>, duration: u32) -> Vec<Vec<State>> {
+    let mut previous_maps = HashMap::new();
+    
+    let mut map = start_map.clone();
+
+    let mut t = 0;
+    while t < duration {
+        let map0 = map.clone();
+        for y in 0..map.len() {
+            for x in 0..map[y].len() {
+                let adjacent = [
+                    (x.wrapping_sub(1), y.wrapping_sub(1)),
+                    (x, y.wrapping_sub(1)),
+                    (x+1, y.wrapping_sub(1)),
+                    (x.wrapping_sub(1), y),
+                    (x+1, y),
+                    (x.wrapping_sub(1), y+1),
+                    (x, y+1),
+                    (x+1, y+1)
+                ].iter().map(|&(other_x,other_y)| {
+                    if other_y >= map0.len() || other_x >= map0[other_y].len() {
+                        State::Open
+                    } else {
+                        map0[other_y][other_x]
+                    }
+                }).collect::<ArrayVec<[State; 8]>>();
+
+                let adjacent_trees = adjacent.iter().filter(|&&x| x == State::Trees).count();
+                let adjacent_lumber = adjacent.iter().filter(|&&x| x == State::Lumber).count();
+
+                map[y][x] = match (map0[y][x], adjacent_trees, adjacent_lumber) {
+                    (State::Open, trees, _) if trees >= 3 => State::Trees,
+                    (State::Open, _, _) => State::Open,
+                    (State::Trees, _, lumber) if lumber >= 3 => State::Lumber,
+                    (State::Trees, _, _) => State::Trees,
+                    (State::Lumber, trees, lumber) if trees >= 1 && lumber >= 1 => State::Lumber,
+                    (State::Lumber, _, _) => State::Open
+                }
+            }
+        }
+
+        t += match previous_maps.get(&map) {
+            Some(previous_t) => {
+                let period = t + 1 - previous_t;
+                let whole_periods = (duration - t - 1) / period;
+                (period * whole_periods) + 1
+            },
+            None => 1
+        };
+        previous_maps.insert(map.clone(), t);
+    }
+
+    map
+}
+
+fn debug_print(map: &Vec<Vec<State>>) {
+    for row in map {
+        for c in row {
+            print!("{}", match c {
+                State::Open => '.',
+                State::Trees => '|',
+                State::Lumber => '#'
+            });
+        }
+        println!();
+    }
+    println!();
+    println!();
+}