diff options
| -rw-r--r-- | 2018/input/18.txt | 50 | ||||
| -rw-r--r-- | 2018/src/day18.rs | 141 | ||||
| -rw-r--r-- | 2018/src/main.rs | 4 |
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")) } } |