Day 18

3 files changed, 194 insertions, 1 deletions

diff --git a/2018/input/18.txt b/2018/input/18.txt
new file mode 100644
index 0000000..c5a08e9
--- /dev/null
+++ b/2018/input/18.txt
@@ -0,0 +1,50 @@
+..#..|..|..###.||......#.|##.##.|#.||..#..||...|.|
+#.....#..#.|....|.#.|..#..||##.|.|.||#|........##.
+.||.|..|.|..##|...|.|.|#|..#.|..|#......||.#...#..
+|...#..|..|...|.#||.|||#|..#|..#|..|.||...#.|.|##|
+#......###....||...|#...#|#..||.|..|....##||#..#.#
+.#..#|....|.|...#....#..#.##......|..|.....|#|..|.
+##.|.#.|||..|#.|#.......|..#....##..#|..|##|..|.|.
+..#..#...#|..#.|.#||#.#..#.##|....#...#.||........
+#.##.......|.#...#.|.|.#||##...|||.......||..|||.#
+|#||...#.|.....|..##...###|#.|.|..##.#..|#....#..|
+#..#.....##.#|##.#.||..||.|||#.|......|..#.||||.#.
+..#....#||..|#.....|......#|..#|.|.|#.##|.||.#...#
+..|#..|#.#|...#..#.#####..##..#...........##..#||.
+.|.|..|..#...#....|.|.....###.....|.#|.|||.|..##..
+..#|.##..###...##||.|...|#.#.##.#....|..#.#..|##..
+|...##|.|..##|.|...#..|||.#..##..#....##.....|....
+.#..#....#.#...#|##...#.#..##.|....|##..#..|.....|
+...|...|.....|||.#...|||#.|...||..|#.|..#|....#.#.
+.|....#.......###.....|.#...#..#|..|#..##|........
+|...|.#.|##.|||..#........|...|||.#.|#|.#..|.|#|..
+#|.....|...|...|..##.#...|..|.#.###....#|.|#.#..#.
+.#...|..#.#|...#...|...#.|#..||....|##|.##..|.##.#
+.....##.|......|....|......#.|.|...#.....#|.....##
+..#....#...#...#.|...#.......#||.##..|.#....#|....
+|...|.......|||#.....#|.#........#.|..||.|...#.#..
+.#|###...#.|.|##...|...||##...|.|.|.....#|..#...#.
+#|###..|...##|##.|..#....##.....#...#|..#|.#....|.
+.#.#...|..||...#...|..#......|....||.|#...||..#.#.
+|.#..|####||.|..||.|.#..#....##.........#.#||...#.
+....|.#.#...#....|..|..#..#.....|...#..|.....|.#..
+|....|...|#.#|..#.....#|.|..#..#.#......#..#.#.|#|
+..##.....|....#||...#..|..|.||.#.#....#|.#.|||.||#
+#..#....#.|.|##|##....||.#.#.##..|#..|..||#....||.
+.|.|..|...#|#.|||.....||#....|.##......|||#..#.|..
+...#..|.#.|......#..|..|.##|#..|...##..#......|...
+#...##.|....#....#...##.|.....|||.#...#..|......#.
+...|.||#.||..||....#|#|#..|...#.##..#.##.#|#.#..##
+...|.|#...|.|.||..|#|#...|#|...#..|..#...|##|#....
+..|..|.............####|..#.#.###.#..#.#.#|||.#|#.
+.###||.|#...|..|....#...|||...|...|.....#|.#|||.#.
+.##.|..............|..|..#..##..|##.|#.#..||.|....
+|..#.|||..|.##......|.|.......#.##..||||......#|..
+....#.||.#.||.|.|.#.|.##.|....##.#.||..||..|.#.|.|
+.|..|..#.#.....#|...##|.||.|.|#|.|.#.....#..|.....
+..|..#|#|#....#.||....#||.|..#|#.........#..|..||#
+..##|#......#.#|.|...||.#....|##..|.####.......|#.
+|..||...#.#.##.|...|#|..|#..|#..|.#.#........#...|
+|.|#...|.#.#...#|.#..#..#.......|#.||....#..|...||
+.||...||.||...|#||.#..|........|.....|.|.|.#...#.#
+.......#|........|..|...||...###.|..|#|.|.....||..
diff --git a/2018/src/day18.rs b/2018/src/day18.rs
new file mode 100644
index 0000000..e78c153
--- /dev/null
+++ b/2018/src/day18.rs
@@ -0,0 +1,141 @@
+use std::io;
+use std::io::BufRead;
+use std::iter;
+use std::collections::HashMap;
+
+const DO_COMPARE_GRIDS: bool = true;
+
+fn parse_ch(c: char) -> u8 {
+    match c {
+        '.' => 0,
+        '|' => 1,
+        '#' => 2,
+        _ => unreachable!(),
+    }
+}
+
+fn res_value(grid: &Vec<Vec<u8>>) -> i32 {
+    let mut num1 = 0;
+    let mut num2 = 0;
+
+    for row in grid {
+        for cell in row {
+            num1 += (*cell == 1) as i32;
+            num2 += (*cell == 2) as i32;
+        }
+    }
+
+    return num1 * num2;
+}
+
+fn compute_step(grid: &Vec<Vec<u8>>, grid2: &mut Vec<Vec<u8>>) -> u64 {
+    let mut hash: u64 = 0;
+    let mut rotating_shift = 0;
+
+    for y in 1..grid.len()-1 {
+        for x in 1..grid[0].len()-1 {
+            let mut tots = [0, 0, 0];
+
+            for dy in -1..2 {
+                for dx in -1..2 {
+                    if dy == 0 && dx == 0 { continue; }
+                    tots[grid[(y as isize + dy) as usize][(x as isize + dx) as usize] as usize] += 1;
+                }
+            }
+
+            let v = match (grid[y][x], tots[0], tots[1], tots[2]) {
+                (0, _, n, _) if n >= 3           => 1,
+                (1, _, _, n) if n >= 3           => 2,
+                (2, _, n, m) if n >= 1 && m >= 1 => 2,
+                (2, _, _, _)                     => 0,
+                (v, _, _, _)                     => v,
+            };
+
+            grid2[y][x] = v;
+
+            hash ^= u64::from(v) << rotating_shift | (tots[0] ^ tots[1] ^ tots[2]) << rotating_shift;
+            rotating_shift = (rotating_shift + 1) % 64;
+        }
+    }
+
+    hash
+}
+
+fn grid_equal(grid1: &Vec<Vec<u8>>, grid2: &Vec<Vec<u8>>) -> bool {
+    for (row1, row2) in grid1.iter().zip(grid2.iter()) {
+        for (&v1, &v2) in row1.iter().zip(row2.iter()) {
+            if v1 != v2 {
+                return false;
+            }
+        }
+    }
+
+    true
+}
+
+fn simulate(mut grid: Vec<Vec<u8>>, nsteps: usize) -> i32 {
+    let mut grid2 = grid.clone();
+
+    let mut hash_vals = Vec::new();
+    let mut res_vals = Vec::new();
+    let mut res_map = HashMap::new();
+
+    let mut cycle = None;
+
+    for step in 0..nsteps {
+        let hash = compute_step(&grid, &mut grid2);
+        std::mem::swap(&mut grid, &mut grid2);
+
+        hash_vals.push(hash);
+        let res = res_value(&grid);
+        res_vals.push(res);
+
+        if let Some((cycle_start, cycle_length, ref start_grid)) = cycle {
+            if step - cycle_start == cycle_length {
+                if !DO_COMPARE_GRIDS || grid_equal(&grid, &start_grid) {
+                    // println!("Check at {}: grids equal", step);
+                    return res_vals[cycle_start + (nsteps - 1 - cycle_start) % cycle_length];
+                } else {
+                    println!("Grids not equal");
+                    cycle = None;
+                }
+            }
+        } else if let Some(&prev_step) = res_map.get(&res) {
+            let length = step - prev_step;
+            if prev_step >= length {
+                if (0..length).all(|i| hash_vals[prev_step - i] == hash_vals[step - i]
+                                        && res_vals[prev_step - i] == res_vals[step - i]) {
+                    // println!("cycle: {} length={}", step, length);
+                    cycle = Some((step, length, if DO_COMPARE_GRIDS { grid.clone() } else { Vec::new() }));
+                }
+            }
+        }
+
+        res_map.insert(res, step);
+    }
+
+    res_value(&grid)
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let mut grid = {
+        iter::once(vec![0; 0])
+            .chain(reader.lines().map(|l|
+                iter::once(0)
+                    .chain(l.unwrap().chars().map(|c| parse_ch(c)))
+                    .chain(iter::once(0)).collect()
+            ))
+            .chain(iter::once(vec![0; 0]))
+            .collect::<Vec<Vec<_>>>()
+    };
+
+    let w = grid[1].len();
+    let h = grid.len();
+    grid[0].resize(w, 0);
+    grid[h-1].resize(w, 0);
+
+    let part1 = simulate(grid.clone(), 10);
+    let part2 = simulate(grid, 1000000000);
+
+    Ok((part1.to_string(), part2.to_string()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 21a77df..08b96db 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -22,8 +22,9 @@ mod day14;
 mod day15;
 mod day16;
 mod day17;
+mod day18;
 
-static NUM_DAYS: i32 = 17;
+static NUM_DAYS: i32 = 18;
 
 fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
@@ -44,6 +45,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
         15 => day15::main(reader),
         16 => day16::main(reader),
         17 => day17::main(reader),
+        18 => day18::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }