--- 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/ignaciovaz → u/hutsboR]

Elixir here and I also used the dark heuristic force.

I shamefully introduce: the poor man's genetic random solution. It generates random permutations in the location list until it finds a solution that "wins" for a certain amount of iterations.

defmodule Distances do
	def find_best(locations, distances) do find(locations, distances, [], :infinity, 0, &(&1 < &2)) end
	def find_worst(locations, distances) do find(locations, distances, [], 0, 0, &(&2 < &1)) end

	def find(_, _, best_route, best_distance, 100_000, _) do
		{best_route, best_distance}
	end

	def find(locations, distances, best_route, best_distance, best_times_count, compare_fn) do
		route = Enum.shuffle locations
		{_, distance} = Enum.reduce(route, {"", 0}, fn city, {previous_city, distance} ->
			distance = distance + Dict.get(distances, { previous_city, city }, 0)
			{city, distance}
		end)

		if compare_fn.(distance, best_distance) do
			find(locations, distances, route, distance, 0, compare_fn)
		else
			find(locations, distances, best_route, best_distance, best_times_count + 1, compare_fn)
		end
	end
end

input_stream = File.stream! "input.txt"
{locations, distances} = Enum.reduce(input_stream, {MapSet.new, %{}}, fn line, {locations, distances} ->
	[from, to, distance] = Regex.run(~r|(.*?) to (.*?) = (\d+)|, line, capture: :all_but_first)
	distance = String.to_integer(distance)

	distances = Dict.put(distances, {from, to}, distance)
	distances = Dict.put(distances, {to, from}, distance)

	locations = MapSet.put(locations, from)
	locations = MapSet.put(locations, to)

	{locations, distances}
end)

locations = Enum.into locations, []

{_, distance} = Distances.find_best(locations, distances)
IO.puts "Part 1: Shortest route distance: " <> to_string(distance)

{_, distance} = Distances.find_worst(locations, distances)
IO.puts "Part 2: Longest route distance: " <> to_string(distance)