Advent of Code 2019 - Day 6

[bjorng]

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

[bjorng]

Here is my solution.

[sb8244]

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.

[Aetherus]

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.

[bjorng]

@Aetherus

My Part 1 solution using :digraph . Deadly slow:

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)

[Aetherus]

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.

[sasajuric]

Here’s my solution, also powered by digraph.

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

[aaronnamba]

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.

[xfix]

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.

KonradBorowski/advent_of_code_2019/blob/master/lib/day6.ex

[NobbZ]

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.

NobbZ/aoc_ex/blob/master/lib/y2019/d6.ex

[milli]

My solution, no digraph

[mkasztelnik]

My solution

[ColaCheng]

Here is my solution.

[cblavier]

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!

[faried]

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

[alvises]

part1 and part2

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.

[JEG2]

I love an excuse to use digraph!

[aaronnamba]

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.

[mindok]

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?

[ganesh]

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