16
\$\begingroup\$

Given a list of positive integers, partition the list into two sublists such that the absolute value of the difference of the sums over the two sublists is minimal.
The output of the program should be the (non-negative) difference of these sums.

Examples:

[1,2,3]       -> 0  # [1,2], [3]
[2,3,5,7,11]  -> 0  # [2,5,7], [3,11]
[13,17,19,23] -> 0  # [13,23], [17,19]
[1,2,3,4]     -> 0  # [1,4], [2,3]
[2,2,2,3,3]   -> 0  # [2,2,2], [3,3]
[1,2,3,4,5]   -> 1  # [1,2,4], [3,5]
[1,2,3,4,5,6] -> 1  # [1,2,3,4], [5,6]
[1,1,2,5]     -> 1  # [1,1,2], [5]
[1,3,9,27]    -> 14 # [1,3,9], [27]

Rules

  • The sublists do not need to be contiguous
  • Every element of the list has to be in (exactly) one of the two sublists
  • The list can contain duplicate elements
  • You can assume that the list contains at least 3 elements
  • You are allowed to assume that the list is sorted (using any convenient ordering)
  • The ordering of two numbers should be the same for all lists
  • This is the shortest solution wins

related challenge

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Suggest [2,2,2,3,3] -> 0 \$\endgroup\$
    – att
    Nov 5, 2023 at 9:40
  • 1
    \$\begingroup\$ You say absolute values of the sums, but the sums are always positive. Do you mean the absolute value of the difference? \$\endgroup\$
    – Luis Mendo
    Nov 5, 2023 at 17:48
  • 2
    \$\begingroup\$ "Any convenient ordering", eh? Seems like the most convenient would be one which is ascending until the necessary split, like, from the examples, [3,1,2] or [2.5.7.3.11] or [17,19,13,23], etc. \$\endgroup\$ Nov 5, 2023 at 18:35
  • 1
    \$\begingroup\$ @DewiMorgan I clarified that the ordering should be independent of the numbers in the list, does this fix the problem \$\endgroup\$
    – bsoelch
    Nov 6, 2023 at 7:05
  • \$\begingroup\$ @bsoelch That's a really weird phrasing, since I can't think of any way to sort numbers in a list without using the numbers in the list. \$\endgroup\$ Nov 6, 2023 at 17:32

19 Answers 19

11
\$\begingroup\$

Python, 57 bytes

f=lambda A,B,*a:min((z:=[abs,f][a>()])(A+B,*a),z(A-B,*a))

Attempt This Online!

Takes splatted input. Input must have at least 2 elements.

How?

Recursively builds up all possible differences by successively adding or subtracting each element (except the first which is allowed to break symmetry).

\$\endgroup\$
10
\$\begingroup\$

05AB1E, 7 5 bytes

æOÂαß

Attempt this online! or try all testcases

Explanation

Utilizes the fact that 05AB1E's powerset builtin returns the sets in the same order as looking at the numbers \$0\$ - \$2^n-1\$ in binary reversed, so the opposite of each element when reversing is its complement.

æ        # all subsets of the input
O        # the sum of each
        # Bifurcated, push the reverse without popping
α        # take the absolute difference (vectorizes)
ß        # the minimum of that
\$\endgroup\$
7
\$\begingroup\$

K (ngn/k), 16 bytes

&//|/-:\+/:/+-:\

Try it online!

            +-:\    ± each
        +/:/        outer sum
   |/-:\            abs
&//                 min
\$\endgroup\$
5
\$\begingroup\$

Uiua, 10 bytes

Same idea as loopy walt's Python answer.

/↧⌵/(⊂⊃+-)

Try it!

/↧⌵/(⊂⊃+-)  # Function taking a vector from the stack and leaving a number
   /(    )  # Reduce the vector by ...
     ⊂      # Concatenate the results from ...
      ⊃+-   # both adding and subtracting the new value from all intermediate values.
  ⌵         # Take the Absolute Value of each number
/↧          # Reduce by Minimum
\$\endgroup\$
0
5
\$\begingroup\$

R, 56 bytes

f=\(x,s=0)`if`(any(x),f(x[-1],c(s,-s)+x[1]),min(abs(s)))

Attempt This Online!

A recursive function, partly inspired by @loopywalt’s Python answer so be sure to upvote that one too! Takes an integer vector and returns an integer.

An alternative non-recursive approach R, 60 57 bytes

\(x)min(abs((1:max(s<-2^seq(x))%o%(2/s)%/%1%%2*2-1)%*%x))

Attempt This Online!

This one avoids recursion, but uses an outer multiplication table and matrix multiplication.

Thanks to @Giuseppe for saving three bytes!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think you can get the non-recursive version down using %o% instead of outer but I'm on mobile and getting the parentheses just right is a nightmare. \$\endgroup\$
    – Giuseppe
    Nov 5, 2023 at 18:32
  • \$\begingroup\$ @Giuseppe, thanks, good spot \$\endgroup\$ Nov 5, 2023 at 19:26
5
\$\begingroup\$

JavaScript (Node.js), 55 bytes

f=([c,...x],y=0)=>c?1/Math.max(1/f(x,y+c),1/f(x,y-c)):y

Try it online!

-1B from tsh

\$\endgroup\$
1
  • \$\begingroup\$ f=([c,...x],y=0)=>c?1/Math.max(1/f(x,y+c),1/f(x,y-c)):y \$\endgroup\$
    – tsh
    Nov 6, 2023 at 5:51
4
\$\begingroup\$

Jelly, 7 bytes

żNŒp§AṂ

Try it online!

A monadic link that takes a list of integers and returns an integer. Works by zipping the original list with its negation, taking the Cartesian project, and finding the minimum absolute sum.

Alternative 7-byters and a 9-byter:

ŒP§ạU$Ṃ
ŒP§ḤạSṂ
LØ+ṗ×⁸§AṂ

The first two are variants on @CommandMaster’s 05AB1E answer. The third works similarly to my non-recursive R answer. Note the TIO link above includes all 4 versions.

\$\endgroup\$
4
\$\begingroup\$

Scala, 98 82 bytes

Saved 16 bytes thanks to @corvus_192


Golfed version. Try it online!

def?(l:Seq[Int],y:Int=0):Int=l match{case c::x=> ?(x,y+c)min?(x,y-c)case _=>y.abs}

Ungolfed version. Try it online!

object Main {
  def f(list: List[Int], y: Int = 0): Int = {
    list match {
      case c :: x => math.min(f(x, y + c), f(x, y - c))
      case Nil    => math.abs(y)
    }
  }

  def main(args: Array[String]): Unit = {
    println(f(List(1,2,3)))         // -> 0
    println(f(List(2,3,5,7,11)))    // -> 0
    println(f(List(13,17,19,23)))   // -> 0
    println(f(List(1,2,3,4)))       // -> 0
    println(f(List(1,2,3,4,5)))     // -> 1
    println(f(List(1,2,3,4,5,6)))   // -> 1
    println(f(List(1,1,2,5)))       // -> 1
    println(f(List(1,3,9,27)))      // -> 14
  }
}
\$\endgroup\$
1
  • \$\begingroup\$ 82 bytes: def?(l:Seq[Int],y:Int=0):Int=l match{case c::x=> ?(x,y+c)min?(x,y-c)case _=>y.abs} \$\endgroup\$
    – corvus_192
    Nov 5, 2023 at 16:29
3
\$\begingroup\$

Vyxal g, 31 bitsv2, 3.875 bytes

ṗṠḂε

Try it Online!

Bitstring:

1001111110100111110010001110010

Ports 05ab1e exactly, command for command.

Explained

ṗṠḂε­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‏​⁢⁠⁡‌­
ṗ     # ‎⁡Powerset, in infinite list friendly order
 Ṡ    # ‎⁢Vectorised sums
  Ḃ   # ‎⁣Bifurcated
   ε  # ‎⁤Absolute differences
# ‎⁢⁡The g flag returns the smallest item. 
💎

Created with the help of Luminespire.

\$\endgroup\$
3
\$\begingroup\$

Uiua, 18 bytes

/↧⌵-⇌.≐(/+▽)⋯⇡ⁿ⧻,2

Try it!

/↧⌵-⇌.≐(/+▽)⋯⇡ⁿ⧻,2
              ⁿ⧻,2  # 2 to the <length of input> power
             ⇡      # create a range from that number
            ⋯       # binary (vectorizing big-endian)
      ≐(   )        # tribute (apply (...) to each binary list and the input)
          ▽         # keep (forming an element of the power set of the input)
        /+          # sum
     .              # duplicate (the sums)
    ⇌               # reverse
  ⌵-                # absolute difference
/↧                  # minimum
\$\endgroup\$
3
\$\begingroup\$

Nekomata, 5 bytes

ŋ∑Aaṁ

Attempt This Online!

A port of @att's K (ngn/k) answer.

ŋ∑Aaṁ
ŋ       Optionally negate each element of the input
 ∑      Sum
  A     Absolute value
   a    All possible values
    ṁ   Minimum
\$\endgroup\$
3
\$\begingroup\$

J, 14 13 bytes

[:<./(+|@,-)/

Try it online!

A port of ovs's Uiua answer thanks to Bubbler. -1 thanks to att.

J, 18 bytes

[:<./[:|@,]+//@,.-

Try it online!

A port of att's nice K answer.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Porting ovs's Uiua answer instead gives 14 bytes [:<./[:|(+,-)/. \$\endgroup\$
    – Bubbler
    Nov 6, 2023 at 7:34
  • \$\begingroup\$ Nice, I had played around with that but was over-complicating it. \$\endgroup\$
    – Jonah
    Nov 6, 2023 at 7:46
  • 1
    \$\begingroup\$ [:|(+,-)/ -> (+|@,-)/ \$\endgroup\$
    – att
    Nov 6, 2023 at 8:14
3
\$\begingroup\$

Python, 86 bytes

-10 bytes by l4m2
-4 bytes thanks to tsh

def f(s,l={0}):
 for i in s:l|={i+j for j in l}
 return min(abs(a+a-sum(s))for a in l)

First time golfing in Python!

Attempt This Online!

\$\endgroup\$
2
2
\$\begingroup\$

Charcoal, 24 20 bytes

⊞υ⁰Fθ≔⁺υ⁺υιυI⌊↔⁻Σθ⊗υ

Try it online! Link is to verbose version of code. Explanation: Port of @mathscat's Python answer.

⊞υ⁰

Start with the sum of the empty sublist.

Fθ

Loop over the input list.

≔⁺υ⁺υιυ

Calculate the sums of the subsets including the current element and any subset of the previous elements and append those to the list of subset sums.

I⌊↔⁻Σθ⊗υ

Calculate the minimum difference between each subset and its complement, using the equation \$ | \sum (U \setminus A) - \sum A | = | \sum U - \sum A - \sum A | = | \sum U - 2 \sum A | \$.

Previous 24-byte solution:

I⌊↔⁻Σθ⊗EX²LθΣEθ×λ﹪÷ιX²μ²

Try it online! Link is to verbose version of code. Explanation:

     θ                      Input list
    Σ                       Take the sum
   ⁻                        Vectorised subtract
         ²                  Literal integer `2`
        X                   Raised to power
           θ                Input list
          L                 Length
       E                    Map over implicit range
              θ             Input list
             E              Map over elements
                λ           Current element
               ×            Multiplied by
                   ι        Outer value
                  ÷         Integer divided by
                     ²      Literal integer `2`
                    X       Raised to power
                      μ     Inner index
                 ﹪          Modulo
                       ²    Literal integer `2`
            Σ               Take the sum
      ⊗                     Doubled
  ↔                         Vectorised absolute
 ⌊                          Take the minimum
I                           Cast to string
                            Implicitly print

19 bytes using the newer version of Charcoal on ATO:

I⌊↔⁻Σθ⊗EX²Lθ↨¹×θ↨κ²

Attempt This Online! Link is to verbose version of code. Explanation:

   ⁻Σθ⊗EX²Lθ        As above
               θ    Input list
              ×     Zipped multiply with
                 κ  Current value
                ↨   Converted to base
                  ² Literal integer `2`
            ↨¹      Take the sum
I⌊↔                 As above

(Sum doesn't work on empty lists because it needs to know what type of list it's summing.)

\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 46 bytes

Prompts for vector of integers:

⌊/|(+/i×m)-+/(i←(b,n)⍴v)×~m←⍉(n⍴2)⊤⍳b←2*n←⍴v←⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

ŒṖ§ḅ-AṂ

A monadic Link that accepts a list of integers and yields the smallest partition difference.

Try it online!

How?

Creates all partitions then treats every other part as being in the first of the two sets. Calculates the difference by converting the sums of the parts from base one (which takes the negative of every other part-sum).

ŒṖ§ḅ-AṂ - Link: list of integers  e.g. [4,5,6]
ŒṖ      - all list partitions          [[[4],[5],[6]],[[4],[5,6]],[[4,5],[6]],[[4,5,6]]]
  §     - sums                         [[4,5,6],[4,11],[9,6],[15]]
   ḅ-   - from base -1                 [5,7,-3,15] i.e. 6-5+4=5 11-4=7 6-9=3 15=15
     A  - absolute values              [5,7,3,15]
      Ṃ - minimum                      3

Alternatives

ŒP§ạṚ$Ṃ - sum every subset absolute difference with its own reverse, minimum
żNŒp§AṂ - zip with negative, take the Cartesian product, get sums, absolute values, minimum
\$\endgroup\$
1
\$\begingroup\$

Excel, 106 bytes

=LET(
    a,A1#,
    b,ROWS(a),
    c,MOD(INT(SEQUENCE(2^b,,)/2^SEQUENCE(,b,)),2),
    MIN(ABS(MMULT(c,a)-MMULT(ABS(1-c),a)))
)

Input is spilled, vertical array in cell A1.

\$\endgroup\$
0
\$\begingroup\$

C (GCC), 66 bytes

A,B;d(a,n)int*a;{for(A=B=0;n--;)A<B?A+=a[n]:(B+=a[n]);a=abs(A-B);}

Attempt This Online!

-1 thanks to Arnauld.

A simple greedy algorithm.

The program uses a wide assortment of tricks:

  • K&R function declarations
  • Assumes that the input is sorted, per challenge specs.
  • Global variables assumed zero & permitted to omit the type specifier due to implicit int.
  • Implicit int in function declaration
  • ~i will check if i is not -1.
  • Ternary operator replaces an if.
  • A return statement is avoided by assuming -O0 and exploiting the load to a writing to rax, the return value register on x86.
\$\endgroup\$
3
  • \$\begingroup\$ Functions must be reusable and you cannot simply assume that A and B are reset to 0 between 2 calls. But you can save some bytes by getting rid of i, so I think this should work for 66 bytes. \$\endgroup\$
    – Arnauld
    Nov 5, 2023 at 17:04
  • 4
    \$\begingroup\$ Note that this algorithm fails for [2,2,2,3,3] anyway. \$\endgroup\$
    – Arnauld
    Nov 5, 2023 at 17:12
  • \$\begingroup\$ -3 bytes: A,B;d(a,n)int*a;{for(A=B=0;n--;*(A<B?&A:&B)+=a[n]);a=abs(A-B);} \$\endgroup\$
    – corvus_192
    Nov 5, 2023 at 20:34
0
\$\begingroup\$

Desmos, 86 bytes

f(l)=[abs(l.total-2total(mod(floor(2i/{2^{[1...L]}),2)l))fori=[1...2^L]].min
L=l.count

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.