# Algorithm challenge: the Partition Problem

**URL:** <https://forum.elixirforum.com/t/algorithm-challenge-the-partition-problem/36939>\
**Category:** Discussions\
**Tags:** algorithm\
**Created:** [January 18, 2021, 6:38pm UTC](https://forum.elixirforum.com/t/algorithm-challenge-the-partition-problem/36939 "2021-01-18T18:38:36Z")\
**Posts on this page:** 1\
**Showing post:** 3

<div class="post-metadata">

**Author:** ![lud](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/lud/32/14382_2.png) [@lud](https://forum.elixirforum.com/u/lud)\
**Post date:** [February 7, 2022, 10:17am UTC](https://forum.elixirforum.com/t/algorithm-challenge-the-partition-problem/36939/3 "2022-02-07T10:17:57Z")

</div>

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.

```elixir
  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:

```elixir

  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)

```

---

_[View the full topic](https://forum.elixirforum.com/t/algorithm-challenge-the-partition-problem/36939)._