Advent of Code - 2024 - Day 19

var input = await File.ReadAllLinesAsync("input.txt");
var towels = input[0].Split(", ").ToArray();
var designs = input[2..];
var cache = new Dictionary<string, long>();

var results = designs.Select(Check).ToArray();
Console.WriteLine($"Part 1: {results.Count(r => r > 0)}");
Console.WriteLine($"Part 2: {results.Sum()}");

return;

long Check(string design)
{
    if (cache.TryGetValue(design, out var cached))
    {
        return cached;
    }

    var result = towels.Contains(design) ? 1L : 0L;
    result += towels.Where(design.StartsWith).Sum(t => Check(design[t.Length..]));
    cache[design] = result;

    return result;
}