defmodule AdventOfCode2018.Day07 do
      def part1(input) do
        instructions =
          input
          |> String.split("\n", trim: true)
          |> Enum.map(&parse_line/1)

        all_steps =
          Enum.reduce(instructions, %{}, fn {left, right}, acc ->
            acc
            |> Map.put_new(left, [])
            |> Map.put_new(right, [])
          end)

        Enum.reduce(instructions, all_steps, fn {left, right}, acc ->
          Map.update(acc, right, [left], &Enum.sort([left | &1]))
        end)
        |> do_step([])
        |> List.to_string()
      end

      defp parse_line(line) do
        <<"Step ", left, " must be finished before step ", right, " can begin.">> = line

        {left, right}
      end

      def do_step(map, acc) when map == %{} do
        Enum.reverse(acc)
      end

      def do_step(map, acc) do
        {delete_me, []} =
          to_remove =
          map
          |> Enum.min_by(
            fn
              {key, []} -> key
              {_, _} -> :infinity
            end,
            fn -> {nil, nil} end
          )

        new_map =
          Enum.reduce(map, %{}, fn
            {k, v}, acc when {k, v} == to_remove -> Map.delete(acc, k)
            {k, v}, acc -> Map.put_new(acc, k, List.delete(v, delete_me))
          end)

        do_step(new_map, [delete_me | acc])
      end

      def part2(input, workers \\ 5, seconds_added \\ 60) do
        instructions =
          input
          |> String.split("\n", trim: true)
          |> Enum.map(&parse_line/1)

        workers = Enum.reduce(1..workers, %{}, fn n, acc -> Map.put_new(acc, n, {0, nil}) end)

        all_steps =
          Enum.reduce(instructions, %{}, fn {left, right}, acc ->
            acc
            |> Map.put_new(left, [])
            |> Map.put_new(right, [])
          end)

        Enum.reduce(instructions, all_steps, fn {left, right}, acc ->
          Map.update(acc, right, [left], &Enum.sort([left | &1]))
        end)
        |> do_step_with_workers(workers, 0, seconds_added)
      end

      def do_step_with_workers(map, workers, total_time, _) when map == %{} do
        {_, {time_to_add, _}} =
          Enum.max_by(workers, fn {_k, {time, _}} -> time end, fn -> {nil, 0} end)

        total_time + time_to_add
      end

      def do_step_with_workers(map, workers, total_time, seconds_added) do
        work_available? = Enum.any?(map, fn {_k, v} -> v == [] end)
        worker_free? = Enum.any?(workers, fn {_k, {_time_left, assigned}} -> assigned == nil end)

        if work_available? and worker_free? do
          {map, workers} = assign_worker_to_step(map, workers, seconds_added)
          do_step_with_workers(map, workers, total_time, seconds_added)
        else
          {map, workers, time_spent} = finish_next_completed_task(map, workers)
          do_step_with_workers(map, workers, total_time + time_spent, seconds_added)
        end
      end

      def assign_worker_to_step(map, workers, seconds_added) do
        {worker_to_use, {0, nil}} =
          Enum.find(workers, fn {_k, {_time_left, assigned}} -> assigned == nil end)

        {step_to_assign, []} =
          map
          |> Enum.min_by(
            fn
              {key, []} -> key
              {_, _} -> :infinity
            end,
            fn -> {64, []} end
          )

        new_map = Map.put(map, step_to_assign, [:assigned])

        workers =
          Map.put(workers, worker_to_use, {step_to_assign + seconds_added - 64, step_to_assign})

        {new_map, workers}
      end

      def finish_next_completed_task(map, workers) do
        # Next tasks to be finished
        {time_done, completed_steps} =
          workers
          |> Enum.reduce({:infinity, []}, fn
            {_key, {_time_left, nil}}, acc ->
              acc

            {_key, {time_left, on_step}}, {time, steps} ->
              cond do
                time_left < time -> {time_left, [on_step]}
                time_left == time -> {time, [on_step | steps]}
                true -> {time, steps}
              end
          end)

        # Move workers along
        workers =
          Enum.into(workers, %{}, fn {k, {time, step}} ->
            if step in completed_steps do
              {k, {max(0, time - time_done), nil}}
            else
              {k, {max(0, time - time_done), step}}
            end
          end)

        # Update steps so task is completed
        new_map =
          Enum.reduce(map, %{}, fn
            {k, v}, acc ->
              case k in completed_steps do
                true -> Map.delete(acc, k)
                false -> Map.put_new(acc, k, v -- completed_steps)
              end
          end)

        # Return new workers, new map and time that's been spent on this task
        {new_map, workers, time_done}
      end
    end