Avent of Code 2020 - Day 19

Papey

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

0 1479 15

2020-12-23 08:28:35 UTC

Showing Posts 1 to 10

Show Best Posts
Show All (oldest first)
Show All (newest first)

Papey

Regex go brrrrrrrrrrrrr and it works ! (for part 1 at least, part 2 in progress)

https://github.com/papey/aoc/commit/e96aadc898b2d48d547b52999ba4cbd0860a5726

Post #1

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.

Post #2

code-shoily

Part 1 is here, part 2 will be problematic. Tried to use + with line 8 but cannot regexify line 11. Might have to recall my theory of automation for this one.

defmodule AdventOfCode.Y2020.Day19 do
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 19

  @alphabet ~w/a b |/

  def run_1 do
    {rules, messages} = process(input!())

    regex = to_regex(:erlang.iolist_to_binary(rule_to_regex(rules, "0", "")))

    length(Enum.filter(messages, &Regex.match?(regex, &1)))
  end

  def process(input), do: parse(String.split(input, "\n\n"))

  def parse([rules, messages]), do: {parse_rules(rules), parse_messages(messages)}

  defp parse_rules(rules) do
    rules
    |> String.split("\n")
    |> Enum.map(&String.replace(&1, "\"", ""))
    |> Enum.map(fn rule ->
      [idx, rule] = String.split(rule, ":")
      {idx, String.trim(rule)}
    end)
    |> Enum.into(%{})
  end

  defp parse_messages(messages), do: String.split(messages, "\n")

  defp rule_to_regex(rules, idx, regex) do
    rules[idx]
    |> String.split(" ")
    |> Enum.map(&((&1 in @alphabet && &1) || ["(", rule_to_regex(rules, &1, regex), ")"]))
  end

  defp to_regex(source), do: %Regex{source: "^" <> source <> "$"}
end

Post #3

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)

My code: Part1 / Part2

my regex

~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)))$/

Post #4

Papey

And for part 2, regex go brrrrrrrrrrrrrrrrrrrrrrrrrr brrrrrrrrrrr

https://github.com/papey/aoc/commit/4f651d6bd3cb53d437d3435469db1f01e82f35df

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))))))))))$/

Post #5

code-shoily

Nice commit message.

Post #6

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.

Post #7

bjorng

Erlang Core Team

In the end, I solved part 2 by a simple generalization of part 1, but I spent a loooong time fixing some elusive bugs. (The last bug I squashed by adding this line.)

Here is my solution.

Post #8

camilleryr

Parsed the rules into regex for the solutions - I had a parsing bug that didnt manifest in the test input and I went down the wrong path for the recursive regex for a while - so this code is a mess and it will stay that way, because this took me enough time as it is.

https://github.com/camilleryr/advent20/blob/main/lib/day_19.ex

Post #9