Advent of Code 2020 Day 19

I took yesterday off, and still needed to finish part 2 of day 18 today, so I’ve got my work cut out for me to get caught up today.

Part 1

I should be able to just turn the rules into a regex.

1. Read the rules into a dictionary.
2. Starting with rules["0"], recursively expand rules, using regexes to match:

• "(\w)" -> character
• ([\d ]+) \| ([\d ]+)" -> ((expand(1))|(expand(2)))
• (\d+ ?)+ -> expand(x) for each x and join

3. Anchor the expanded regex and compile.

Part 2

8: 42 | 42 8
11: 42 31 | 42 11 31

I wasn’t sure what to expect for part 2, but now the regex solution will definitely not work without some significant changes. I’ll start with the suggestion, and look at rules 42 and 31 to see what they’re doing:

julia> r["42"]
"97 132 | 65 26"

julia> expand(r,"42")
"((((a((b((((a((((a)|(b))((a)|(b))b)|(bba)))|(b((((a((a)|(b)))|(ba))b)|(((ab)|(b...

julia> r["31"]
"38 26 | 77 132"

julia> expand(r,"31")
"((((b((b((((((((((a)|(b))b)|(aa))b)|(((ab)|(bb))a))a)|(((baa)|(a((ba)|(((a)|(b)...

Well the expansions don’t help much, but I see from the rules that each of them ends in a fixed character, although that doesn’t immediately seem very helpful.

julia> r["132"]
"\"a\""

julia> r["26"]
"\"b\""

Let’s see where 8 and 11 are used:

0: 8 11

Ah, well that helps a bit. Maybe I can manually expand the recusive rules out to make several versions to test against:

0: 8 11 
0: 42 8 11
0: 8 42 11 31
0: 42 8 42 11 31

But how far will this recursion need to go? I suppose I could keep going until I get the right answer. A couple iterations get through the test case, but then regex engine blows up on the problem, so I think I need to back up and look at the rules a bit more.

to be continued…