🏡 index : ~doyle/aoc.git

7049e491a67e4401d4631a2de6a1069533c123ad [patch]

b8a10e518a388fa99d9860b17512a7f5cb5fb4fa

b9437d842566f234f7df5581e37db6cbe23da32a

7049e491a67e4401d4631a2de6a1069533c123ad.tar.gz

Add 2024 day 19

Diff

 Cargo.lock |  7 +++++++
 Cargo.toml |  5 +++++
 README     |  4 ++--
 2024/13.rs |  2 +-
 2024/19.rs | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 91 insertions(+), 3 deletions(-)

diff --git a/Cargo.lock b/Cargo.lock
index 174e56a..367bc66 100644
--- a/Cargo.lock
+++ a/Cargo.lock
@@ -18,6 +18,7 @@
 "nom",
 "rangemap",
 "strum",
 "trie-hard",
]

[[package]]
@@ -131,6 +132,12 @@
 "quote",
 "unicode-ident",
]

[[package]]
name = "trie-hard"
version = "0.1.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "b9bd82ef455bc8dc4951d95d3857abb8742a207032305df96a8dc6ed6649ac79"

[[package]]
name = "unicode-ident"
diff --git a/Cargo.toml b/Cargo.toml
index 2867d65..388d4f9 100644
--- a/Cargo.toml
+++ a/Cargo.toml
@@ -10,6 +10,7 @@
strum = { version = "0.25", features = ["derive"] }
nom = "7"
itertools = "0.12"
trie-hard = "0.1"

[[bin]]
name = "aoc2023-21"
@@ -46,6 +47,10 @@
[[bin]]
name = "aoc2024-13"
path = "2024/13.rs"

[[bin]]
name = "aoc2024-19"
path = "2024/19.rs"

[profile.release]
overflow-checks = true
diff --git a/README b/README
index c266f46..f9890ae 100644
--- a/README
+++ a/README
@@ -32,8 +32,8 @@
|       16 | OCaml    | |       16 | Haskell  |
|       17 | OCaml    | |       17 | Rust     |
|       18 | OCaml    | |       18 | Haskell  |
+---------------------+ |       19 | Haskell  |
                        |       20 | Haskell  |
|       19 | Rust     | |       19 | Haskell  |
+---------------------+ |       20 | Haskell  |
                        |       21 | Rust     |
                        |       22 | Haskell  |
                        |       23 | Haskell  |
diff --git a/2024/13.rs b/2024/13.rs
index 57d472d..bb4d0c9 100755
--- a/2024/13.rs
+++ a/2024/13.rs
@@ -93,6 +93,6 @@
    Ok((s, Input { buttons, prize }))
}

fn parse_input<'a>(s: &'a str) -> IResult<&'a str, Vec<Input>> {
fn parse_input(s: &'_ str) -> IResult<&'_ str, Vec<Input>> {
    separated_list1(tag("\n"), parse_block)(s)
}
diff --git a/2024/19.rs b/2024/19.rs
new file mode 100644
index 0000000..0be9f5b 100644
--- /dev/null
+++ a/2024/19.rs
@@ -1,0 +1,76 @@
use std::{collections::HashMap, io::Read};

use anyhow::Result;
use nom::IResult;
use trie_hard::TrieHard;

fn main() -> Result<()> {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input)?;

    let (_, input) = parse_input(&input).unwrap();

    let mut possible = 0;
    let mut rearrangements = 0;

    for wanted in &input.wanted {
        let res = get_towels_for_patterns(wanted, &input.towels, &mut HashMap::new());
        possible += res.min(1);
        rearrangements += res;
    }

    eprintln!("{possible}");
    eprintln!("{rearrangements}");

    Ok(())
}

fn get_towels_for_patterns<'b>(
    wanted: &'b str,
    towels: &TrieHard<'_, &'_ str>,
    cache: &mut HashMap<&'b str, u64>,
) -> u64 {
    if wanted.is_empty() {
        return 1;
    }

    let mut possibilities = 0;

    for i in (0..wanted.len()).rev() {
        let (wanted, rest) = wanted.split_at(i + 1);

        if towels.get(wanted).is_some() {
            if let Some(cached) = cache.get(rest) {
                possibilities += cached;
                continue;
            }

            let value = get_towels_for_patterns(rest, towels, cache);
            cache.insert(rest, value);
            possibilities += value;
        }
    }

    possibilities
}

#[derive(Debug)]
pub struct Input<'a> {
    towels: TrieHard<'a, &'a str>,
    wanted: Vec<&'a str>,
}

fn parse_input(input: &str) -> IResult<&str, Input> {
    use nom::{
        bytes::complete::tag, character::complete::alpha1, combinator::map, multi::separated_list1,
        sequence::separated_pair,
    };

    let parse_towels = map(separated_list1(tag(", "), alpha1), TrieHard::from_iter);
    let parse_wanted = separated_list1(tag("\n"), alpha1);

    map(
        separated_pair(parse_towels, tag("\n\n"), parse_wanted),
        |(towels, wanted)| Input { towels, wanted },
    )(input)
}