Has My Pie Been Bisected?

Question

Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as "1 2 3 4" or [1, 2, 3, 4].

The numbers in the input list represent the slices of a full pie chart where each slice size is proportional to its corresponding number and all slices are arranged around the chart in the order given.

For example, the pie for 1 2 3 4 is:

The question your code must answer is: Is the pie chart ever bisected? That is, is there ever a perfectly straight line from one side of the circle to the other, splitting it symmetrically in two?

You need to output a truthy value if there is at least one bisector and output a falsy value if there are none.

In the 1 2 3 4 example there is a bisection between 4 1 and 2 3 so the output would be truthy.

But for input 1 2 3 4 5 there is no bisector so the output would be falsy:

Additional Examples

Arranging numbers differently may remove bisectors.
e.g. 2 1 3 4 → falsy:

If only one number is in the input list the pie is not bisected.
e.g. 10 → falsy:

There may be multiple bisectors. As long as there are more than zero the output is truthy.
e.g. 6 6 12 12 12 11 1 12 → truthy: (there are 3 bisectors here)

Bisections may exist even if they are not visually obvious.
e.g. 1000000 1000001 → falsy:

e.g. 1000000 1000001 1 → truthy:

(Thanks to nces.ed.gov for generating the pie charts.)

Test Cases

Truthy
1 2 3 4
6 6 12 12 12 11 1 12
1000000 1000001 1
1 2 3
1 1
42 42
1 17 9 13 2 7 3
3 1 2
10 20 10

Falsy
1 2 3 4 5
2 1 3 4
10
1000000 1000001
1
1 2
3 1 1
1 2 1 2 1 2
10 20 10 1

Scoring

The shortest code in bytes wins. Tiebreaker is earlier answer.

Answer 1

J, 18 bytes

5 bytes thanks to Dennis.

+/e.[:,/2*+/\-/+/\

@HelkaHomba: Nope.

Usage

>> f =: +/e.[:,/2*+/\-/+/\
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic  =: +/\-/+/\
doubled_bm   =: 2 * black_magic
flatten      =: ,/
sum          =: +/
is_member_of =: e.
f =: sum is_member_of monadic flatten doubled_bm

---

Previous 23-byte version:

[:+/[:+/+/=+:@-/~@(+/\)

Usage

>> f =: [:+/[:+/+/=+:@-/~@(+/\)
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic =: -/~@(+/\)
double      =: +:
equals      =: =
sum         =: +/
monadic     =: [:
of          =: @
f =: monadic sum monadic sum (sum equals double of black_magic)

---

Explanation

The sum of all substrings is calculated by the black_magic. The +/\ calculate the partial sums.

For example, a b c d becomes a a+b a+b+c a+b+c+d.

The -/~ then constructs a subtraction table based on the input, so x y z becomes:

x-x x-y x-z
y-x y-y y-z
z-x z-y z-z

When applied to a a+b a+b+c a+b+c+d, the result would be:

    0  -b -b-c -b-c-d
    b   0   -c   -c-d
  b+c   c    0     -d
b+c+d c+d    d      0

This calculated the sums of all the substrings which does not contain a.

This guarantees to be enough, since if one bisection contains a, the other bisection will not contain a and also will not wrap around.

Answer 2

Jelly, 9 8 bytes

Ḥ+\©_Sf®

Return a non-empty list (truthy) or an empty list (falsy). Try it online! or verify all test cases.

How it works

Ḥ+\©_Sf®  Main link. Argument: A (list)

Ḥ         Double all integers in A.
 +\       Take the cumulative sum of 2A.
   ©      Copy; store the result in the register.
    _S    Subtract the sum of A from each partial sum of 2A.
      f®  Filter; intersect this list with the list in the register.

Answer 3

Julia, 34 30 29 bytes

!x=sum(x)∈cumsum!(x,2x).-x'

Thanks to @GlenO for golfing off 1 byte!

Try it online!

How it works

After storing the cumulative sum of 2x in x, we subtract the row vector x' from the column vector x, yielding the matrix of all possible differences. Essentially, this computes the sums of all adjacent subarrays of x that do not contain the first value, their negatives, and 0's in the diagonal.

Finally, we test if the sum of the original array x belongs to the generated matrix. If this is the case, the sum of at least one of the adjacent sublists is equal to exactly halve of the sum of the entire list, meaning that there is at least one bisector.

Answer 4

Python 2, 64 bytes

f=lambda l,s=0:l>[]and(sum(l)==s)|f(l[1:],s+l[0])|f(l,s+l.pop())

Recursively tries to remove elements from the front or end until the sum of what remains equals the sum of what was deleted, which is stored is s. Takes time exponential in the list length.

Dennis saved 3 bytes with pop.

Answer 5

Haskell, 41 bytes

f l=elem(sum l/2)$scanr(:)[]l>>=scanl(+)0

The idea is to check whether there is a sublist of l whose sum equals sum l/2. We generate the sums of these sublists as scanr(:)[]l>>=scanl(+)0. Let's look at how this works with l=[1,2,3]

>> scanr(:)[]l
[[1,2,3],[2,3],[3],[]] 
-- the suffixes of l

>> scanl(+)0 [2,3,4]
[0,2,5,9]
-- the cumulative sums of the input

>> scanr(:)[]l>>=scanl(+)0
[0,1,3,6,0,2,5,0,3,0]
-- the cumulative sums of the suffixes of l, flattened to a single list

Old 43 bytes:

f l|c<-scanl1(+)l=elem(sum l/2)$(-)<$>c<*>c

Generates the list c of cumulative sums. Then, checks if any two of these sums differ by sum l/2 by checking if it is an element of the list of differences (-)<$>c<*>c.

Answer 6

Pyth, 10 9 bytes

}sQmysd.:

Test it in the Pyth Compiler.

How it works

       .:  Generate the list of all adjacent sublists.
   m       Map over the result:
     sd       Add the integers of the sublist.
    y         Double the sum.
 sQ        Compute the sum of the input.
}          Check if it belongs to the list of doubled sublist sums.

Answer 7

Python 2, 76 74 70 66 bytes

def f(x):n=sum(x);print n in[2*sum(x[k/n:k%n])for k in range(n*n)]

Thanks to @xnor for golfing off 4 8 bytes!

Test it on Ideone. (larger test cases excluded)

Answer 8

Actually, 21 bytes

;Σ@2*;lR@τ╗`╜V♂Σi`Míu

Try it online!

This program prints out a 0 for false cases, and a positive integer for true cases.

Explanation:

;Σ@2*;lR@τ╗`╜V♂Σi`Míu
;Σ                     sum of copy of input
  @2*                  double values in other copy
     ;lR               copy, range(1, len(input)+1)
        @τ             append other copy to itself
          ╗            save in reg0
           `╜V♂Σi`M    map: generate cyclic cumulative sums
                   íu  1-based index of sum of input (0 if not found)

Non-competing version, 10 bytes

;Σ@2*σ;)-∩

Try it online!

This program outputs an empty list for false cases and a non-empty list otherwise. It is essentially a port of Dennis's Jelly answer. It is non-competing because the cumulative sum and vectorized difference functionality post-date the challenge.

Explanation:

;Σ@2*σ;)-∩
;Σ          sum of copy of input
  @2*       multiply values in other copy by 2
     σ;     two copies of cumulative sum
       )-   subtract sum of input from each element in one copy
         ∩  set intersection with other copy

Answer 9

MATL, 10 bytes

EYst!-Gs=z

The output is the number of bisectors.

Try it online!

Explanation

Same approach as Dennis' Julia answer.

E       % Implicit input. Multiply by 2 element-wise 
Ys      % Cumulative sum 
t!-     % Compute all pairwise differences. Gives a 2D array 
Gs      % Sum of input 
=       % Test for equality, element-wise 
z       % Number of nonzero elements. Implicit display 

Answer 10

Ruby, 60 53 bytes

->a{a.any?{r=eval a*?+;a.rotate!.any?{|i|0==r-=2*i}}}

Generates all possible partitions by taking every rotation of the input array and then taking all slices of length 1..n, where n is the size of the input array. Then checks if there exists any partition with a sum half the total sum of the input array.

Answer 11

Python 2, 47 bytes

k=t=1
for x in input():t<<=x;k|=t*t
print k&k/t

Try it online!

I'm back 2.75 years later to beat my old solution by over 25% using a new method.

This 1-byte longer version is a little clearer.

k=t=0
for x in input():t+=x;k|=4**t
print k&k>>t

Try it online!

The idea is to store the set of cumulative sums t as bits of k, setting bit 2*t to indicate that t is a cumulative sum. Then, we check if any two cumulative sums differ by half the list sum (final t) by bit-shifting k this much and doing bitwise & with the original to see the result is nonzero (truthy).

Answer 12

JavaScript (ES6), 83 bytes

a=>a.map(_=>a.slice(--n).map(m=>s.push(t+=m),t=0),s=[],n=a.length)&&s.includes(t/2)

Generates all possible sums, then checks to see whether half of the last sum (which is the sum of the whole list) appears in the list. (Generating the sums in the slightly awkward order to arrange for the sum I need to be last saves 4 bytes.)

Answer 13

Dyalog APL, 12 bytes

+/∊2×+\∘.-+\

Test it with TryAPL.

How it works

+/∊2×+\∘.-+\  Monadic function train. Right argument: y (vector)

     +\   +\  Yield the cumulative sum of y.
       ∘.-    Compute all differences of all partial sums.
              This computes the sums of all adjacent subvectors of y that do not
              contain the first value, their negatives, and 0's in the diagonal.
   2×         Multiply all differences by 2.
+/            Yield the sum of y.
  ∊           Test for membership.

Answer 14

Brachylog, 6 bytes

sj+~+?

Try it online!

Outputs through success or failure, printing true. or false. if run as a program.

s         A contiguous sublist of the input
 j        with all of its items duplicated
  +       sums to
   ~+     the sum of the elements of
     ?    the input.

Answer 15

C, 161 145 129 bytes

• saved few bytes thanks to @LeakyNun
• saved few bytes thanks to @ceilingcat

i;j;k;t;r;s;f(x,n)int*x;{for(t=i=k=r=0;i<n;)t+=x[i++];for(;++k<n;i=n)for(;i--;r|=2*s==t)for(s=0,j=i;j<i+k;)s+=x[j++%n];return r;}

Ungolfed try online

int f(int*x,int n)
{
    int t=0;

    for(int i=0;i<n;i++)
    {
        t += x[i];
    }

    for(int k=1;k<n;k++) // subset-size
    {
        for(int i=0,s;i<n;i++) // where to start
        {
            s=0;

            for(int j=i;j<i+k;j++) // sum the subset
            {
                s+=x[j%n];
            }

            if(2*s==t) return 1; // TRUE
        }
    }

    return 0; // FALSE
}

Answer 16

APL, 25 chars

Assuming the list is given in X ← 1 2 3 4.

(+/X)∊∘.{2×+/⍺↑⍵↓X,X}⍨⍳⍴X←⎕

Explanation:

First note that APL evaluates form right to left. Then:

• X←⎕ takes the user input and stores it in X

• ⍴X gives the length of X

• ⍳⍴X the numbers from 1 to ⍴X

• The ⍺ and ⍵ in {2×+/⍺↑⍵↓X,X} are the left and right argument to a dyadic function we are defining inside the braces.

  • Now for the ⍺↑⍵↓X,X part: X,X just concatenates X with itself; ↑ and ↓ are take and drop.
  • +/ reduces/folds + over the list on its right

  So 2 {2×+/⍺↑⍵↓X,X} 1 = 2×+/2↑1↓X,X = 2×+/2↑1↓1 2 3 4 1 2 3 4 =

  = 2×+/2↑2 3 4 1 2 3 4 = 2×+/2 3 = 2×5 = 10.

• ∘.brace⍨idx is just idx ∘.brace idx. (⍨ is the diagonal map; ∘. is the outer product)

  So this gives us a ⍴X by ⍴X matrix which contains twice the sums of all connected sublists.

   4  6  8  2
  10 14 10  6
  18 16 14 12
  20 20 20 20
  

  The last thing we have to do is to check if the sum of X is somewhere inside this matrix.

• Which we do with (+/X)∊matrix.

Answer 17

APL(NARS), chars 95, bytes 190

{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}

Consider one array of input of 4 elements: 1 2 3 4. How we can choose the useful for this exercise partition of that set? Afther some think the partition of these 4 elements we can use are descrived in the binary number on the left:

0001,0010,0100,1000 2^(0..4) 1 2 4  8 
0011,0110,1100,                3 6 12
0111,1110,                       7 14
1111                               15

(1001 or 1011 ecc could be in that set but already we have 0110 and 0100 ecc) so one hat just to write one function that from the number of element of the input array build these binary numbers... it would be:

c←{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}

that from input 1 2 4 8 [2^0..lenBytesArgument-1] find 3 6 12, 7 14, 15; so find binary of these numbers and using them find the right partitions of the input array...I tested c function only for that input 4 elements, but seems it is ok for other number of elements...

test:

  f←{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}
  f¨(1 2 3 4)(6 6 12 12 12 11 1 12)(1000000 1000001 1)(1 2 3)(1 1)(42 42)
1 1 1 1 1 1 
  f¨(1 2 3 4 5)(2 1 3 4)(,10)(1000000 1000001)(,1)(1 2)(3 1 1)
0 0 0 0 0 0 0 

Answer 18

Haskell, 68 bytes

f l|x<-[0..length l]=any(sum l==)[2*(sum$take a$drop b l)|a<-x,b<-x]

The function f first creates a list of the sums of all the possible slices of the given list. Then it compares to the total sum of list elements. If we get at some point half of the total sum, then we know that we've got a bisection. I'm also using the fact that if you take or drop more elements than there are in the list, Haskell does not throw an error.

Answer 19

Mathematica, 48 bytes

!FreeQ[Outer[Plus,#,-#],Last@#/2]&@Accumulate@#&

Anonymous function, similar in action to the numerous other answers.

Outer[Plus, #, -#], when acting on Accumulate@# (which in turn acts on the input list, giving a list of successive totals) generates essentially the same table, as at the bottom of Leaky Nun's answer.

!FreeQ[..., Last@#/2] checks if (Last@#)/2 is not absent from the resulting table, and Last@# is the last of the successive totals, i.e. the sum of all elements of the input list.

If this answer is somewhat interesting, it is not because of a new algorithm, but more about the tricks specific to Mathematica; e.g. !FreeQ is nice, compared to MemberQ, since it does not require a flattening of the table it checks and it saves a byte.