Advent of Code 2019 - Day 6

Here is my solution.

Wait, digraph has the full answer in it??? Good to know for the future. I like your pt1 solution too.

My Solution ended up doing DFS/BFS manually. I got tripped up a bit by trying to do BFS without an Enumeration, and then I remembered that is a real hassle and that Enum.map would work great.

My Part 1 solution using :digraph. Deadly slow:

graph = :digraph.new([:acyclic, :private])

edges = File.stream!("./day06-input.txt")
        |> Enum.map(fn line -> line |> String.trim() |> String.split(")") end)

vertices = edges
           |> List.flatten()
           |> MapSet.new()

Enum.each(vertices, fn v -> :digraph.add_vertex(graph, v) end)

Enum.each(edges, fn [v1, v2] -> :digraph.add_edge(graph, v1, v2) end)

vertices
|> Stream.map(fn vertex -> :digraph.get_path(graph, "COM", vertex) end)
|> Stream.filter(& &1)
|> Stream.map(fn path -> length(path) - 1 end)
|> Enum.sum()
|> IO.inspect()

UPDATE part 2 solution

graph = :digraph.new([:cyclic, :private])

edges = File.stream!("./day06-input.txt")
        |> Enum.map(fn line -> line |> String.trim() |> String.split(")") end)

vertices = edges
           |> List.flatten()
           |> MapSet.new()

Enum.each(vertices, fn v -> :digraph.add_vertex(graph, v) end)

Enum.each(edges, fn [v1, v2] ->
  :digraph.add_edge(graph, v1, v2)
  :digraph.add_edge(graph, v2, v1)
end)

path = :digraph.get_short_path(graph, "YOU", "SAN")

IO.inspect(length(path) - 3)

Note that the graph needs to be bidirectional and thus cyclic, so I just added 2 edges for each pair of vertices, in opposite directions.

Part 1 will be much faster if you reverse the direction of the edges. That is, add the edges like this:

Enum.each(edges, fn [v1, v2] -> :digraph.add_edge(graph, v2, v1) end)

and search for the path like this:

|> Stream.map(fn vertex -> :digraph.get_path(graph, vertex, "COM") end)

Indeed! Thank you @bjorng. I guess it’s because there is no need to search a path from a child node to a parent node, but not the other way around.

Here’s my solution, also powered by digraph.

For the fun of it, I also implemented a pure functional version.

My day 6 solution, not powered by :digraph, which I am going to go look up right now.

At first, I was duped by the example into thinking they were going to give me a nicely ordered input set. That was silly, and cost me quite a bit of time.

I made a solution without :digraph because I had no idea it existed. And I suppose because what’s the point of using a functional programming language if you are going to use shared mutable data structures.

This was a quick one, though I lost about an hour reading into dijkstra algorithm for pathfinding again and trying to implement it, before just resorting into :digraph for part 2.

My solution, no digraph