From 44230d5670356d2fddb1943c3beb75e13f31333d Mon Sep 17 00:00:00 2001 From: Jordan Doyle Date: Sat, 28 Dec 2024 15:05:41 +0700 Subject: [PATCH] Add 2024 day 20 --- Cargo.lock | 23 +++++++++++++++++++++++ Cargo.toml | 6 ++++-- README | 4 ++-- 2024/20.rs | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 130 insertions(+), 4 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 367bc66..cff2461 100644 --- a/Cargo.lock +++ a/Cargo.lock @@ -14,6 +14,7 @@ dependencies = [ "anyhow", "arrayvec", + "indexmap", "itertools", "nom", "rangemap", @@ -34,10 +35,32 @@ checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07" [[package]] +name = "equivalent" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5" + +[[package]] +name = "hashbrown" +version = "0.15.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bf151400ff0baff5465007dd2f3e717f3fe502074ca563069ce3a6629d07b289" + +[[package]] name = "heck" version = "0.4.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "95505c38b4572b2d910cecb0281560f54b440a19336cbbcb27bf6ce6adc6f5a8" + +[[package]] +name = "indexmap" +version = "2.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62f822373a4fe84d4bb149bf54e584a7f4abec90e072ed49cda0edea5b95471f" +dependencies = [ + "equivalent", + "hashbrown", +] [[package]] name = "itertools" diff --git a/Cargo.toml b/Cargo.toml index 388d4f9..0a20261 100644 --- a/Cargo.toml +++ a/Cargo.toml @@ -11,6 +11,7 @@ nom = "7" itertools = "0.12" trie-hard = "0.1" +indexmap = "2.7" [[bin]] name = "aoc2023-21" @@ -52,8 +53,9 @@ name = "aoc2024-19" path = "2024/19.rs" -[profile.release] -overflow-checks = true +[[bin]] +name = "aoc2024-20" +path = "2024/20.rs" [lints.clippy] pedantic = "deny" diff --git a/README b/README index f9890ae..0d103ca 100644 --- a/README +++ a/README @@ -33,8 +33,8 @@ | 17 | OCaml | | 17 | Rust | | 18 | OCaml | | 18 | Haskell | | 19 | Rust | | 19 | Haskell | -+---------------------+ | 20 | Haskell | - | 21 | Rust | +| 20 | Rust | | 20 | Haskell | ++---------------------+ | 21 | Rust | | 22 | Haskell | | 23 | Haskell | | 24 | Haskell | diff --git a/2024/20.rs b/2024/20.rs new file mode 100644 index 0000000..514631d 100644 --- /dev/null +++ a/2024/20.rs @@ -1,0 +1,101 @@ +#![allow(clippy::cast_possible_wrap)] +use std::{ + collections::{HashSet, VecDeque}, + io::Read, +}; + +use indexmap::IndexMap; +use itertools::Itertools; + +fn main() -> anyhow::Result<()> { + let mut input = String::new(); + std::io::stdin().read_to_string(&mut input)?; + + let input = parse_input(&input); + + let distances = dists(&input); + + part1(&distances); + part2(&distances); + + Ok(()) +} + +fn part1(distances: &IndexMap<(usize, usize), isize>) { + let mut out = 0; + + for ((node1, d1), (node2, d2)) in distances.iter().tuple_combinations() { + let dist = (node1.0.abs_diff(node2.0) + node1.1.abs_diff(node2.1)) as isize; + + if dist == 2 && d2 - d1 - dist >= 100 { + out += 1; + } + } + + eprintln!("{out}"); +} + +fn part2(distances: &IndexMap<(usize, usize), isize>) { + let mut out = 0; + + for ((node1, d1), (node2, d2)) in distances.iter().tuple_combinations() { + let dist = (node1.0.abs_diff(node2.0) + node1.1.abs_diff(node2.1)) as isize; + + if dist <= 20 && d2 - d1 - dist >= 100 { + out += 1; + } + } + + eprintln!("{out}"); +} + +fn dists(input: &Input) -> IndexMap<(usize, usize), isize> { + let mut queue = VecDeque::new(); + let mut distances = IndexMap::new(); + + distances.insert(input.start, 0); + queue.push_back((input.start, 0)); + + while let Some(((nx, ny), dist)) = queue.pop_front() { + for next in [ + (nx.wrapping_sub(1), ny), + (nx + 1, ny), + (nx, ny.wrapping_sub(1)), + (nx, ny + 1), + ] { + if input.grid.contains(&next) && !distances.contains_key(&next) { + distances.insert(next, dist + 1); + queue.push_back((next, dist + 1)); + } + } + } + + distances +} + +#[derive(Default, Debug, Clone)] +pub struct Input { + start: (usize, usize), + end: (usize, usize), + grid: HashSet<(usize, usize)>, +} + +fn parse_input(s: &str) -> Input { + let mut input = Input::default(); + + for (y, s) in s.trim().lines().enumerate() { + for (x, c) in s.chars().enumerate() { + match c { + '#' => continue, + 'S' => input.start = (x, y), + 'E' => input.end = (x, y), + '.' => (), + _ => panic!("invalid char in input: {c}"), + } + + input.grid.insert((x, y)); + } + } + + input +} -- rgit 0.1.5