1  #![feature(test)]
 2  
 3  use std::iter::successors;
 4  
 5  use num::Integer;
 6  use rustc_hash::{FxHashMap, FxHashSet};
 7  
 8  type Input = Vec<Vec<u8>>;
 9  type Position = (usize, usize);
10  
11  fn setup(input: &str) -> Input {
12      input
13          .trim()
14          .lines()
15          .map(|line| line.bytes().collect())
16          .collect()
17  }
18  
19  fn solve<I>(input: &Input, antinode_positions: impl Fn(Position, Position) -> I) -> usize
20  where
21      I: Iterator<Item = Position>,
22  {
23      let mut frequency_map = FxHashMap::<_, Vec<_>>::default();
24      for (y, row) in input.iter().enumerate() {
25          for (x, &c) in row.iter().enumerate() {
26              if c != b'.' {
27                  frequency_map.entry(c).or_default().push((x, y));
28              }
29          }
30      }
31  
32      let mut antinodes = FxHashSet::default();
33      for antennas in frequency_map.values() {
34          for (i, &a) in antennas.iter().enumerate() {
35              for &b in &antennas[..i] {
36                  antinodes.extend(antinode_positions(a, b));
37              }
38          }
39      }
40  
41      antinodes.len()
42  }
43  
44  fn part1(input: &Input) -> usize {
45      solve(input, |(x1, y1), (x2, y2)| {
46          let (x1, y1, x2, y2) = (x1 as isize, y1 as isize, x2 as isize, y2 as isize);
47          let (dx, dy) = (x2 - x1, y2 - y1);
48          [(x1 - dx, y1 - dy), (x2 + dx, y2 + dy)]
49              .into_iter()
50              .flat_map(|(x, y)| Some((x.try_into().ok()?, y.try_into().ok()?)))
51              .filter(|&(x, y)| x < input[0].len() && y < input.len())
52      })
53  }
54  
55  fn part2(input: &Input) -> usize {
56      let on_grid = |(x, y): &(isize, isize)| {
57          (0..input[0].len() as _).contains(x) && (0..input.len() as _).contains(y)
58      };
59      solve(input, |(x1, y1), (x2, y2)| {
60          let (x1, y1, x2, y2) = (x1 as isize, y1 as isize, x2 as isize, y2 as isize);
61          let (dx, dy) = (x2 - x1, y2 - y1);
62          let gcd = dx.abs().gcd(&dy.abs());
63          let (dx, dy) = (dx / gcd, dy / gcd);
64  
65          successors(Some((x1, y1)), move |&(x, y)| {
66              Some((x + dx, y + dy)).filter(on_grid)
67          })
68          .chain(successors(Some((x2, y2)), move |&(x, y)| {
69              Some((x - dx, y - dy)).filter(on_grid)
70          }))
71          .map(|(x, y)| (x as _, y as _))
72      })
73  }
74  
75  aoc::main!(2024, 8, ex: 1);