Today, The Historians take you up to the hot springs on Gear Island! Very suspiciously, absolutely nothing goes wrong as they begin their careful search of the vast field of helixes.

Could this finally be your chance to visit the onsen next door? Only one way to find out.

Visit the website for the full story and full puzzle description.

I initially thought that I would be able to entirely solve today's problem using regular expressions. This worked for Part 1, but unfortunately, the regex library can only determine whether a pattern matches a string — it cannot return the number of ways the match can occur. Not that it’s its job anyway...

I had to implement the search function myself. It’s a simple recursive function that iterates through all towels and tries to match them to the beginning of the pattern. If a match is found, it continues recursively with the remaining pattern until the entire pattern becomes an empty string, which signifies a complete match.

Of course, this approach would never terminate as-is, it needs to be converted into a cached function. Thankfully, this is straightforward to do using a ConcurrentDictionary, which I discovered earlier this year. By utilizing the GetOrAdd method of the ConcurrentDictionary class, one can simply wrap the uncached logic inside a lambda and call it a day.

It’s very similar to Python’s cached function decorators, albeit with the caveat of having to pass an additional 'cache' argument at the end of the parameter list. But since we’re in the world of C#, we have to work with what it offers.

namespace AdventOfCode.Y2024.Day19;

using System;
using System.Collections.Generic;
using System.Linq;

using Cache = System.Collections.Concurrent.ConcurrentDictionary<string, long>;

[ProblemName("Linen Layout")]
class Solution : Solver {

    public object PartOne(string input) => MatchCounts(input).Count(c => c != 0);

    public object PartTwo(string input) => MatchCounts(input).Sum();

    IEnumerable<long> MatchCounts(string input) {
        var blocks = input.Split("\n\n");
        var towels = blocks[0].Split(", ");
        return 
            from pattern in  blocks[1].Split("\n") 
            select MatchCount(towels, pattern, new Cache());
    }

    // computes the number of ways the pattern can be build up from the towels. 
    // works recursively by matching the prefix of the pattern with each towel.
    // a full match is found when the pattern becomes empty. the cache is applied 
    // to _drammatically_ speed up execution
    long MatchCount(string[] towels, string pattern, Cache cache) =>
        cache.GetOrAdd(pattern, (pattern) => 
            pattern switch {
                "" => 1,
                _  =>  towels
                    .Where(pattern.StartsWith)
                    .Sum(towel => MatchCount(towels, pattern[towel.Length ..], cache))
            }
        );
}

Please ☆ my repo if you like it!