120 lines
3.1 KiB
Rust
120 lines
3.1 KiB
Rust
#![feature(test)]
|
|
|
|
use aoc::grid::Direction;
|
|
use itertools::Itertools;
|
|
|
|
type Input = Vec<Vec<u8>>;
|
|
|
|
fn setup(input: &str) -> Input {
|
|
input
|
|
.trim()
|
|
.lines()
|
|
.map(|line| line.bytes().collect())
|
|
.collect()
|
|
}
|
|
|
|
struct Regions {
|
|
area_by_id: Vec<usize>,
|
|
id_by_idx: Vec<usize>,
|
|
}
|
|
|
|
fn dfs(input: &Input) -> Regions {
|
|
let rows = input.len();
|
|
let cols = input[0].len();
|
|
|
|
let mut stack = (0..rows)
|
|
.flat_map(|i| (0..cols).map(move |j| (i, j, usize::MAX)))
|
|
.collect::<Vec<_>>();
|
|
let mut visited = vec![false; rows * cols];
|
|
|
|
let mut regions = Regions {
|
|
area_by_id: Vec::new(),
|
|
id_by_idx: vec![usize::MAX; rows * cols],
|
|
};
|
|
|
|
while let Some((i, j, mut region_id)) = stack.pop() {
|
|
let idx = i * cols + j;
|
|
if visited[idx] {
|
|
continue;
|
|
};
|
|
visited[idx] = true;
|
|
|
|
if region_id == usize::MAX {
|
|
region_id = regions.area_by_id.len();
|
|
regions.area_by_id.push(0);
|
|
}
|
|
|
|
regions.id_by_idx[idx] = region_id;
|
|
regions.area_by_id[region_id] += 1;
|
|
|
|
stack.extend(
|
|
Direction::iter()
|
|
.flat_map(|d| d.step(j, i, cols, rows))
|
|
.filter(|&(nj, ni)| input[ni][nj] == input[i][j])
|
|
.map(|(nj, ni)| (ni, nj, region_id)),
|
|
);
|
|
}
|
|
|
|
regions
|
|
}
|
|
|
|
fn part1(input: &Input) -> usize {
|
|
let rows = input.len();
|
|
let cols = input[0].len();
|
|
|
|
let regions = dfs(input);
|
|
|
|
let mut region_perimeters = regions
|
|
.area_by_id
|
|
.iter()
|
|
.map(|&area| area * 4)
|
|
.collect::<Vec<_>>();
|
|
(0..rows)
|
|
.flat_map(|i| (0..cols).map(move |j| (i, j)))
|
|
.for_each(|(i, j)| {
|
|
region_perimeters[regions.id_by_idx[i * cols + j]] -= Direction::iter()
|
|
.flat_map(|d| d.step(j, i, cols, rows))
|
|
.filter(|&(nj, ni)| input[ni][nj] == input[i][j])
|
|
.count();
|
|
});
|
|
|
|
regions
|
|
.area_by_id
|
|
.into_iter()
|
|
.zip(region_perimeters)
|
|
.map(|(area, perimeter)| area * perimeter)
|
|
.sum()
|
|
}
|
|
|
|
fn part2(input: &Input) -> usize {
|
|
let rows = input.len();
|
|
let cols = input[0].len();
|
|
|
|
let regions = dfs(input);
|
|
|
|
let mut corner_counts = vec![0; regions.area_by_id.len()];
|
|
(0..=rows)
|
|
.flat_map(|i| (0..=cols).map(move |j| (i, j)))
|
|
.for_each(|(i, j)| {
|
|
[(0, 0), (0, 1), (1, 1), (1, 0)]
|
|
.map(|(ci, cj)| {
|
|
((1..=cols).contains(&(i + ci)) && (1..=rows).contains(&(j + cj)))
|
|
.then(|| regions.id_by_idx[(i + ci - 1) * cols + j + cj - 1])
|
|
.unwrap_or(usize::MAX)
|
|
})
|
|
.into_iter()
|
|
.circular_tuple_windows()
|
|
.filter(|&(a, _, _, _)| a != usize::MAX)
|
|
.filter(|&(a, b, c, d)| a != b && a != d || a == b && a == d && a != c)
|
|
.for_each(|(a, _, _, _)| corner_counts[a] += 1);
|
|
});
|
|
|
|
regions
|
|
.area_by_id
|
|
.into_iter()
|
|
.zip(corner_counts)
|
|
.map(|(area, corners)| area * corners)
|
|
.sum()
|
|
}
|
|
|
|
aoc::main!(2024, 12, ex: 1, 2, 3, 4, 5);
|