This one took longer than it should, because it turned up a possible bug in :digraph_utils.
Day 1:
defmodule PrintQueue do
def read(filename) do
filename
|> File.read!()
|> String.split("\n\n")
|> then(fn [rules, pages] ->
{
parse_rules(rules),
parse_pages(pages)
}
end)
end
defp parse_rules(rules) do
g = :digraph.new()
rules
|> String.split("\n")
|> Enum.each(fn line ->
line
|> String.split("|")
|> Enum.map(&String.to_integer/1)
|> then(fn [v1, v2] ->
:digraph.add_vertex(g, v1)
:digraph.add_vertex(g, v2)
:digraph.add_edge(g, v1, v2)
end)
end)
g
end
defp parse_pages(pages) do
pages
|> String.trim()
|> String.split("\n")
|> Enum.map(fn line ->
line
|> String.split(",")
|> Enum.map(&String.to_integer/1)
end)
end
def valid?(page, rules) do
subgraph = fixed_subgraph(rules, page)
page
|> triangle()
|> Enum.to_list()
|> Enum.each(fn {v1, v2} ->
:digraph.add_edge(subgraph, v1, v2)
end)
result = :digraph_utils.topsort(subgraph)
:digraph.delete(subgraph)
result
end
defp triangle([_]), do: []
defp triangle([h | rest]) do
rest
|> Enum.map(&{h, &1})
|> Stream.concat(triangle(rest))
end
def edges(g) do
:digraph.edges(g)
|> Enum.map(&:digraph.edge(g, &1))
|> Enum.map(fn {_, a, b, _} -> {a, b} end)
|> Enum.sort()
end
defp fixed_subgraph(g, vs) do
sg = :digraph_utils.subgraph(g, vs)
[{_, last_eid}] = :ets.lookup(elem(g, 3), :"$eid")
ntab = elem(sg, 3)
:ets.delete(ntab, :"$eid")
:ets.insert(ntab, {:"$eid", last_eid})
sg
end
def middle(vs) do
len = length(vs)
Enum.at(vs, div(len, 2))
end
end
{rules, pages} = PrintQueue.read("input.txt")
pages
|> Enum.map(&PrintQueue.valid?(&1, rules))
|> Enum.filter(& &1)
|> Enum.map(&PrintQueue.middle/1)
|> Enum.sum()
|> IO.inspect()
The idea:
- turn the rules into a
:digraphof “x precedes y” - for a list of pages, get a subgraph that only has those pages as vertices
- compute all the “x precedes y” relations from the given page list and add them to the subgraph
- check the subgraph for a cycle; a rule violation (eg putting 75 before 97 with the rule
97|75) will have one
Hilariously, part 2 requires LESS effort than part 1 - the “correctly ordered” updates are just a :digraph_utils.topsort of the subgraph!
