From 7049e491a67e4401d4631a2de6a1069533c123ad Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
Date: Fri, 27 Dec 2024 20:49:46 +0700
Subject: [PATCH] Add 2024 day 19

---
 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)
+}
--
rgit 0.1.5