From 44230d5670356d2fddb1943c3beb75e13f31333d Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
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