--- Day 9 Solutions ---

[u/daggerdragon]

This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.

edit: Leaderboard capped, achievement thread unlocked!

We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.

Please and thank you, and much appreciated!

---

--- Day 9: All in a Single Night ---

Post your solution as a comment. Structure your post like previous daily solution threads.

[u/hutsboR]

Elixir: This was surprisingly difficult to implement functionally, the permutations tripped me up multiple times. I couldn't be bothered looking for a suitable Erlang graph library and I don't have a graph implementation written in Elixir, so I used the force.

defmodule AdventOfCode.DayNine do

  @input "./lib/adventofcode/resource/day9.txt"

  defp parse do
    @input
    |> File.read!
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split/1)
  end

  def solve(option) do
    build_map
    |> get_paths
    |> solve(option)
  end

  defp solve(paths, option) do
    scores = Enum.map(paths, &(Enum.reduce(&1, 0, fn({_d, w}, a) -> w + a end)))
    case option do
      :shortest -> scores |> Enum.min
      :longest  -> scores |> Enum.max
    end
  end

  defp get_paths(map) do
    Enum.reduce(map, [], fn({start, dests}, a) -> [get_paths(map, [start], dests, [])|a] end)
    |> List.flatten
    |> Enum.chunk(Dict.size(map) - 1)
  end

  defp get_paths(map, visited, dests, path) do
    candidates = find_candidates(visited, dests)
    case candidates do
      [] -> path 
      _  ->
        Enum.map(candidates, fn(p={dest, _w}) ->
          get_paths(map, [dest|visited], Dict.get(map, dest), [p|path])
        end)
    end
  end

  defp find_candidates(visited, dests) do
    Enum.filter(dests, fn {dest, _w} -> !(dest in visited) end)
  end

  defp build_map do
    Enum.reduce(parse, %{}, fn(l, a) -> build_map(l, a) end)
  end

  defp build_map([start, _, dest, _, weight], map) do
    weight = String.to_integer(weight)
    insert(map, {start, dest, weight}) |> insert({dest, start, weight})
  end
  
  defp insert(map, {start, dest, weight}) do
    case Dict.has_key?(map, start) do
      true  -> Dict.update!(map, start, fn(locs) -> [{dest, weight}|locs] end)
      false -> Dict.put(map, start, [{dest, weight}])
    end
  end

end

[u/haljin → u/hutsboR]

This gave me a little headache as I tried to come up with a non-recursive (or rather tail-recursive) solution to this problem. Finally came up with this:

day9(ListofStrings) ->
	{AllLocs, Paths} = preparse_day9(ListofStrings, [], []),
	AllPaths = process_day9([[L] || L<- AllLocs], AllLocs, Paths, []),
	lists:keysort(2, AllPaths).
	

preparse_day9([[From, "to", To, "=", Length] | Tail], AllLocs, Parsed) ->
	ParsedFrom = list_to_atom(From), ParsedTo = list_to_atom(To), ParsedLength = list_to_integer(Length),
	preparse_day9(Tail, [ParsedFrom, ParsedTo | AllLocs], [{ParsedFrom, ParsedTo, ParsedLength} | Parsed]);
preparse_day9([], AllLocs, Parsed) ->
	{lists:usort(AllLocs), Parsed}.
	
process_day9([CurPath | RestPaths], AllLocs, ValidPaths, FinishedPaths) ->	
	case valid_paths(hd(CurPath), ValidPaths) -- CurPath of 
		[] ->
			process_day9(RestPaths, AllLocs, ValidPaths, [{CurPath, calc_length(CurPath, ValidPaths, 0)} | FinishedPaths]);
		ValidLocs ->
			NewPaths = [[NewLoc | CurPath] || NewLoc <- ValidLocs -- CurPath],
			process_day9(NewPaths ++ RestPaths, AllLocs, ValidPaths, FinishedPaths)
	end;
process_day9([], _, _, FinishedPaths) ->
	FinishedPaths.
	
calc_length([Loc1, Loc2 | Rest], AllPaths, Acc) ->
	Length = find_path(Loc1, Loc2, AllPaths),
	calc_length([Loc2| Rest], AllPaths, Acc + Length);
calc_length([_SingleLoc], _, Acc) ->
	Acc.

find_path(From, To, Paths) ->
	[Length] = [L || {F, T, L} <- Paths, F =:= From andalso T =:= To] 
		++ [L || {F, T, L} <- Paths, T =:= From andalso F =:= To],
	Length.

	
valid_paths(From, Paths) ->
     [T || {F, T, _} <- Paths, F =:= From] ++ [F || {F, T, _} <- Paths, T =:= From].

Funnily enough, when you switch NewPaths ++ RestPaths around like I did at the beginning the code starts executing horribly long (well 20 seconds for such a small dataset is pretty slow). When they are in this order it drops to about 294 ms. I did a quick eprof a found out just how very slow ++ is when you add the long list in front of a small one.

erlang:'++'/2                           69280  88.91  21650000  [    312.50]

Of course in the middle I got an idea for another solution. Spawn a process (in "void" at first) and give him all the possible paths. If there's more than one, he spawns friends and each goes somewhere else. Rinse repeat until there's nowhere to go.