I implemented the solution with subset-sum and dynamic programming, though I’m not a dynamic programming expert
I’m using the process dictionary as the memo.
defmodule PP.Impls.Aetherus do
@spec solve([pos_integer()]) ::
{
{partition1_sum :: non_neg_integer(), partition2_sum :: non_neg_integer()},
{partition1_length :: non_neg_integer(), partition2_length :: non_neg_integer()},
{partition1 :: [pos_integer()], partition2 :: [pos_integer()]}
}
def solve(nums) do
sum = Enum.sum(nums)
len = length(nums)
sum_target = div(sum, 2)
len_target = div(len, 2)
{sum_diff, len_diff, partition1} =
Task.async(fn ->
closest_subset_sum(Enum.with_index(nums), sum_target, len_target)
end)
|> Task.await(:infinity)
partition2 = nums |> List.myers_difference(partition1) |> Keyword.get_values(:del) |> List.flatten()
{
{sum_target + sum_diff, sum - sum_target - sum_diff},
{len_target + len_diff, len - len_target - len_diff},
{partition1, partition2}
}
end
@spec closest_subset_sum([pos_integer()], non_neg_integer(), non_neg_integer()) ::
{integer(), integer(), [pos_integer()]}
defp closest_subset_sum([], sum_target, length_target) do
{-sum_target, -length_target, []}
end
defp closest_subset_sum([{h, i} | t], sum_target, length_target) do
key = {i, sum_target, length_target}
case Process.get(key) do
solution when solution != nil ->
solution
nil ->
{sum_diff1, len_diff1, solution1} =
closest_subset_sum(t, sum_target - h, length_target - 1)
{sum_diff2, len_diff2, solution2} = closest_subset_sum(t, sum_target, length_target)
cond do
abs(sum_diff1) < abs(sum_diff2) ->
{sum_diff1, len_diff1, [h | solution1]}
abs(sum_diff1) > abs(sum_diff2) ->
{sum_diff2, len_diff2, solution2}
abs(len_diff1) <= abs(len_diff2) ->
{sum_diff1, len_diff1, [h | solution1]}
true ->
{sum_diff2, len_diff2, solution2}
end
|> tap(fn solution -> Process.put(key, solution) end)
end
end
end
Tests failed:
1) test impl_aetherus: [3, 1, 1, 2, 2, 1] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[1, 1, 3], [1, 2, 2], 5, 5} == PP.impl_aetherus([3, 1, 1, 2, 2, 1])
left: {[1, 1, 3], [1, 2, 2], 5, 5}
right: {[3, 1, 1], [2, 2, 1], 5, 5}
stacktrace:
test/pp_test.exs:36: (test)
2) test impl_aetherus: [2, 3, 10, 5, 8, 9, 7, 3, 5, 2] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27} == PP.impl_aetherus([2, 3, 10, 5, 8, 9, 7, 3, 5, 2])
left: {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27}
right: {[2, 3, 10, 5, 7], [8, 9, 3, 5, 2], 27, 27}
stacktrace:
test/pp_test.exs:36: (test)
3) test impl_aetherus: [1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185} ==
PP.impl_aetherus([1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100])
left: {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185}
right: {[1, 3, 5, 11, 65, 100], [4, 7, 8, 9, 74, 83], 185, 185}
stacktrace:
test/pp_test.exs:36: (test)
4) test impl_aetherus: [6000, 3000, 480, 240, 120] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[6000], [120, 240, 480, 3000], 6000, 3840} == PP.impl_aetherus([6000, 3000, 480, 240, 120])
left: {[6000], [120, 240, 480, 3000], 6000, 3840}
right: {[6000], [3000, 480, 240, 120], 6000, 3840}
stacktrace:
test/pp_test.exs:36: (test)
.
5) test impl_aetherus: [1, 1, 1, 1, 1, 1, 1, 50, 50, 100] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[1, 1, 1, 1, 100], [1, 1, 1, 50, 50], 104, 103} ==
PP.impl_aetherus([1, 1, 1, 1, 1, 1, 1, 50, 50, 100])
left: {[1, 1, 1, 1, 100], [1, 1, 1, 50, 50], 104, 103}
right: {[1, 1, 1, 50, 50], [1, 1, 1, 1, 100], 103, 104}
stacktrace:
test/pp_test.exs:36: (test)
..
6) test impl_aetherus: [1, 2, 3, 4, 5] (PPTest)
test/pp_test.exs:35
Assertion with == failed
code: assert {[1, 2, 5], [3, 4], 8, 7} == PP.impl_aetherus([1, 2, 3, 4, 5])
left: {[1, 2, 5], [3, 4], 8, 7}
right: {[2, 5], [1, 3, 4], 7, 8}
stacktrace:
test/pp_test.exs:36: (test)
....
Finished in 0.04 seconds (0.00s async, 0.04s sync)
14 tests, 6 failures