Day 19! (the cuervo gold....)
disc and code
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));
}