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)
