defmodule InPlace.ExactCoverTest do
  use ExUnit.Case

  alias InPlace.ExactCover

  require Logger

  describe "ExactCover" do
    test "Knuth and Wikipedia instances" do
      Enum.each(
        [knuth_instance(), wiki_instance()],
        fn instance ->
          assert_instance(instance)
        end
      )
    end

    test "Instance for Langford numbers (Knuth)" do
      assert_instance(langford3_instance())
    end

    test "Instance with no exact cover" do
      options = [
        [1, 2, 3],
        [2, 3, 4]
      ]

      ExactCover.solve(options,
        solution_handler: async_solution_handler(options)
      )

      refute_received(_, timeout: 100)
    end

    defp async_solution_handler(instance) do
      fn solution ->
        send(
          self(),
          Enum.map(solution, fn option_id ->
            Enum.at(instance, option_id)
          end)
        )
      end
    end

    defp knuth_instance() do
      {
        [
          [:c, :e, :f],
          [:a, :d, :g],
          [:b, :c, :f],
          [:a, :d],
          [:b, :g],
          [:d, :e, :g]
        ],
        [
          [[:b, :g], [:a, :d], [:c, :e, :f]]
        ]
      }
    end

    defp wiki_instance() do
      ##  https://en.wikipedia.org/wiki/Exact_cover#Detailed_example
      {
        [
          [1, 4, 7],
          [1, 4],
          [4, 5, 7],
          [3, 5, 6],
          [2, 3, 6, 7],
          [2, 7]
        ],
        [
          [[3, 5, 6], [2, 7], [1, 4]]
        ]
      }
    end

    defp langford3_instance() do
      {[
         ~w{1 s1 s3},
         ~w{1 s2 s4},
         ~w{1 s3 s5},
         ~w{1 s4 s6},
         ~w{2 s1 s4},
         ~w{2 s2 s5},
         ~w{2 s3 s6},
         ~w{3 s1 s5},
         ~w{3 s2 s6}
       ],
       [
         [["1", "s2", "s4"], ["2", "s3", "s6"], ["3", "s1", "s5"]],
         [["1", "s3", "s5"], ["2", "s1", "s4"], ["3", "s2", "s6"]]
       ]}
    end

    defp assert_instance(instance) do
      {options, expected_solution} = instance

      ExactCover.solve(options,
        solution_handler: async_solution_handler(options)
      )

      received = flush()

      assert Enum.all?(
               Enum.zip(received, expected_solution),
               fn {r, e} -> Enum.sort(List.flatten(r)) == Enum.sort(List.flatten(e)) end
             )

      assert_exact_cover(options, received)
    end

    defp assert_exact_cover(options, solutions) do
      Enum.each(solutions, fn solution ->
        combined =
          Enum.reduce(tl(solution), MapSet.new(hd(solution)), fn option, acc ->
            option_set = MapSet.new(option)
            assert MapSet.disjoint?(option_set, acc)
            MapSet.union(option_set, acc)
          end)

        assert MapSet.new(List.flatten(options)) == combined
      end)
    end

    def flush() do
      flush([])
    end

    def flush(acc) do
      receive do
        msg -> flush([Enum.sort(msg) | acc])
      after
        0 -> acc
      end
    end
  end
end