@EnEnCode

EnEnCode@programming.dev · 2 days ago

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)
}

EnEnCode@programming.dev · 2 days ago

Day 19 is definitely my proudest solve (though learning about Aho-Corasick dampens it a little bit 😅) with some clever ideas to both check towels more efficiently than the naïve approach while creating no Strings to avoid a bunch of heap allocation. Figuring out how to binary search without creating the target object, and merely knowledge of its properties and those of the list, meant I got to use a pretty niche library function and got my solution from 25 to 11 ms.

EnEnCode@programming.dev · 3 days ago

Congrats to everyone! Not first year, though first year of at least trying every problem. Burnout definitely got me by day 20 though, ha ha ha… There was a lot of ugly (readability a backseat to “code writing speed”), a lot of bad (don’t ask how long the test suite has to run for), but an occasional gem of good (my day 19 solution is some of the most dopamine from just writing code I’ve gotten. I’m only used to getting that much when it actually gets merged). I learned a little through the problems themselves, but I did learn a lot about writing macro_rules macros by creating a test suite generator and a benchmark generator. I also picked up some useful Git knowledge like --allow-unrelated-histories, interactive rebasing, --name-only, and using the reflog to help recover data (don’t ask what happened on day 23). This year was a personal success. Till next year!