Avent of Code 2020 - Day 19

Papey · December 19, 2020, 11:34am

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

Papey · December 19, 2020, 11:38am

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

princemaple · December 19, 2020, 12:06pm

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.

code-shoily · December 19, 2020, 1:44pm

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

cblavier · December 19, 2020, 2:08pm

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

Papey · December 19, 2020, 4:40pm

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

code-shoily · December 19, 2020, 4:52pm

Nice commit message.

Hallski · December 19, 2020, 4:55pm

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.

bjorng · December 19, 2020, 6:11pm

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.

camilleryr · December 19, 2020, 6:49pm

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.

github.com

camilleryr/advent20/blob/main/lib/day_19.ex

defmodule Day19 do
  def test_input do
    """
    0: 4 1 5
    1: 2 3 | 3 2
    2: 4 4 | 5 5
    3: 4 5 | 5 4
    4: "a"
    5: "b"

    ababbb
    bababa
    abbbab
    aaabbb
    aaaabbb
    """
  end

  def test_input_2 do
    """

This file has been truncated. show original

code-shoily · December 19, 2020, 9:20pm

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems."

Does not quite work for day 19 of 2020 Advent of Code. In fact quite the inverse.

Ablu · December 19, 2020, 9:37pm

Not very pretty (planning to do some performance learning on this code layer maybe… (currently it takes 40s for the second task on a Ryzen 3900X)), but since nobody posted a CYK based solution, here is mine :

defmodule Aoc19 do
  defp parse_rule(rule) do
    [rule_no, rule] = String.split(rule, ": ")

    String.split(rule, " | ")
    |> Enum.map(fn x -> {rule_no, String.split(x, " ")} end)
  end

  def parse(file) do
    [rules, inputs] =
      File.stream!(file)
      |> Stream.map(&String.trim/1)
      |> Stream.chunk_by(fn x -> x == "" end)
      |> Stream.reject(fn x -> x == [""] end)
      |> Enum.to_list()

    {rules |> Enum.flat_map(&parse_rule/1) |> normalize(), inputs}
  end

  def normalize(rules) do
    rules_to_collapse =
      rules
      |> Enum.filter(fn {_, rhs} ->
        case rhs do
          [_, _] -> false
          ["\"" <> <<_::bytes-size(1)>> <> "\""] -> false
          _ -> true
        end
      end)

    get_replacements = fn x ->
      Enum.concat([x], Stream.filter(rules_to_collapse, fn {nt, _} -> nt == x end) |> Enum.map(fn {_, [r]} -> r end))
    end

    rules
    |> Stream.reject(fn x -> Enum.member?(rules_to_collapse, x) end)
    |> Stream.flat_map(fn orig = {nt, rhs} ->
      case rhs do
        [a, b] ->
          for new_a <- get_replacements.(a),
              new_b <- get_replacements.(b) do
            {nt, [new_a, new_b]}
          end
        _ -> [orig]
      end
    end)
    |> Enum.to_list()
  end

  def well_formed?(rules) do
    rules
    |> Enum.reject(fn {_, rhs} ->
      case rhs do
        ["\"a\""] -> true
        ["\"b\""] -> true
        [_, _] -> true
        _ -> false
      end
    end)
    |> IO.inspect(label: "invalid")
    |> Enum.count() == 0
  end

  def get_possible_productions(rules, i, lower_rows) do
    depth = Enum.count(lower_rows)
    cell_pairs_to_check =
      for d <- 0..(depth - 1),
          potential_match1 <-
            lower_rows
            |> Enum.at(d)
            |> Enum.at(i),
          potential_match2 <-
            lower_rows
            |> Enum.at(depth - d - 1)
            |> Enum.at(i + (depth - d)) do
        {potential_match1, potential_match2}
      end
      |> List.flatten()

    potentials_nts =
      cell_pairs_to_check
      |> Stream.flat_map(fn {r1, r2} ->
        Enum.filter(rules, fn {_, rhs} ->
          [r1, r2] == rhs
        end)
        |> Enum.map(fn {nt, _} -> nt end)
      end)
      |> Enum.filter(fn x -> x != [] end)

    potentials_nts
  end

  def reverse_t_rule(rules, x) do
    Enum.find_value(rules, fn {nt, replacement} -> if replacement == ["\"#{x}\""], do: nt end)
  end

  def matches?(rules, input) do
    n = String.length(input)

    to_nts = String.graphemes(input) |> Enum.map(fn x -> [reverse_t_rule(rules, x)] end)

    (n - 1)..1
    |> Enum.reduce([to_nts], fn j, lower_rows ->
      [
        for i <- 0..(j - 1) do
          get_possible_productions(rules, i, lower_rows)
        end
        | lower_rows
      ]
    end)
    |> Enum.at(0)
    |> Enum.at(0)
    |> Enum.any?(fn x -> x == "0" end)
  end
end

I cheated for the second task by doing:

11: 42 31 | 42 X
X: 11 31

(The normalize() function already was complex enough :P)

felix-alonso · December 20, 2020, 8:44pm

Hallski, your solution saved me from banging my head against the wall for another couple hours. I had something very similar, but was returning results instead of concatenating them to a queue of actions. I was too stubborn to stop, but too burnt to re-evaluate.

APB9785 · December 21, 2020, 7:50pm

I think this is where my AoC journey stops this year… Couldn’t make any headway into 19 or 20.

felix-alonso · December 22, 2020, 6:19pm

If it is any consolation, Day 21 is a lot easier than 19 or 20. If you want to keep the party going, I would recommend skipping straight to it. (Plus, I hear there is some sort of crab fight on Day 22.)

Papey · December 23, 2020, 8:28am

+1 on that, 19 and 20 are hard because this is the last week-end of AOC. On week days they are always a little less intensive.