summaryrefslogtreecommitdiff
path: root/2018
diff options
context:
space:
mode:
authorTom Smeding <tom.smeding@gmail.com>2018-12-18 14:36:11 +0100
committerTom Smeding <tom.smeding@gmail.com>2018-12-18 14:36:11 +0100
commit57a5348f7f101b00ccca5c5db2f843465430c5ba (patch)
tree1bff232defb43561685df9806bbfea3977b6e694 /2018
parente9f9fc18cce35fbc9eb3fd682716fc948f1e776f (diff)
Day 18
Diffstat (limited to '2018')
-rw-r--r--2018/input/18.txt50
-rw-r--r--2018/src/day18.rs141
-rw-r--r--2018/src/main.rs4
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"))
}
}