Javascript

Behold an abomination!

const input = require('fs').readFileSync(0, 'utf-8').toString();
const towels = new Set(input.split(/\r?\n\r?\n/g)[0].split(', '));
const count = (p, t) => [...new Array(p.length).keys()].reduce((acc, i) => [...new Array(i + 1).keys()].forEach(j => acc[j] > 0n && t.has(p.substring(j, i + 1)) ? acc[i + 1] += acc[j] : null) ? acc : acc, [1n, ...new Array(p.length).fill(0n)])[p.length];
input.split(/\r?\n\r?\n/g)[1].split(/\r?\n/g).filter(p => p.length > 0).reduce((acc, p) => { let c = count(p, towels); acc[0] += c > 0 ? 1 : 0; acc[1] += c; return acc }, [0, 0n]).forEach((v, i) => console.log(`Part ${i+1}: ${v}`));

Python

Approach: Recursive memoized backtracking with a Trie

I get to use one of my favorite data structures here, a Trie! It helps us figure out whether a prefix of the design is a valid pattern in linear time.

I use backtracking to choose potential component patterns (using the Trie), kicking off matching the rest of the design down the stack. We can continue matching longer patterns immediately after the recursion stack unwinds.
In addition, I use global memoization to keep track of the feasibility (part 1) or the number of combinations (part 2) for designs and sub-designs. This way, work done for earlier designs can help speed up later ones too.

I ended up combining part 1 and 2 solutions into a single function because part 1 is a simpler variant of part 2 where we count all designs with the number of possible pattern combinations > 0.

::: spoiler Reading Input

import os

here = os.path.dirname(os.path.abspath(__file__))

# read input
def read_data(filename: str):
    global here

    filepath = os.path.join(here, filename)
    with open(filepath, mode="r", encoding="utf8") as f:
        return f.read()

:::

::: spoiler Trie Implementation

class Trie:
    class TrieNode:
        def __init__(self) -> None:
            self.children = {}  # connections to other TrieNode
            self.end = False  # whether this node indicates an end of a pattern

    def __init__(self) -> None:
        self.root = Trie.TrieNode()

    def add(self, pattern: str):
        node = self.root
        # add the pattern to the trie, one character at a time
        for color in pattern:
            if color not in node.children:
                node.children[color] = Trie.TrieNode()
            node = node.children[color]
        # mark the node as the end of a pattern
        node.end = True

:::

::: spoiler Solution

def soln(filename: str):
    data = read_data(filename)
    patterns, design_data = data.split("\n\n")

    # build the Trie
    trie = Trie()
    for pattern in patterns.split(", "):
        trie.add(pattern)

    designs = design_data.splitlines()

    # saves the design / sub-design -> number of component pattern combinations
    memo = {}

    def backtrack(design: str):
        nonlocal trie

        # if design is empty, we have successfully 
        #   matched the caller design / sub-design
        if design == "":
            return 1
        # use memo if available
        if design in memo:
            return memo[design]

        # start matching a new pattern from here
        node = trie.root
        # number of pattern combinations for this design
        pattern_comb_count = 0
        for i in range(len(design)):
            # if design[0 : i+1] is not a valid pattern,
            #   we are done matching characters
            if design[i] not in node.children:
                break
            # move along the pattern
            node = node.children[design[i]]
            # we reached the end of a pattern
            if node.end:
                # get the pattern combinations count for the rest of the design / sub-design
                # all of them count for this design / sub-design
                pattern_comb_count += backtrack(design[i + 1 :])

        # save the pattern combinations count for this design / sub-design
        memo[design] = pattern_comb_count
        return pattern_comb_count

    pattern_comb_counts = []
    for design in designs:
        pattern_comb_counts.append(backtrack(design))
    return pattern_comb_counts


assert sum(1 for dc in soln("sample.txt") if dc > 0) == 6
print("Part 1:", sum(1 for dc in soln("input.txt") if dc > 0))

assert sum(soln("sample.txt")) == 16
print("Part 2:", sum(soln("input.txt")))

:::

Haskell

::: spoiler solution

{-# LANGUAGE LambdaCase #-}

module Main where

import Control.Arrow
import Control.Monad.State
import Data.Char
import Data.List
import Data.Map qualified as M
import Data.Monoid
import Text.ParserCombinators.ReadP

parse = fst . last . readP_to_S ((,) <$> (patterns <* eol <* eol) <*> designs)
  where
    eol = char '\n'
    patterns = sepBy word (string ", ")
    designs = endBy word eol
    word = munch1 isLetter

part1 patterns = length . filter (valid patterns)
part2 patterns = getSum . combinations patterns

dropPrefix = drop . length

valid :: [String] -> String -> Bool
valid patterns design = go design
  where
    go "" = True
    go design = case filter (`isPrefixOf` design) patterns of
        [] -> False
        l -> any (go . (`dropPrefix` design)) l

combinations :: [String] -> [String] -> Sum Int
combinations patterns designs = evalState (fmap mconcat . mapM go $ designs) mempty
  where
    go "" = return $ Sum 1
    go design =
        gets (M.lookup design) >>= \case
            Just c -> return c
            Nothing -> case filter (`isPrefixOf` design) patterns of
                [] -> return $ Sum 0
                l -> do
                    res <- mconcat <$> mapM (go . (`dropPrefix` design)) l
                    modify (M.insert design res)
                    return res

main = getContents >>= print . (uncurry part1 &&& uncurry part2) . parse

:::

Haskell

My naive solution was taking ages until I tried matching from right to left instead :3

In the end the cache required for part two solved the problem more effectively.

import Control.Arrow
import Control.Monad.State
import Data.List
import Data.List.Split
import Data.Map (Map)
import Data.Map qualified as Map

arrangements :: [String] -> String -> Int
arrangements atoms = (`evalState` Map.empty) . go
  where
    go "" = return 1
    go molecule =
      let computed = do
            c <- sum <$> mapM (\atom -> maybe (return 0) go $ stripPrefix atom molecule) atoms
            modify (Map.insert molecule c)
            return c
       in gets (Map.!? molecule) >>= maybe computed return

main = do
  (atoms, molecules) <- (lines >>> (splitOn ", " . head &&& drop 2)) <$> readFile "input19"
  let result = map (arrangements atoms) molecules
  print . length $ filter (> 0) result
  print . sum $ result

Rust

I figured that Part 2 would want something to do with unique paths, so I tried to generate all paths in Part 1, which took too long. So I then decided to go with dynamic programming. In Part 1, I stored a cache of whether a given state can lead to the solution. In Part 2, I updated it to store how many options are possible from a given state.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day19.rs?ref_type=heads

::: spoiler The Code

use std::collections::HashMap;

use crate::solver::DaySolver;

fn parse_input(input: String) -> (Vec<String>, Vec<String>) {
    let towels = input.lines().take(1).collect::<String>().split(", ").map(|s| s.to_string()).collect();

    let designs = input.lines().skip(2).map(|s| s.to_string()).collect();

    (towels, designs)
}

fn how_many_ways(cache: &mut HashMap<String, usize>, towels: &[String], current: String, target: &str) -> usize {
    if let Some(ways) = cache.get(&current) {
        *ways
    } else if current == target {
        cache.insert(current.clone(), 1);
        1
    } else if !target.starts_with(&current) {
        cache.insert(current.clone(), 0);
        0
    } else {
        let ways = towels.iter()
            .map(|t| format!("{}{}", current, t))
            .map(|next| how_many_ways(cache, towels, next, target))
            .sum();
        cache.insert(current, ways);
        ways
    }
}

pub struct Day19Solver;

impl DaySolver for Day19Solver {
    fn part1(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .filter(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), d) > 0)
            .count()
            .to_string()
    }

    fn part2(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .map(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), &d))
            .sum::<usize>()
            .to_string()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("6", solver.part1(input.to_string()));
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("16", solver.part2(input.to_string()));
    }
}

:::

Dart

Thanks to this useful post for reminding me that dynamic programming exists (and for linking to a source to help me remember how it works as it always makes my head spin :-) I guessed that part 2 would require counting solutions, so that helped too.

Solves live data in about 40ms.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

int countTarget(String target, Set<String> towels) {
  int n = target.length;
  List<int> ret = List.filled(n + 1, 0)..[0] = 1;

  for (int e in 1.to(n + 1)) {
    for (int s in 0.to(e)) {
      if (towels.contains(target.substring(s, e))) ret[e] += ret[s];
    }
  }
  return ret[n];
}

List<int> allCounts(List<String> lines) {
  var towels = lines.first.split(', ').toSet();
  return lines.skip(2).map((p) => countTarget(p, towels)).toList();
}

part1(List<String> lines) => allCounts(lines).where((e) => e > 0).length;
part2(List<String> lines) => allCounts(lines).sum;

Haskell

I had several strategy switches from brute-force to pathfinding (when doing part1 input instead of example) because It simply wouldn't finish. My solution only found the first path to the design, which is why I rewrote to only count how many towels there are for each prefix I have already built. Do that until there is either only one entry with the total combinations count or no entry and it's impossible to build the design.

I like the final solution, its small (unlike my other solutions) and runs fast.

::: spoiler 🚀

import Control.Arrow

import Data.Map (Map)

import qualified Data.List as List
import qualified Data.Map as Map

parse :: String -> ([String], [String])
parse = lines . init
        >>> (map (takeWhile (/= ',')) . words . head &&& drop 2)

countDesignPaths :: [String] -> String -> Map Int Int -> Int
countDesignPaths ts d es
        | Map.null es    = 0
        | ml == length d = mc
        | otherwise = countDesignPaths ts d es''
        where
                ((ml, mc), es') = Map.deleteFindMin es
                ns = List.filter (flip List.isPrefixOf (List.drop ml d))
                        >>> List.map length
                        >>> List.map (ml +)
                        $ ts
                es'' = List.foldl (\ m l' -> Map.insertWith (+) l' mc m) es'
                        $ ns
solve (ts, ds) = List.map (flip (countDesignPaths ts) (Map.singleton 0 1))
        >>> (List.length . List.filter (/= 0) &&& List.sum)
        $ ds

main = getContents
        >>= print
        . solve
        . parse

:::

C

Interestingly part 1 already defied a naive approach. It was fun thinking of a way to memoize without hash tables.

:::spoiler Code

#include "common.h"

static char *pats[480];
static int lens[480];
int np;

/* memoized for 's' by mem[off], 0 = unknown, >0 = value+1 */
static int64_t
recur(char *s, int off, int64_t *mem)
{
	int64_t acc=0;
	int i;

	if (!s[off]) return 1;
	if (mem[off]) return mem[off]-1;

	for (i=0; i<np; i++)
		if (!strncmp(s+off, pats[i], lens[i]))
			acc += recur(s, off+lens[i], mem);

	mem[off] = acc+1;
	return acc;
}

int
main(int argc, char **argv)
{
	static char patbuf[3200], design[64];
	int64_t p1=0,p2=0, mem[64], n;
	char *rest, *lf;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	rest = fgets(patbuf, sizeof(patbuf), stdin);

	for (; (pats[np] = strsep(&rest, ",")); np++) {
		while (isspace(pats[np][0]))
			pats[np]++;	/* skip spaces */
		if ((lf = strchr(pats[np], '\n')))
			*lf = '\0';	/* trim trailing \n */
		lens[np] = strlen(pats[np]);
		assert(np+1 < (int)LEN(pats));
	}

	while (scanf(" %63s", design) == 1) {
		memset(mem, 0, sizeof(mem));
		n = recur(design, 0, mem);
		p1 += n >0;
		p2 += n;
	}

	printf("19: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}

:::

https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day19.c

Zee

Also a port to my cursed Dutch dialect of C, Zee:

:::spoiler Code

#ingesloten "zee.kop"
#ingesloten "algemeen.kop"

besloten letterverwijzing patronen[480];
besloten getal lengtes[480];
getal patroonsom;

besloten zeer groot getal
afdaling(
    letterverwijzing tekst,
    getal startpositie,
    zeergrootgetalreeksverwijzing onthouden)
{
	zeer groot getal deelsom=0;
	getal sortering, teller;

	tenzij (tekst[startpositie])
		lever 1;
	mits (onthouden[startpositie])
		lever onthouden[startpositie]-1;

	voor (teller=0; teller < patroonsom; teller++) {
		sortering = tekstdeelvergelijking(
		    tekst + startpositie,
		    patronen[teller],
		    lengtes[teller]);

		mits (sortering == 0) {
			deelsom += afdaling(
			    tekst,
			    startpositie + lengtes[teller],
			    onthouden);
		}
	}

	onthouden[startpositie] = deelsom+1;
	lever deelsom;
}

getal
aanvang(
    getal parametersom,
    letterverwijzingsreeksverwijzing parameters)
{
	blijvende letter patroonruimte[3200];
	blijvende letter ontwerp[64];
	zeer groot getal deel1=0, aantal;
	zeer groot getal deel2=0, onthouden[64];
	letterverwijzing rest;
	letterverwijzing regeleinde;

	mits (parametersom > 1)
		VERWERP(heropen(parameters[1], "r", standaardinvoer));

	rest = geefregel(patroonruimte, grootte(patroonruimte),
	    standaardinvoer);

	voor (; ; patroonsom++) {
		verzeker(patroonsom+1 < (getal)LENGTE(patronen));
		patronen[patroonsom] = tekstsplitsing(naar rest, ",");
		mits (patronen[patroonsom] == NIETS)
			klaar;

		zolang (iswitruimte(patronen[patroonsom][0]))
			patronen[patroonsom]++;
		mits ((regeleinde = zoekletter(patronen[patroonsom], '\n')))
			volg regeleinde = '\0';

		lengtes[patroonsom] = tekstlengte(patronen[patroonsom]);
	}

	zolang (invorm(" %63s", ontwerp) == 1) {
		overschrijf(onthouden, 0, grootte(onthouden));
		aantal = afdaling(ontwerp, 0, onthouden);
		deel1 += aantal >0;
		deel2 += aantal;
	}

	uitvorm("19: %"GEEFZGG" %"GEEFZGG"\n", deel1, deel2);
	lever 0;
}

:::

https://codeberg.org/sjmulder/aoc/src/

C#

Part 2 was pretty much the same as Part 2 except we can't short-circuit when we find the first match. So, implement a cache of each sub-pattern and the number of ways to form it from the towels, and things get much faster.

using System.Collections.Immutable;
using System.Diagnostics;
using Common;

namespace Day19;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = ReceiveInput("sample.txt");
        var programInput = ReceiveInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input input)
    {
        return input.Patterns
            .Select(p => AnyTowelMatches(p, input.Towels) ? 1 : 0)
            .Sum();
    }

    static object Part2(Input input)
    {
        var matchCache = new Dictionary<string, long>();
        return input.Patterns
            .Select(p => CountTowelMatches(p, input.Towels, matchCache))
            .Sum();
    }

    private static bool AnyTowelMatches(
        string pattern,
        ImmutableArray<string> towels)
    {
        return towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t =>
                !pattern.StartsWith(t) ? false :
                (pattern.Length == t.Length) ? true :
                AnyTowelMatches(pattern.Substring(t.Length), towels))
            .Any(r => r);
    }

    private static long CountTowelMatches(
        string pattern,
        ImmutableArray<string> towels,
        Dictionary<string, long> matchCache)
    {
        if (matchCache.TryGetValue(pattern, out var count)) return count;

        count = towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t => 
                !pattern.StartsWith(t) ? 0 :
                (pattern.Length == t.Length) ? 1 :
                CountTowelMatches(pattern.Substring(t.Length), towels, matchCache))
            .Sum();

        matchCache[pattern] = count;
        return count;
    }

    static Input ReceiveInput(string file)
    {
        using var reader = new StreamReader(file);

        var towels = reader.ReadLine()!.SplitAndTrim(',').ToImmutableArray();
        var patterns = new List<string>();
        reader.ReadLine();
        var line = reader.ReadLine();
        while (line is not null)
        {
            patterns.Add(line);
            line = reader.ReadLine();
        }

        return new Input()
        {
            Towels = towels,
            Patterns = [..patterns],
        };
    }

    public class Input
    {
        public required ImmutableArray<string> Towels { get; init; }
        public required ImmutableArray<string> Patterns { get; init; }
    }
}

Python3

Solver uses trie just like the other python solve here, I try to not look at solve threads until after it is solved. yet, I somehow got a solve that only takes ~7 ms. previously I would rebuild the trie every time and made it take ~55 ms.

:::spoiler Code

from collections import deque

def profiler(method):
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret

    return wrapper_method

def build_aho_corasick(towels):
    # Each node: edges dict, failure link, output (which towels end here)
    trie = [{'fail': 0, 'out': []}]
    
    # Build trie of towels
    for index, word in enumerate(towels):
        node = 0
        for char in word:
            if char not in trie[node]:
                trie[node][char] = len(trie)
                trie.append({'fail': 0, 'out': []})
            node = trie[node][char]
        trie[node]['out'].append(len(word))  # store length of matched towel

    # Build fail links (BFS)
    queue = deque()
    # Initialize depth-1 fail links
    for c in trie[0]:
        if c not in ('fail', 'out'):
            nxt = trie[0][c]
            trie[nxt]['fail'] = 0
            queue.append(nxt)

    # BFS build deeper fail links
    while queue:
        r = queue.popleft()
        for c in trie[r]:
            if c in ('fail', 'out'):
                continue
            nxt = trie[r][c]
            queue.append(nxt)
            f = trie[r]['fail']
            while f and c not in trie[f]:
                f = trie[f]['fail']
            trie[nxt]['fail'] = trie[f][c] if c in trie[f] else 0
            trie[nxt]['out'] += trie[trie[nxt]['fail']]['out']
    return trie

def count_possible_designs_aho(trie, design):
    n = len(design)
    dp = [0] * (n + 1)
    dp[0] = 1

    # State in the trie automaton
    state = 0

    for i, char in enumerate(design, 1):
        # Advance in trie
        while state and char not in trie[state]:
            state = trie[state]['fail']
        if char in trie[state]:
            state = trie[state][char]
        else:
            state = 0
        
        # For every towel match that ends here:
        for length_matched in trie[state]['out']:
            dp[i] += dp[i - length_matched]
    
    return dp[n]

@profiler
def main(input_data):
    towels,desired_patterns = ( sorted(x.split(), key=len, reverse=True) for x in input_data.replace(',', ' ').split('\n\n') )
    part1 = 0
    part2 = 0
    
    # Build Aho-Corasick structure
    trie = build_aho_corasick(towels)
    
    for pattern in desired_patterns:
        count = count_possible_designs_aho(trie, pattern)
        if count:
            part1 += 1
            part2 += count
    
    return part1,part2

if __name__ == "__main__":
    with open('input', 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = main(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])

:::

Rust

Pretty similar to the other rust answer. This definitely requires ::: spoiler spoiler memoization ::: of some form, but when done right, is very performant. 122ms for both.

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    fn count_solutions(
        design: &str,
        patterns: &[&str],
        seen_designs: &mut HashMap<String, i64>,
    ) -> i64 {
        if design.is_empty() {
            return 1;
        }
        if let Some(s) = seen_designs.get(design) {
            return *s;
        }
        let mut count = 0;
        for pattern in patterns {
            if design.starts_with(pattern) {
                count += count_solutions(&design[pattern.len()..], patterns, seen_designs);
            }
        }
        seen_designs.insert(design.to_string(), count);
        count
    }

    #[test]
    fn day19_both_test() {
        let input = std::fs::read_to_string("src/input/day_19.txt").unwrap();
        let parts = input.split_once("\n\n").unwrap();
        let patterns = parts.0.split(", ").collect::<Vec<&str>>();
        let designs = parts.1.split('\n').collect::<Vec<&str>>();

        let mut count = 0;
        let mut total = 0;
        let mut seen_designs = HashMap::new();
        for design in designs {
            let shortlist = patterns
                .iter()
                .filter_map(|p| {
                    if design.contains(p) {
                        return Some(*p);
                    }
                    None
                })
                .collect::<Vec<&str>>();
            let sol_count = count_solutions(design, &shortlist, &mut seen_designs);
            total += sol_count;
            count += (sol_count != 0) as usize;
        }
        println!("{}", count);
        println!("{}", total);
    }
}

Haskell

Runs in 115 ms. Today's pretty straight forward. Memoization feels like magic sometimes!

::: spoiler Code

import Control.Monad.Memo
import Data.List

splitX :: Eq a => [a] -> [a] -> [[a]]
splitX xs = go
    where
        go [] = [[]]
        go ys@(y : ys') = case stripPrefix xs ys of
            Just ys'' -> [] : go ys''
            Nothing   -> let (zs : zss) = go ys' in (y : zs) : zss

parse :: String -> ([String], [String])
parse s =
    let (patterns : _ : designs) = lines s
    in  (splitX ", " patterns, takeWhile (not . null) designs)

countPatterns :: (Eq a, Ord a) => [[a]] -> [a] -> Memo [a] Int Int
countPatterns yss = go
    where
        go [] = return 1
        go xs = sum <$> sequence
            [memo go xs' | Just xs' <- map (\ys -> stripPrefix ys xs) yss]

main :: IO ()
main = do
    (patterns, designs) <- parse <$> getContents
    let ns = startEvalMemo $ mapM (countPatterns patterns) designs
    print $ length $ filter (> 0) ns
    print $ sum ns

:::

Rust

First part is solved by making a regex of the available towels, like ^(r|wr|bg|bwu|rb|gb|br)*$ for the example. If a design matches it, then it can be made. This didn't work for the second part, which is done using recursion and memoization instead. Again, it was quite surprising to see such a high solution number. 32 bits were not enough (thanks, debug mode overflow detection).

::: spoiler Solution

use regex::Regex;
use rustc_hash::FxHashMap;

fn parse(input: &str) -> (Vec<&str>, Vec<&str>) {
    let (towels, designs) = input.split_once("\n\n").unwrap();
    (towels.split(", ").collect(), designs.lines().collect())
}

fn part1(input: String) {
    let (towels, designs) = parse(&input);
    let pat = format!("^({})*$", towels.join("|"));
    let re = Regex::new(&pat).unwrap();
    let count = designs.iter().filter(|d| re.is_match(d)).count();
    println!("{count}");
}

fn n_arrangements<'a>(
    design: &'a str,
    towels: &[&str],
    cache: &mut FxHashMap<&'a str, u64>,
) -> u64 {
    if design.is_empty() {
        return 1;
    }
    if let Some(n) = cache.get(design) {
        return *n;
    }
    let n = towels
        .iter()
        .filter(|t| design.starts_with(*t))
        .map(|t| n_arrangements(&design[t.len()..], towels, cache))
        .sum();
    cache.insert(design, n);
    n
}

fn part2(input: String) {
    let (towels, designs) = parse(&input);
    let sum: u64 = designs
        .iter()
        .map(|d| n_arrangements(d, &towels, &mut FxHashMap::default()))
        .sum();
    println!("{sum}");
}

util::aoc_main!();

:::

Also on github

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. ::: spoiler 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)
}

:::

C#

I had an error in the escape clause of the recursion that stumped me for a bit - wasn't counting the last towel!

This might be the first time I have ever had to use a long/ulong in 9 years of C# dev! (corp dev is obviously boring)

::: spoiler spoiler using System.Collections.Concurrent;

namespace AoC2024.day_19;

public class Day19 { private ConcurrentDictionary<string,ulong> _cachedPossibilities = new ConcurrentDictionary<string, ulong>();

public void GoPart1()
{
    var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
    var availableTowels = GetAvailableTowels(inputText);
    var requiredPatterns = GetTargetPatterns(inputText);
    int reachablePatterns = 0;
    
    foreach (var targetPattern in requiredPatterns)
    {
        var result = DoTowelsMatch(targetPattern, availableTowels);

        if (result.Item1)
        {
            reachablePatterns++;
            Console.WriteLine($"Target pattern {targetPattern} can be reached with the following towels: {result.Item2.Aggregate("",(s, s1) => $"{s},{s1}")}");
        }
        else
        {
            Console.WriteLine($"Target pattern {targetPattern} can't be reached");
        }
    }
    
    Console.WriteLine($"reachable patterns: {reachablePatterns}");
}

public void GoPart2()
{
    var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
    //var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\testInput.txt");
    var availableTowels = GetAvailableTowels(inputText);
    var requiredPatterns = GetTargetPatterns(inputText);
    ulong patternCount = 0;
    
    var tasks = new List<Task<ulong>>();
    
   // requiredPatterns = requiredPatterns.Take(5).ToList();
    
    
    foreach (var targetPattern in requiredPatterns)
    {
        var task = new Task<ulong>(() =>
        {
            Console.WriteLine(targetPattern);
            ulong taskPatternCount = 0;
            var result = DoTowelsMatch2(targetPattern, availableTowels);

            if (result.Item1)
            {
                taskPatternCount = result.Item2;
                Console.WriteLine($"Target pattern {targetPattern} can be reached with {result.Item2} permutations");
            }
            else
            {
                Console.WriteLine($"Target pattern {targetPattern} can't be reached");
            }

            return taskPatternCount;
        });
        
        task.Start();
        tasks.Add(task);
    }

    Task.WaitAll(tasks);

    tasks.ForEach(task => patternCount += task.Result);
    Console.WriteLine($"{tasks.Count(task => task.Result > 0)} of the patterns were achieved");
    
    Console.WriteLine($"reachable patterns: {patternCount}");
}

private (bool,ulong) DoTowelsMatch2(string targetPattern, List<string> towelPatterns)
{
    ulong possiblePatternCount = 0;
   
    if (_cachedPossibilities.ContainsKey(targetPattern))
    {
        _cachedPossibilities.TryGetValue(targetPattern, out possiblePatternCount);
        return (possiblePatternCount > 0,possiblePatternCount);
    }
    
    foreach (var towelPattern in towelPatterns)
    {
        if (targetPattern.StartsWith(towelPattern))
        {
            var newTargetPattern = targetPattern.Substring(towelPattern.Length);

            if (string.IsNullOrEmpty(newTargetPattern))
            {
                possiblePatternCount++;
                continue;
            }
            
            var doTowelsMatchResult = DoTowelsMatch2(newTargetPattern, towelPatterns);
            if (doTowelsMatchResult.Item1)
            {
                possiblePatternCount += doTowelsMatchResult.Item2;
            }
        }
    }

    _cachedPossibilities.TryAdd(targetPattern, possiblePatternCount);
    
    return (possiblePatternCount>0,possiblePatternCount);
}

private (bool,List<string>?) DoTowelsMatch(string targetPattern, List<string> towelPatterns)
{
    foreach (var towelPattern in towelPatterns)
    {
        if (targetPattern.StartsWith(towelPattern))
        {
            var newTargetPattern = targetPattern.Substring(towelPattern.Length);

            if (string.IsNullOrEmpty(newTargetPattern))
            {
                return (true, new List<string>(){ towelPattern });
            }
            
            var doTowelsMatchResult = DoTowelsMatch(newTargetPattern, towelPatterns);
            if (doTowelsMatchResult.Item1)
            {
                doTowelsMatchResult.Item2.Insert(0, towelPattern);
                return (true, doTowelsMatchResult.Item2);
            }
        }
    }

    return (false,null);
}

private List<string> GetAvailableTowels(string input)
{
    return input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).First().Split(',', StringSplitOptions.RemoveEmptyEntries).Select(s => s.Trim()).ToList();
}

private List<string> GetTargetPatterns(string input)
{
    var lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).ToList();
    lines.RemoveAt(0);
    return lines.Select(s => s.Trim()).ToList();
}

} :::