Packages
inplace
0.2.1
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
test/algorithms/exact_cover_test.exs
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 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 assert_instance(instance) do
{options, expected_solution} = instance
ExactCover.solve(options,
solution_handler: async_solution_handler(options)
)
received =
receive do
msg -> msg
end
assert Enum.sort(received) == Enum.sort(expected_solution)
assert_exact_cover(options, received)
end
defp assert_exact_cover(options, solution) do
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
end