Ok so my path to this answer was circuitous and I now hate myself a little.

P1: Ok, a repeated dfs on suffixes. that shouldn’t be too hard. (it was not hard)

P2: Ok, a repeated dfs is a little too slow for me, I wonder how I can speed it up?

forgets about memoisation, a thing that you can do to speed this sort of thing up

I guess the problem is I’m doing an O(mn) match (where m is the number of towels, n is the max towel length) when I can do O(n). I’ll build a prefix tree!

one prefix tree later

Ok that still seems to be quite slow. What am I doing wrong?

remembers that memoisation exists

Oh I just need to memoise my dp from part 1. Oops.

Anyway posting the code because I shrunk it down to like two semicolons worth of lines.

(

List<String> input = getLines();
Set<String> ts = Set.from(input.first.split(', '));
Map<String, int> dp = {};

int dpm(String s) => dp.putIfAbsent(
    s,
    () => s.isNotEmpty
        ? ts
            .where((t) => t.matchAsPrefix(s) != null)
            .map((t) => dpm(s.substring(t.length)))
            .fold(0, (a, b) => a + b)
        : 1);

void d19(bool sub) {
  print(input
      .skip(2)
      .map((s) => dpm(s))
      .map((i) => sub
          ? i
          : i > 0
              ? 1
              : 0)
      .reduce((a, b) => a + b));
}