Add day 21
Diff
2023/17.rs | 19 +++----
2023/21.rs | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
Cargo.toml | 4 ++-
3 files changed, 176 insertions(+), 9 deletions(-)
@@ -20,8 +20,8 @@ fn part1(input: &[Vec<u8>]) {
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<u8>]) {
@@ -30,10 +30,11 @@ fn part2(input: &[Vec<u8>]) {
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<u8>],
start: (usize, usize),
@@ -129,7 +130,7 @@ fn dijkstra(
None
}
fn print_grid(input: &[Vec<u8>], visited: HashMap<(usize, usize), Direction>) {
fn print_grid(input: &[Vec<u8>], 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<u8>], 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<std::cmp::Ordering> {
self.cost.partial_cmp(&other.cost)
Some(self.cmp(other))
}
}
@@ -189,9 +190,9 @@ impl Direction {
}
fn parse_input(input: &[u8]) -> Vec<Vec<u8>> {
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())
@@ -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<Point>, bounds: Point) {
eprintln!("{}", bfs(origin, obstructions, 64, bounds));
}
fn part2(origin: Point, obstructions: &HashSet<Point>, 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<const N: usize>(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<Point>, 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<i32> 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>, 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))
}
@@ -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"