Graph traversals
Parse
graph =
puzzle_input
|> String.split("\n", trim: true)
|> Map.new(fn <<from::binary-3>> <> ": " <> rest ->
{from, String.split(rest)}
end)
Implementation
defmodule Servers do
def paths(graph, from, to), do: paths(graph, from, to, [from])
defp paths(_graph, to, to, acc), do: [Enum.reverse(acc)]
defp paths(graph, from, to, acc) do
if next = graph[from] do
Stream.flat_map(next, &paths(graph, &1, to, [&1 | acc]))
else
[]
end
end
def paths_through(graph, from, to, required),
do: path_through(graph, from, to, MapSet.new(required), %{})
defp path_through(_graph, to, to, required, memo),
do: {if(Enum.empty?(required), do: 1, else: 0), memo}
defp path_through(graph, from, to, required, memo) do
state = MapSet.delete(required, from)
with :error <- Map.fetch(memo, {from, state}),
{:ok, next} <- Map.fetch(graph, from) do
{sum, memo} =
Enum.reduce(next, {0, memo}, fn n, {sum, acc} ->
{c, next_acc} = path_through(graph, n, to, state, acc)
{c + sum, next_acc}
end)
{sum, Map.put(memo, {from, state}, sum)}
else
:error -> {0, memo}
{:ok, val} -> {val, memo}
end
end
end
Part 1
Servers.paths(graph, "you", "out") |> Enum.count()
Part 2
Servers.paths_through(graph, "svr", "out", ["dac", "fft"])
|> elem(0)
