Advent Of Code @programming.dev CameronDev @programming.dev 1 mo. ago

👻 - 2024 DAY 19 SOLUTIONS -👻

Day 19 - Linen Layout

Megathread guidelines

Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
Where do I participate?: https://adventofcode.com/
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

You're viewing a single thread.

34 comments

Rust

Definitely not Aho–Corasick cool or genius, but does get ~11ms on both parts. Gains over the other Rust solves are partly a less naïve approach to towel checking and partly getting it to work with 0 String allocations, which involves both an instructive lifetime annotation and the clever use of a niche standard library function.

Code

pub fn day19(input: &str) -> (u64, u64) {
    fn recur_helper<'a>(pat: &'a str, towels: &[&str], map: &mut HashMap<&'a str, u64>) -> u64 {
        let mut hits = 0;
        let mut towel_subset = towels;
        for l in 1..=pat.len() {
            let test_pat = &pat[0..l];
            match towel_subset.binary_search(&test_pat) {
                Ok(idx) => {
                    if pat[l..].is_empty() {
                        return hits + 1;
                    } else if let Some(&v) = map.get(&pat[l..]) {
                        hits += v;
                    } else {
                        let v = recur_helper(&pat[l..], towels, map);
                        map.insert(&pat[l..], v);
                        hits += v;
                    }

                    towel_subset = &towel_subset[idx..];
                    let end = towel_subset.partition_point(|&x| x.starts_with(test_pat));
                    towel_subset = &towel_subset[..end];
                    if towel_subset.is_empty() {
                        return hits;
                    }
                }
                Err(idx) => {
                    towel_subset = &towel_subset[idx..];
                    let end = towel_subset.partition_point(|&x| x.starts_with(test_pat));
                    towel_subset = &towel_subset[..end];
                    if towel_subset.is_empty() {
                        return hits;
                    }
                }
            }
        }
        hits
    }
    let mut part1 = 0;
    let mut part2 = 0;
    let mut lines = input.lines();
    let mut towels = lines.next().unwrap().split(", ").collect::<Vec<_>>();
    towels.sort();
    let mut map = HashMap::new();
    for pat in lines.skip(1) {
        let tmp = recur_helper(pat, &towels, &mut map);
        part2 += tmp;
        if tmp > 0 {
            part1 += 1;
        }
    }
    (part1, part2)
}

nice job! now do it without recursion. something I always attempt to shy away from as I think it is dirty to do, makes me feel like it is the "lazy man's" loop.

Aho-Corasick is definitely meant for this kind of challenge that requires finding all occurrences of multiple patterns, something worth reading up on! If you are someone who builds up a util library for future AoC or other projects then that would likely come in to use sometimes.

Another algorithm that is specific to finding one pattern is the Boyer-Moore algorithm. something to mull over: https://softwareengineering.stackexchange.com/a/183757

have to remember we are all discovering new interesting ways to solve similar or same challenges. I am still learning lots, hope to see you around here and next year!

You've viewed 34 comments.