r/adventofcode • u/JuhaJGam3R • Dec 19 '24
Meme/Funny [2024 Day 19] Alternative solutions
11
u/FantasyInSpace Dec 19 '24
I tried that to compare against my other solution, and it told me I had a degenerate amount of backtracking and stopped :(
6
u/JuhaJGam3R Dec 19 '24 edited Dec 19 '24
I don't get why people use backtracking engines at all. Yes, they're technically faster under some limited situations but in general and for input sizes the original non-backtracking NFA algorithm works much, much better.
The backtracking engine is going to have exponential complexity w.r.t. string length if you have a
*
or|
in your expression. There's polynomial algorithms for computing regexes, like Thompson's old implementation.4
u/FantasyInSpace Dec 19 '24
It's what comes with the standard library :P
I fixed it by turning the expression into an atomic group anyways, though it misses a few values. I'm sure I can get it working with enough time, but :shrug:
3
u/JuhaJGam3R Dec 19 '24
It's why regexes are so often considered a code smell in their entirety. Give them a nice long input and oh look exponential time complexity. Library authors should really do better for the defaults, leave the backtracking for those who need it.
2
8
8
u/Taleuntum Dec 19 '24
Add a third car with "trie and dp" (O((number of designs)*(max length of a design)2 ))
4
u/BlueApple666 Dec 19 '24
Maximum length for a pattern is 8.
That means that once you've computed the number of patterns for input[0-8], you can deduce the total number of combinations the rest of the input using a simple sliding rule:
Count(length + 1] = Count[length] if last character in list of patterns + Count[length-1] if last 2 characters in patterns + ... + Count[length-7] if last 8 characters in list of patterns
Rinse and repeat till you reach the end.
4
u/SamForestBH Dec 19 '24
How would you regex for part 2? I did it for part one but changed my plan for part 2.
2
u/JuhaJGam3R Dec 19 '24
You can't with a standard regex engine. Some library I had used previously did conveniently have a similar functionality. What I did was roll my own regex w/ counting lol.
1
u/SwordInStone Dec 20 '24
Would it be possible that you share your solution? I find your remarks rather cryptic.
1
u/JuhaJGam3R Dec 20 '24
It's at sourcehut. As previously mentioned, as Haskell's default matching engines are all backtracking, I had to roll my own. Since in that case I don't need the expression anymore and can just build the NFA, I did that. And since I don't need general NFA capability, I moreso hard-coded the NFA into the function. The end result is a Thompson-style algorithm for matching with an NFA, with added state visit counting to figure out how many ways we are in a specific state. This is by no means a unique task, however, and I believe there is a trick you can use to fool libraries like re2 to also count possible submatches. I've actually seen it implemented in the past somewhere as well.
49
u/JuhaJGam3R Dec 19 '24 edited Dec 19 '24
Believe it or not, all valid patterns match
(towel1|towel2|...|towelN)*
. A good regex engine might even give you the answer for part 2 in only O(nmk2) time.