*Note: This topic is to talk about Day 6 of the Advent of Code 2019.*

There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:

`39276-eeb74f9a`

*Note: This topic is to talk about Day 6 of the Advent of Code 2019.*

There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:

`39276-eeb74f9a`

1 Like

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.

4 Likes

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.

2 Likes

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)`

1 Like

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.

2 Likes

Hereâ€™s my solution, also powered by digraph.

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

4 Likes

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.

2 Likes

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.

2 Likes

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.

1 Like

My take on day6 : https://github.com/cblavier/advent/tree/master/lib/2019/day6

Not so much code, and I think my solution is elegant. But it took me hours to write it because I was heading into an algorithm way too complicated until I got enlighted

Still, it was a lot of fun, again!

2 Likes

Todayâ€™s problem was pretty easy. My solution does a lot more work for part 2 than necessary; switching to Erlangâ€™s arrays wouldâ€™ve sped it up. Still, it doesnâ€™t take very long to run. My part 1 should also keep track of distances itâ€™s already seen (like @NobbZâ€™s solution).

1 Like

I didnâ€™t know about digraphâ€¦ so to solve part2 I had to (painfully ) implement functions to create a graph (represented by a map of verteces and neighbors) and a sort of Dijkstra min path to find the minimum transitions neededâ€¦

Going see now how much time I could save with digraphâ€¦

**Update**: digraphâ€¦ great tool, it took much less. Iâ€™ve just added the digraph

version as well.

1 Like

A lot of people seem to have interpreted this as a graph problem. While not technically incorrect, itâ€™s much simpler if you think of it as a tree. To solve part 2, forget Dijkstra, just find the common ancestor of YOU and SAN.

12 Likes

I saw a lot of mentions of Erlangâ€™s digraph library. Out of interest, did anyone take a look at https://github.com/bitwalker/libgraph - an Elixir graph library implementation?

Today I learned about digraph. So implemented part 2 with digraph and without digraph. Both solutions here