Day 19 solution thread
# advent-of-code
a
Day 19 solution thread
I considered converting the rules to a single Regex but I'm glad I opted to use recursion as otherwise Part 2 would have been a nightmare. I was lucky that my solution to Part 1 also solved Part 2 with zero modifications.
it wasn't a nightmare once I found a little trick
it does rely on assuming that every rule matches at least one character, but that is true in our input, and I could remove that assumption
👏🏻 1
n
I dunno, it was weird, the second part said now that it could be infinite, that was important, for me that no made difference
The big difference for me was that rules could be different lengths
I started doing the general implementation for part1, saw the shortcut in the data and got lazy, and then of course had to backtrack for part2 🙂
Not ultra efficient but reasonably elegant and it still ran in like a second or so
k
Initially I went with the regex approach, had to change for part 2. Tried changing rule
8
with
42 +
but then rule
11
recursion had to be limited in some way, which was not neat. Took inspiration from @andyb 😅
👍 1
n
I'm just curious, isn't the recursion limited by just eating more and more of the string as you go?
I didn't undesrtand how they talked about that in part2
But oviously it seems like a relevant hint for some people's approaches
e
one of the approaches to part 1 is just to expand all the rules into one big set, and then test each message for membership
that approach is… less good for part 2
n
Yeah I just realized that a moment ago
It's weird how I didn't even consider it
I always thought of it as a graph
I thought about collapsing/bubbling up the graph but was too lazy
a
I have tidied up my recursive solution to use a Sealed class representing a Rule (either a character or a list of sub-rules). Also used a pointer to current position in the message to minimise the String manipulation. It now takes ~100ms on my old laptop to solve Part 2.
e
I personally found it nicer to use
Copy code
sealed class Item {
    data class Literal(string: String) : Item()
    data class Reference(key: Int) : Item()
}
// typealias Rule = Pair<Int, List<List<Item>>>
so there's only one form of rule, and I can use
0: "a" 1 | 2 "b"
in testing
n
I did the same thing almost
Except my Rule didn't include the Int, I had a Map<Int, Rule>
data class Rule(val subrules: List<List<RuleSegment>>
l
I went for the regex approach. It sucks that backreferences are limited to the match (AFAIK). If you could extract the length of the match, part 2 would be a little easier. I iterated for rule 11 for 1 repetition to
longestMessageLength
and summed.
b
I went with a custom parser initially but kept having issues
so I went the regexp route
I also just made an optimized version that does part 2 in 36ms