🏡 index : ~doyle/aoc.git

44230d5670356d2fddb1943c3beb75e13f31333d [patch]

14e61bf4a5a18ae92496b79e9c32816de5468f31

7049e491a67e4401d4631a2de6a1069533c123ad

44230d5670356d2fddb1943c3beb75e13f31333d.tar.gz

Add 2024 day 20

Diff

 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
}