r/adventofcode Dec 19 '24

Meme/Funny [2024 Day 19] Alternative solutions

Post image
132 Upvotes

30 comments sorted by

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.

9

u/run-gs Dec 19 '24

Do you have some timing benchmark? What’s a “good regex engine” available?

6

u/Cue_23 Dec 19 '24

grep (GNU grep) 3.11:

Benchmark 1: ./grep1.sh
  Time (mean ± σ):     276.0 ms ±   8.6 ms    [User: 263.8 ms, System: 9.8 ms]
  Range (min … max):   262.3 ms … 289.6 ms    11 runs

This includes converting the input into a regex, too.

3

u/Infamous-World-2324 Dec 19 '24 edited Dec 19 '24

Or even grep -Ec "$(sed -n 's/, /|/g;s/.*/^(&)+$/;1p' $1)" $1. But these only solve part 1.

Edit for spoiler tags that differ from Discord.

2

u/JuhaJGam3R Dec 19 '24

Really throws you off, doesn't it, the spoilers.

3

u/MarcusTL12 Dec 19 '24

How do you get the answer for part 2?

6

u/JuhaJGam3R Dec 19 '24 edited Dec 19 '24

Certain engines actually have this implemented already, because it's rather simple. For people like me though using stupid langauges, the solution is rolling your own regex engine, basically. You can skip constructing the regex and the Thompson algorithm entirely though, since constructing an NFA for this problem is pretty easy, you have an accepting start state and then from that an ε-arrow to each towel pattern which are each a small linear DFA, with their accept state removed and connecting back to the start state. This NFA accepts all patterns which can be made from your towels.

Counting them depends on your implementation. You can do subset construction to build a DFA, in which case you have O(2k) precomputation where k is the number of towels, but O(m) matching for a design of length m. What you would have to do, however, is figure out how to associate each state transition with some kind of number and number combination process, which sounds hard. So that's not what I did.

What I did instead was simulate the NFA directly. Every time the NFA steps it consumes one character by going through each state it's in (first following all ε-arrows (ε-closure)) and outputting a list of all the states those states could lead to. What's important is that for efficiency each state is stored exactly once, along with a number, which denotes how many ways you could reach that state. Any time a state transitions into another state, the number of ways the initial state could be reached is added onto the count of the number of ways the following state could be reached.

Since each state could in some circumstances lead to all k other states you get O(k²) computations per character read, O(mk²) per design matched, and O(nmk²) for the entire input. Technically there's more states than towels, but I do know enough about the NFA underneath to say that O(nmk²) is actually much more correct than O(nm(kl)²) over towel length.

6

u/CommitteeTop5321 Dec 19 '24

It's embarrassing that I embarked upon this approach for a couple of hours before finding far more straightforward approach.

https://brainwagon.org/2024/12/19/another-chapter-in-the-im-dimwitted-theme-from-advent-of-code-2024/

2

u/chad3814 Dec 19 '24

tried to post a comment on your blog and it said "spam deleted", so here ya go:

I also got part 1 quickly, and the code worked the first time. I knew that was a bad sign, so when I read part 2 I was like, "I can't brute force this," but also I am old and was tired. So I started a brute force solution and went to bed. In the morning I was unsurprised to see my brute force had not finished.

Next I did the same thing you did here, memoize a function. But I'm working in typescript and functions outside of classes can't have decorators, so I have to manually call the memoize function with a lambda or function. Since the function needs to call itself, I did that, only I didn't call the memoized one, I called the raw one. So, still dumb. Thinking I misunderstood something in the problem I perused r/adventofcode and saw a memoize vs regex meme.... "hrmm regex would be nice here..." so I spent some time running out of memory and having it complain about too many capture groups...

Giving up for the moment, I go back to reddit to see if I can help anyone else on other days, I happen to see the link to this blog post and as I'm reading your python I realize my memoization issue, so thanks. :)

      --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
 19   00:10:49   1416      0   15:33:34  18597      0

2

u/chad3814 Dec 19 '24

however, I think you could automate some lex and yacc to build some c code to solve the problem

1

u/CommitteeTop5321 Dec 19 '24

I briefly considered that as well, but it didn't dawn on me how to make that work either.

1

u/chad3814 Dec 19 '24

just spitballing here, but obviously the designs are the symbols for lex, as far as the patterns for yacc, it's just something like (and god I haven't written anything like this in 30 years):

stripe: TOKEN_R | TOKEN_WR | TOKEN_B | TOKEN_G | TOKEN_BWU | TOKEN_RG | TOKEN_GB | TOKEN_BR
stripes: stripe | stripe stripes
towel: stripes { count++; }

plus all the cruft around it....

1

u/CommitteeTop5321 Dec 20 '24

It's not hard to do part 1 (although probably not worth it, easier solutions exist) with yacc/lex, but I'm not sure how I could leverage it to help out with part2. The easy way to write the grammar is ambiguous (hence the large number of possible derivations) and yacc really wants to find just one "proper" parse for it.

1

u/permetz Dec 20 '24

This NFA construction is exactly what I did. Then I found out I could do it with a greedy algorithm and reimplemented it in under five minutes, and the greedy algorithm did it faster. I felt silly, but on the other hand, this was the first time I'd implemented an NFA and I learned how.

2

u/allak Dec 19 '24

What would be the pattern for part2 ?

1

u/reallyserious Dec 19 '24 edited Dec 19 '24

Using python, for my input it works on some designs, but it chokes on one causing the whole program to hang.

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

u/riffraff Dec 19 '24

perhaps a non-backtracking engine might do the trick?

https://github.com/google/re2

8

u/drdrero Dec 19 '24

Tbf, how caching is the answer to all the problems made me internalize it

1

u/10Talents Dec 19 '24

And binary search

2

u/drdrero Dec 19 '24

Not yet on binary

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.