From fec42f6c7340521d5ba070c7fb5ef11eca33a356 Mon Sep 17 00:00:00 2001 From: Jordan Doyle Date: Wed, 27 Dec 2023 18:29:37 +0000 Subject: [PATCH] Add day 21 --- 2023/17.rs | 19 ++++++++++--------- 2023/21.rs | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Cargo.toml | 4 ++++ 3 files changed, 176 insertions(+), 9 deletions(-) create mode 100644 2023/21.rs diff --git a/2023/17.rs b/2023/17.rs index 79dd8f3..5bb4422 100644 --- a/2023/17.rs +++ b/2023/17.rs @@ -20,8 +20,8 @@ fn part1(input: &[Vec]) { let (distance, path) = dijkstra(input, start, end, 0, 3).unwrap(); - print_grid(input, path); - eprintln!("part 1: {:?}", distance); + print_grid(input, &path); + eprintln!("part 1: {distance:?}"); } fn part2(input: &[Vec]) { @@ -30,10 +30,11 @@ fn part2(input: &[Vec]) { let (distance, path) = dijkstra(input, start, end, 4, 10).unwrap(); - print_grid(input, path); - eprintln!("part 1: {:?}", distance); + print_grid(input, &path); + eprintln!("part 1: {distance:?}"); } +#[allow(clippy::type_complexity)] fn dijkstra( input: &[Vec], start: (usize, usize), @@ -129,7 +130,7 @@ fn dijkstra( None } -fn print_grid(input: &[Vec], visited: HashMap<(usize, usize), Direction>) { +fn print_grid(input: &[Vec], visited: &HashMap<(usize, usize), Direction>) { for (y, a) in input.iter().enumerate() { for (x, v) in a.iter().enumerate() { match visited.get(&(x, y)) { @@ -138,7 +139,7 @@ fn print_grid(input: &[Vec], visited: HashMap<(usize, usize), Direction>) { Some(Direction::Left) => print!("<"), Some(Direction::Right) => print!(">"), Some(Direction::None) => print!("*"), - None => print!("{}", v), + None => print!("{v}"), } } @@ -163,7 +164,7 @@ impl Ord for NodeInfo { impl PartialOrd for NodeInfo { fn partial_cmp(&self, other: &Self) -> Option { - self.cost.partial_cmp(&other.cost) + Some(self.cmp(other)) } } @@ -189,9 +190,9 @@ impl Direction { } fn parse_input(input: &[u8]) -> Vec> { - std::str::from_utf8(&input) + std::str::from_utf8(input) .unwrap() - .split("\n") + .split('\n') .map(|v| { v.chars() .map(|c| u8::try_from(c.to_digit(10).unwrap()).unwrap()) diff --git a/2023/21.rs b/2023/21.rs new file mode 100644 index 0000000..ea49df9 --- /dev/null +++ b/2023/21.rs @@ -0,0 +1,162 @@ +use std::{ + collections::HashSet, + io::Read, + ops::{Add, Rem}, +}; + +fn main() { + let mut input = String::new(); + std::io::stdin().lock().read_to_string(&mut input).unwrap(); + let (origin, obstructions, canvas_size) = parse_input(input.trim()); + + part1(origin, &obstructions, canvas_size); + part2(origin, &obstructions, canvas_size); +} + +fn part1(origin: Point, obstructions: &HashSet, bounds: Point) { + eprintln!("{}", bfs(origin, obstructions, 64, bounds)); +} + +fn part2(origin: Point, obstructions: &HashSet, canvas_size: Point) { + let c = canvas_size.0; + let n = f64::from(26_501_365_i32 / c + 1); + let r = 26_501_365_i32 % c; + + let x1 = f64::from(bfs(origin, obstructions, r, canvas_size)); + let x2 = f64::from(bfs(origin, obstructions, r + c, canvas_size)); + let x3 = f64::from(bfs(origin, obstructions, r + (c * 2), canvas_size)); + + let coeffs = divided_difference([x1, x2, x3]); + eprintln!("{}", interpolate(&coeffs, n)); +} + +fn divided_difference(y: [f64; N]) -> [f64; N] { + let mut coefficients = [0.0; N]; + let mut divided_diff = y; + + for i in 0..N { + coefficients[i] = divided_diff[i]; + + for j in (i + 1..N).rev() { + let i = u32::try_from(i).unwrap(); + divided_diff[j] = (divided_diff[j] - divided_diff[j - 1]) / f64::from(i + 1); + } + } + + coefficients +} + +fn interpolate(coefficients: &[f64], x: f64) -> f64 { + let mut result = 0.0; + let mut term = 1.0; + + for (i, &coeff) in coefficients.iter().enumerate() { + result += coeff * term; + term *= x - f64::from(u32::try_from(i).unwrap() + 1); + } + + result +} + +fn bfs(origin: Point, obstructions: &HashSet, max_steps: i32, bounds: Point) -> u32 { + let mut queue = Vec::new(); + queue.push((origin, 0_i32)); + + let mut visited = HashSet::new(); + let mut out = 0; + + while let Some((pos, steps)) = queue.pop() { + if !visited.insert((pos, steps)) { + continue; + } + + if steps == max_steps { + out += 1; + continue; + } + + for d in Direction::ALL { + let p = pos.go(d); + + if obstructions.contains(&(((p % bounds) + bounds.0) % bounds)) { + continue; + } + + queue.push((p, steps + 1)); + } + } + + out +} + +#[derive(Hash, Eq, PartialEq, Debug, Copy, Clone)] +pub struct Point(i32, i32); + +impl Add for Point { + type Output = Self; + + fn add(self, rhs: i32) -> Self::Output { + Self(self.0 + rhs, self.1 + rhs) + } +} + +impl Rem for Point { + type Output = Self; + + fn rem(self, rhs: Self) -> Self::Output { + Self(self.0 % rhs.0, self.1 % rhs.1) + } +} + +impl Point { + #[must_use] + pub fn go(self, d: Direction) -> Self { + let Self(x, y) = self; + + let (nx, ny) = match d { + Direction::Left => (x - 1, y), + Direction::Right => (x + 1, y), + Direction::Up => (x, y - 1), + Direction::Down => (x, y + 1), + }; + + Self(nx, ny) + } +} + +#[derive(Copy, Clone)] +pub enum Direction { + Left, + Right, + Up, + Down, +} + +impl Direction { + const ALL: [Self; 4] = [Self::Left, Self::Right, Self::Up, Self::Down]; +} + +fn parse_input(s: &str) -> (Point, HashSet, Point) { + let mut origin = None; + let mut obstructions = HashSet::new(); + + let mut x = 0; + let mut y = 0; + + for c in s.chars() { + if c == '#' { + obstructions.insert(Point(x, y)); + } else if c == 'S' { + origin = Some(Point(x, y)); + } + + if c == '\n' { + x = 0; + y += 1; + } else { + x += 1; + } + } + + (origin.unwrap(), obstructions, Point(x, y + 1)) +} diff --git a/Cargo.toml b/Cargo.toml index 81e5c71..4ac3eec 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -11,6 +11,10 @@ nom = "7" itertools = "0.12" [[bin]] +name = "aoc2023-21" +path = "2023/21.rs" + +[[bin]] name = "aoc2023-17" path = "2023/17.rs" -- libgit2 1.7.2