136 lines
3.4 KiB
Rust
136 lines
3.4 KiB
Rust
#![feature(test)]
|
|
|
|
use std::collections::VecDeque;
|
|
|
|
use aoc::grid::Direction;
|
|
use itertools::Itertools;
|
|
|
|
struct Input {
|
|
width: usize,
|
|
height: usize,
|
|
grid: Vec<usize>,
|
|
prefix_len: usize,
|
|
bytes: Vec<(usize, usize)>,
|
|
}
|
|
|
|
fn setup(input: &str) -> Input {
|
|
let mut lines = input.trim().lines().peekable();
|
|
let (width, height, prefix_len) = match lines.next_if(|l| l.starts_with('#')) {
|
|
Some(line) => line
|
|
.trim_start_matches('#')
|
|
.split_whitespace()
|
|
.map(|n| n.parse().unwrap())
|
|
.collect_tuple()
|
|
.unwrap(),
|
|
None => (71, 71, 1024),
|
|
};
|
|
|
|
let bytes = lines
|
|
.map(|l| {
|
|
l.split(',')
|
|
.map(|n| n.parse().unwrap())
|
|
.collect_tuple()
|
|
.unwrap()
|
|
})
|
|
.collect::<Vec<_>>();
|
|
|
|
let mut grid = vec![usize::MAX; width * height];
|
|
for (i, &(x, y)) in bytes.iter().enumerate() {
|
|
grid[y * width + x] = i;
|
|
}
|
|
|
|
Input {
|
|
width,
|
|
height,
|
|
grid,
|
|
prefix_len,
|
|
bytes,
|
|
}
|
|
}
|
|
|
|
struct UnionFind {
|
|
parents: Vec<usize>,
|
|
}
|
|
|
|
impl UnionFind {
|
|
fn new(len: usize) -> Self {
|
|
Self {
|
|
parents: (0..len).collect(),
|
|
}
|
|
}
|
|
|
|
fn find(&mut self, x: usize) -> usize {
|
|
if self.parents[x] == x {
|
|
return x;
|
|
}
|
|
self.parents[x] = self.find(self.parents[x]);
|
|
self.parents[x]
|
|
}
|
|
|
|
fn merge(&mut self, x: usize, y: usize) {
|
|
let x = self.find(x);
|
|
let y = self.find(y);
|
|
self.parents[x] = y;
|
|
}
|
|
}
|
|
|
|
fn part1(input: &Input) -> usize {
|
|
let mut queue = VecDeque::from([(0, 0, 0)]);
|
|
let mut visited = vec![false; input.width * input.height];
|
|
while let Some((d, x, y)) = queue.pop_front() {
|
|
let idx = y * input.width + x;
|
|
if std::mem::replace(&mut visited[idx], true) {
|
|
continue;
|
|
}
|
|
|
|
if (x, y) == (input.width - 1, input.height - 1) {
|
|
return d;
|
|
}
|
|
|
|
queue.extend(
|
|
Direction::iter()
|
|
.flat_map(|d| d.step(x, y, input.width, input.height))
|
|
.filter(|&(nx, ny)| input.grid[ny * input.width + nx] >= input.prefix_len)
|
|
.map(|(nx, ny)| (d + 1, nx, ny)),
|
|
);
|
|
}
|
|
|
|
panic!()
|
|
}
|
|
|
|
fn part2(input: &Input) -> String {
|
|
let mut uf = UnionFind::new(input.width * input.height);
|
|
for y in 0..input.height {
|
|
for x in 0..input.width {
|
|
let idx = y * input.width + x;
|
|
if x + 1 < input.width
|
|
&& input.grid[idx] == usize::MAX
|
|
&& input.grid[idx + 1] == usize::MAX
|
|
{
|
|
uf.merge(idx, idx + 1);
|
|
}
|
|
if y + 1 < input.height
|
|
&& input.grid[idx] == usize::MAX
|
|
&& input.grid[idx + input.width] == usize::MAX
|
|
{
|
|
uf.merge(idx, idx + input.width);
|
|
}
|
|
}
|
|
}
|
|
|
|
for (i, &(x, y)) in input.bytes.iter().enumerate().rev() {
|
|
for (nx, ny) in Direction::iter()
|
|
.flat_map(|d| d.step(x, y, input.width, input.height))
|
|
.filter(|&(nx, ny)| input.grid[ny * input.width + nx] > i)
|
|
{
|
|
uf.merge(y * input.width + x, ny * input.width + nx);
|
|
}
|
|
if uf.find(0) == uf.find(input.width * input.height - 1) {
|
|
return format!("{x},{y}");
|
|
}
|
|
}
|
|
|
|
panic!()
|
|
}
|
|
|
|
aoc::main!(2024, 18, ex: 1);
|