1  #![feature(test)]
 2  
 3  use rustc_hash::FxHashSet;
 4  
 5  struct Input {
 6      algo: Vec<bool>,
 7      width: usize,
 8      height: usize,
 9      grid: FxHashSet<(i32, i32)>,
10  }
11  
12  fn setup(input: &str) -> Input {
13      let mut lines = input.lines();
14      let algo = lines.next().unwrap().chars().map(|c| c == '#').collect();
15      let grid = lines
16          .skip(1)
17          .enumerate()
18          .flat_map(|(i, line)| {
19              line.chars().enumerate().filter_map(move |(j, c)| {
20                  if c == '#' {
21                      Option::Some((j as i32, i as i32))
22                  } else {
23                      Option::None
24                  }
25              })
26          })
27          .collect();
28      Input {
29          algo,
30          grid,
31          width: input.lines().nth(2).unwrap().len(),
32          height: input.lines().count() - 2,
33      }
34  }
35  
36  fn get_neighbors(x: i32, y: i32) -> Vec<(i32, i32)> {
37      (-1..=1)
38          .flat_map(|dy| (-1..=1).map(move |dx| (x + dx, y + dy)))
39          .collect()
40  }
41  
42  fn solve(input: &Input) -> (usize, usize) {
43      let mut grid = input.grid.clone();
44      let mut inf = false;
45      let mut part1 = 0;
46      let mut part2 = 0;
47      for i in 1..=50 {
48          let new_inf = inf != input.algo[0];
49          grid = (-i..=input.height as i32 + i)
50              .flat_map(|y| (-i..=input.width as i32 + i).map(move |x| (x, y)))
51              .filter(|(x, y)| {
52                  let idx = get_neighbors(*x, *y).iter().fold(0, |acc, (p, q)| {
53                      acc << 1 | (grid.contains(&(*p, *q)) != inf) as usize
54                  });
55                  input.algo[idx] != new_inf
56              })
57              .collect();
58          inf = new_inf;
59          if i == 2 {
60              part1 = grid.len();
61          }
62          if i == 50 {
63              part2 = grid.len();
64          }
65      }
66      (part1, part2)
67  }
68  
69  fn part1(input: &Input) -> usize {
70      solve(input).0
71  }
72  
73  fn part2(input: &Input) -> usize {
74      solve(input).1
75  }
76  
77  aoc::main!(2021, 20, ex: 1);