Algorithm challenge: the Partition Problem

Chat & Discussions Discussions
3

This problem has a well known solution, you just keep track of each partition size and add the biggest remaining part to the smallest size. The basic implementation with recursive functions will already be optimized.

You can add streams and stuff but it will only be slower.

I propose to change the tests with a more generic specification, that is asking for a number of partitions instead of always having two partitions.

I tested with the code below for two partitions, but this is failing the tests as the tests expects the specific results of your implementation. I would pass if the tests only asserted the expected sums but not lists items.

  def impl_lud(list) when is_list(list) do
    # solve the problem
    result = impl_lud(list, 2)

    # comply with the shape expected from the test
    [{left_list, left_sum}, {right_list, right_sum}] = Enum.sort_by(result, &(-1 * elem(&1, 1)))
    {left_list, right_list, left_sum, right_sum}
  end

  defp impl_lud(list, parts) do
    partitions = List.duplicate({[], 0}, parts)

    list
    |> Enum.sort(:desc)
    |> Enum.reduce(partitions, &impl_lud_reducer/2)
  end

  defp impl_lud_reducer(x, [{partition, size} | partitions]) do
    impl_lud_insert({[x | partition], size + x}, partitions)
  end

  defp impl_lud_insert({_, size} = p, [{_, smaller} = candidate | rest]) when smaller < size do
    [candidate | impl_lud_insert(p, rest)]
  end

  defp impl_lud_insert(p, rest) do
    [p | rest]
  end

With those errors:


  1) test impl_lud: [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_lud([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, 7, 9, 65, 100], [4, 5, 8, 11, 74, 83], 185, 185}
     stacktrace:
       test/pp_test.exs:36: (test)

.....

  2) test impl_lud: [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_lud([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, 5, 8, 9], [2, 3, 5, 7, 10], 27, 27}
     stacktrace:
       test/pp_test.exs:36: (test)

..

  3) test impl_lud: [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_lud([3, 1, 1, 2, 2, 1])
     left:  {[1, 1, 3], [1, 2, 2], 5, 5}
     right: {[1, 2, 2], [1, 1, 3], 5, 5}
     stacktrace:
       test/pp_test.exs:36: (test)
2 Likes