Learning Resources>Coding Challenges

Avent of Code 2020 - Day 19

#2020#advent-of-code
Papey

Papey

Avent of Code 2020 - Day 19

This topic is about Day 19 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

15 comments
#2020#advent-of-code
11 1176 15

Most Liked

Papey

Papey

And for part 2, regex go brrrrrrrrrrrrrrrrrrrrrrrrrr brrrrrrrrrrr

The key thing is the recursive regex :

  def gen_matcher(rules, "11", true) do
    Enum.join(
      [
        "(?'recurse'(#{gen_matcher(rules, "42", true)})",
        "(?&recurse)?",
        "(#{gen_matcher(rules, "31", true)})",
        ")"
      ],
      ""
    )
  end

First, you define a named group with a name (recurse here), after that you trigger the recursion with (?&recurse).

I used Enum.join instead of string litterals because it was unreadable without it.

regex

~r/^((((a(((((ab|bb)b|(ab)a)a|(((a|b)(a|b))a|(b(a|b)|aa)b)b)b|((a(ba|bb)|b((a|b)(a|b)))a|(a(ba|aa)|b((a|b)(a|b)))b)a)b|(b((b(ba|bb)|a(ab))b|(b(b(a|b)|aa)|a(ab))a)|a(b(b((a|b)(a|b))|a(b(a|b)|aa))|a((aa)b|(ba|aa)a)))a)|b((b(b(b(aa)|a(ba))|a(b(ab|bb)|a(bb|aa)))|a(((bb)a|(b(a|b)|aa)b)b|(b(b(a|b)|aa)|a(ba|bb))a))a|(a(((ba|aa)b|(ab)a)b|((aa)b|(ab|bb)a)a)|b(b((ab|ba)a|(ba|bb)b)|a((ba|aa)a|(ba|bb)b)))b))a|((((((ba|aa)b|(ab)a)a|(b(bb|aa)|a((a|b)(a|b)))b)b|(a((ba|aa)a|(ba|a(a|b))b)|b((bb|aa)b|(ba)a))a)a|(a(((a(a|b)|bb)a|((a|b)(a|b))b)a|(a(aa)|b(ba|aa))b)|b(a(a(ba))|b(a(ba|aa)|b(b(a|b)|aa))))b)a|(((((ba|bb)b|(bb|aa)a)a|(b(ab)|a(ab|bb))b)b|(a((aa|ab)b|(ab|bb)a)|b((a|b)(a(a|b)|bb)))a)a|(a(((ba)a)b|((ba)a|(bb)b)a)|b(((bb|aa)b|(ba)a)a|(b(ab)|a(b(a|b)|aa))b))b)b)b))+(?‘recurse’(((a(((((ab|bb)b|(ab)a)a|(((a|b)(a|b))a|(b(a|b)|aa)b)b)b|((a(ba|bb)|b((a|b)(a|b)))a|(a(ba|aa)|b((a|b)(a|b)))b)a)b|(b((b(ba|bb)|a(ab))b|(b(b(a|b)|aa)|a(ab))a)|a(b(b((a|b)(a|b))|a(b(a|b)|aa))|a((aa)b|(ba|aa)a)))a)|b((b(b(b(aa)|a(ba))|a(b(ab|bb)|a(bb|aa)))|a(((bb)a|(b(a|b)|aa)b)b|(b(b(a|b)|aa)|a(ba|bb))a))a|(a(((ba|aa)b|(ab)a)b|((aa)b|(ab|bb)a)a)|b(b((ab|ba)a|(ba|bb)b)|a((ba|aa)a|(ba|bb)b)))b))a|((((((ba|aa)b|(ab)a)a|(b(bb|aa)|a((a|b)(a|b)))b)b|(a((ba|aa)a|(ba|a(a|b))b)|b((bb|aa)b|(ba)a))a)a|(a(((a(a|b)|bb)a|((a|b)(a|b))b)a|(a(aa)|b(ba|aa))b)|b(a(a(ba))|b(a(ba|aa)|b(b(a|b)|aa))))b)a|(((((ba|bb)b|(bb|aa)a)a|(b(ab)|a(ab|bb))b)b|(a((aa|ab)b|(ab|bb)a)|b((a|b)(a(a|b)|bb)))a)a|(a(((ba)a)b|((ba)a|(bb)b)a)|b(((bb|aa)b|(ba)a)a|(b(ab)|a(b(a|b)|aa))b))b)b)b))(?&recurse)?((b(a(b((b(a(bb)|b(ab|bb))|a((ab|ba)a|(ba|a(a|b))b))a|((a(aa|ab)|b(ab))b|(((a|b)(a|b))b|(b(a|b)|aa)a)a)b)|a((((a(a|b)|bb)b|(aa|ab)a)a|(a(ab|ba)|b(ba|bb))b)b|(((aa|ab)a|(b(a|b)|aa)b)a|(a(aa|ab)|b(ba|bb))b)a))|b(a((((aa|ab)b|(ab|bb)a)b|(b(ba|aa)|a(ab|ba))a)a|(((bb)a|(ab|ba)b)b|(b(b(a|b)|aa)|a(ba|bb))a)b)|b((a((a(a|b)|bb)(a|b))|b(b(ba|a(a|b))|a(ba)))a|(b(b(ab|bb))|a(b(b(a|b)|aa)|a(a(a|b)|bb)))b)))|a(b(b((a(b(ba|aa)|a(ba|bb)))a|(b(a(aa|ab)|b(ba|bb))|a(b(a(a|b)|bb)|a(bb|aa)))b)|a(a(((ba|aa)b|(ab)a)b|((ab)b|(aa|ab)a)a)|b(b(b(a(a|b)|bb)|a(bb|aa))|a((b(a|b)|aa)a|(ab|bb)b))))|a(b((((ab)a|((a|b)(a|b))b)b|(a(bb|aa)|b(bb))a)b|(a(a(ba))|b(b(ab|bb)))a)|a(a(((ba|bb)a|(aa|ab)b)a|(a(ab|bb)|b(bb|aa))b)|b(a(b(b(a|b)|aa)|a(ba))|b(b(a(a|b)|bb)|a(b(a|b)|aa))))))))))$/

3
Post #6
Hallski

Hallski

I parsed the rules into a Map and split each message into lists. After that I traversed left to right and branched on rules that have multiple branches.

My solution

It works for both part 1 and 2 by patching the rules. (That said, I had a bug in the implementation that didn’t manifest in part 1 that took me ages to track down).

At the end I used Task.stream_async to process the messages in parallell which cut the time in half to about 0.05s.

3
Post #8
cblavier

cblavier

For part1 I generated a giant Regex.

Then for part2, to prevent infinite recursion, I just set a depth limit (I chose 5). I was lucky to get the solution with 5 because starting from 6, Elixir couldn’t compile the Regex (too large) :sweat_smile:

My code: Part1 / Part2

my regex

:upside_down_face:

~r/^((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a))))))((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b))|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b))|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b))|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b))|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)((((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b))|(((a(((aaa|b(ab|ba))b|((bb|ba)b|(aa|ba)a)a)b|(((b|a)(b|a)b|(ab|aa)a)a|(a(ab|ba)|b(bb|ba))b)a)|b(b(b((ab|b(b|a))b|(ab|aa)a)|a(a(ab|ba)|b(bb|ba)))|a(b(bb|ba)(b|a)|a(bab|aab))))a|((a((a(ab|aa)|bab)a|(a(ab|bb)|b(bb|ba))b)|b(b(ab|aa)a|((ab|aa)b|((b|a)a|ab)a)b))b|(b((b(ab|aa)|a(ab|b(b|a)))a|((bb|aa)b|(ab|aa)a)b)|a((bab|aab)b|(a(bb|ba)|b(ab|aa))a))a)b)b|(((a(b(a(ab|aa)|bab)|a((bb|ba)b|(ab|ba)a))|b((b(bb|ba)|aab)b|b(ab|aa)a))a|((b(b(bb|a(b|a))|a(bb|ba))|a(((b|a)a|bb)b|(ab|b(b|a))a))a|(a((aa|ba)b|(ab|ba)a)|b((bb|a(b|a))a|((b|a)a|ab)b))b)b)b|(b(b((a(aa|ba)|b(ab|b(b|a)))a|((bb|a(b|a))b|(aa|ba)a)b)|a(b((ab|bb)a|(bb|a(b|a))b)|a(aab|b(bb|a(b|a)))))|a(((b(ab|ba)|a(ab|bb))b|((ab|b(b|a))a|(ab|ba)b)a)b|((a(bb|aa)|b(ab|aa))b|(bab|aab)a)a))a)a)(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b)))(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b)))(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b)))(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b)))(a(a((a(b(a(ab|ba)|bba)|a(aab|b(bb|a(b|a))))|b(a((ab|bb)a|(ab|b(b|a))b)|b((ab|b(b|a))a|(ab|ba)b)))b|(a(a(b(ab|b(b|a))|a(b|a)(b|a))|b(aba|b(ab|aa)))|b((baa|(bb|ba)b)b|(abb|((b|a)a|ab)a)a))a)|b(((b((bb|aa)b|aaa)|a(a((b|a)a|bb)|bba))a|(a((bb|a(b|a))b|aba)|b(b|a)((b|a)a|ab))b)b|((((bb|ba)b|((b|a)a|bb)a)a|(b(bb|ba)|aab)b)a|(ab(aa|ba)|b(((b|a)a|bb)a|(ab|bb)b))b)a))|b((((a(ab|aa)a|b((bb|aa)b|baa))b|(b((bb|ba)a|(ab|aa)b)|a(((b|a)a|bb)b|(b|a)(b|a)a))a)b|(b((bab|(ab|bb)a)b|(baa|a(ab|bb))a)|a(b(bab|(aa|ba)a)|a(a((b|a)a|bb)|bba)))a)a|(((b(b(b|a)(b|a)|abb)|a(b|a)(aa|ba))b|(b(b((b|a)a|ab)|a(ab|bb))|a(aaa|bbb))a)b|(a(a(b|a)((b|a)a|bb)|b(ab|aa)(b|a))|b(a(a(bb|aa)|b(ab|aa))|b((bb|ba)a|aab)))a)b)))$/

2
Post #5
princemaple

princemaple

defmodule D19 do
  def parse_rules(text) do
    text
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_rule/1)
    |> Enum.into(%{})
  end

  def parse_rule(line) do
    [rule_number, rule_data] = String.split(line, ": ")

    rule_branches =
      rule_data
      |> String.replace("\"", "")
      |> String.split(" | ")
      |> Enum.map(&String.split/1)

    {rule_number, rule_branches}
  end

  def solve(rules, text) do
    text
    |> String.split("\n", trim: true)
    |> Enum.filter(&(consume(rules, &1, "0") == ""))
    |> length
  end

  def consume(_rules, "a" <> rest, "a") do
    rest
  end

  def consume(_rules, "b" <> rest, "b") do
    rest
  end

  def consume(_rules, _no_match, char) when char in ["a", "b"] do
    nil
  end

  def consume(rules, line, rule) do
    Enum.find_value(rules[rule], fn branch ->
      Enum.reduce(branch, line, fn rule, line ->
        line && consume(rules, line, rule)
      end)
    end)
  end
end

rules  = ...
text = ...

# p1
rules |> D19.parse_rules() |> D19.solve(text) |> IO.inspect()

# p2
rules
|> String.replace("0: 8 11", "0: 8")
|> String.replace("8: 42", "8: 42 11 | 42 8")
|> String.replace("11: 42 31", "11: 42 31 | 42 11 31")
|> D19.parse_rules()
|> D19.solve(text)
|> IO.inspect()

cheated p2 by changing the “change” to a manually simplified form, moving the 11 in 0 to the first branch of 8, that gives the same match result but avoids back tracking.

1
Post #3
code-shoily

code-shoily

Nice commit message.

1
Post #7

Where Next?

View thread on forum (has 15 responses!)
2020
advent-of-code
Home Learning Resources>Coding Challenges
#2020#advent-of-code
11 1177 15
Last post

Popular in Challenges Top

DmitriyChernyavskiy
Learning Resources>Coding Challenges

How to implement extension of functionality as inheritance in object oriented language
Hello everyone, I’m a new in elexir and functional language. I’m trying to implement Websocket interraction with server. On first layer...
#callbacks#use#genserver
13 1602 7
New
bjorng
Learning Resources>Coding Challenges

Advent of Code 2019 - Day 12
Note: This topic is to talk about Day 12 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can joi...
#2019#advent-of-code
33 1688 15
New
rugyoga
Learning Resources>Coding Challenges

Advent of Code 2024 - Day 8
27 lines
#advent-of-code#2024
14 716 20
New
bjorng
Learning Resources>Coding Challenges

Advent of Code 2019 - Day 9
Note: This topic is to talk about Day 9 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can join...
#2019#advent-of-code
34 2019 24
New
Aetherus
Learning Resources>Coding Challenges

Advent of Code 2022 - Day 7
Today’s challenge is quite interesting. I ended up using Zipper to solve this problem. Maybe I overengineered quite a bit. The data stru...
#advent-of-code#2022
15 2265 16
New
bjorng
Learning Resources>Coding Challenges

Advent of Code 2021 - Day 9
This topic is about Day 9 of the Advent of Code 2021 . We have a private leaderboard (shared with users of Erlang Forums): https://adve...
#advent-of-code
7 2192 13
New
jkwchui
Learning Resources>Coding Challenges

Advent of Code 2022 - Day 11
Monkeys fitted squarely as GenServers in my head. My initial problem was using cast instead of call; I imagine impolite monkeys slinging...
#advent-of-code
16 1818 19
New
rugyoga
Learning Resources>Coding Challenges

Advent of Code 2024 - Day 9
Not the prettiest but it works
#advent-of-code#2024
19 1175 30
New
kwando
Learning Resources>Coding Challenges

Advent of Code 2022 - Day 9
Took a while, but another use case for “move vectors” today and pattern matching. :slight_smile: The trick was to first generate a list...
#advent-of-code#2022
9 1456 11
New
code-shoily
Learning Resources>Coding Challenges

Advent of Code 2024 - Day 3
Here’s my day 3 code This was quite easy. I was afraid Part 2 would be “un-regex-able” and was preparing for hand crafting automata bu...
#advent-of-code#2024
82 1894 57
New

Other popular topics Top

JDanielMartinez
Questions & Help>Questions

** (RuntimeError) could not lookup Ecto repo Repo because it was not started or it does not exist
Hi! May someone helps me, please! I have two apps into an umbrella project: the first one is Database, which manages queries, and the se...
#umbrella#testing#repo#runtimeerror
11 15040 14
New
itssasanka
Questions & Help>Questions

Why use `utc_datetime` over `naive_datetime` for Ecto?
Hi all, Trying to get some more clarity over utc_datetime and naive_datetime for Ecto: https://hexdocs.pm/ecto/Ecto.Schema.html#module-...
#ecto#timestamps#datetime#timezones
115 14814 19
New
ycv005
Questions & Help>Questions

BEAM file compliation error after degrading Erlang version from 22 to 21
I have followed this StackOverflow post to install the specific version of Erlang. And When I am running mix ecto.setup then getting fol...
/phoenix#erlang
33 15699 4
New
fireproofsocks
Questions & Help>Questions

Defining Ecto Schemas (PostGres) to use NOT NULL in column definitions
I’m working on defining a simple Ecto schema for a table (in PostGres), but I don’t see where I can define a column as NOT NULL. Conside...
#ecto
29 14078 4
New
script
Questions & Help>Questions

Removing spaces and characters from string
If I have a string “1000 cfu/ml” . I want to remove the characters and / and space . So the string is like this "1000" What is the ...
#regex
11 14427 2
New
vonH
Questions & Help>Questions

How do I kill a process ` #PID<0.186.0` in iex?
When I run the Plug and I recompile I wind up having to use Ctrl C to quit iex and start again. Witht the help of rlwrap I can use the cu...
#iex#processes#how-to-question
36 21149 8
New
stefanluptak
Questions & Help>Questions

Using VSCode on multiple monitors
Hello everybody, usually, I use a 29" ultra-wide monitor for VSCode which can easily accomodate explorer (files panel) + file with code ...
#vscode#vscode-elixir
7 17615 6
New
WestKeys
Questions & Help>Questions

Mint vs Finch vs Gun vs Tesla vs HTTPoison etc
Currently suffering from paralysis by [HTTP client] analysis. This is rather unusual in Elixirland as there tends to be consensus on the ...
#http_client
252 21859 30
New
Patoshizzle
Questions & Help>Questions

(Postgrex.Error) FATAL 28P01 (invalid_password) password authentication failed for user “postgres”
After calling mix ecto.create I get this error: 17:00:32.162 [error] GenServer #PID&lt;0.412.0&gt; terminating ** (Postgrex.Error) FATAL...
#ecto#postgres#troubleshooting
10 28696 20
New
jay1
Questions & Help>Questions

Why isn’t mnesia the most preferred database for use in Elixir/Phoenix?
Why is it that the mnesia database isn’t the most preferred database for use in Elixir/Phoenix?
/phoenix#mnesia
123 21186 22
New
Back to top

Learning Resources>Coding Challenges

Resources Challenges ❯

Latest on Elixir Forum

Elixir Forum ❯

Sponsor Spotlight

EEF

Supporting innovation across the BEAM ecosystem.

Our Sponsors

Dashbit

Build Elixir applications with speed and confidence.

EEF

Supporting innovation across the BEAM ecosystem.

Coders51

We build reliable cloud platforms for business-critical systems.

AppSignal

Catch errors, track performance, monitor hosts and more.

Manning

Develop your skills with books, videos, and courses.

ElixirCasts

Producing high quality Elixir screencasts since 2017.

WyewWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

Categories:

Sub Categories:

Forums

Our Sponsors

Dashbit

Build Elixir applications with speed and confidence.

EEF

Supporting innovation across the BEAM ecosystem.

Coders51

We build reliable cloud platforms for business-critical systems.

AppSignal

Catch errors, track performance, monitor hosts and more.

Manning

Develop your skills with books, videos, and courses.

ElixirCasts

Producing high quality Elixir screencasts since 2017.

WyewWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

We're in Beta

About us Mission Statement