Has My Pie Been Bisected?

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:

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.

• I believe you mean piesected? Jun 4, 2016 at 6:02
• @HelkaHomba, can you rearrange the sectors to make it work, and is that what you meant by "arranging numbers differently may remove bisectors"? Jun 6, 2016 at 15:40
• @SolomonUcko You may not rearrange the sectors. Jun 6, 2016 at 20:48
• Only [2 1 3 4] of the false cases has to actually be evaluated. The other false cases are easily rejected because their sum is odd (or their length is < 2). Jun 7, 2016 at 10:48

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         =: +/
of          =: @


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.

• With some restructuring, you can get to 13 bytes: +/e.&,2*+/\\. Jun 4, 2016 at 15:35

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.


Julia, 3430 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.

• Let's watch as Dennis gives 5 answers before anyone else gives one. Jun 4, 2016 at 4:53

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.

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.

• A weird alternative that gives lists: f=lambda l,s=0:l and(sum(l)==s)*l+f(l[1:],s+l[0])+f(l,s+l.pop())
– xnor
Jun 4, 2016 at 8:05

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.


Actually, 21 bytes

;Σ@2*;lR@τ╗╜V♂ΣiMíu


Try it online!

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

Explanation:

;Σ@2*;lR@τ╗╜V♂ΣiMí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♂ΣiM    map: generate cyclic cumulative sums


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


Python 2, 767470 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)

• I realized you can do n=sum(x) to do n in ...; it doesn't hurt to use a larger value for n.
– xnor
Jun 8, 2016 at 9:50
• Ooh, that's clever. Thank you! Jun 8, 2016 at 16:06

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).

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


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.

Vyxal, 6 bytes

¦Dt½-∩


Try it Online!

As in Jelly, a list is falsy iff it is empty.

¦         Push the cumulative sums
D        three times.
t       Take the last one,
½      halve it,
-     subtract it from each of the cumulative sums,
∩    and take the intersection of the differences and the cumulative sums.


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.)

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.


Jelly, 6 bytes

ÄḤf_¥S


Try it online!

Jelly has gained a single-byte builtin for cumulative sums since Dennis posted his solution, making it trivial to golf to 7 bytes. Turns out there's a lot of creative ways to tie 7, but to hit 6 all it takes is restructuring it with a dyadic chain.

 Ḥ        Double
Ä         the cumulative sums,
f       then filter them by membership in
_¥     the differences between them and
S    the total sum.


As Dennis presumably observed, a difference of partial sums is the sum of a substring, and if a difference of partial sums is half the total sum, the difference of a partial sum and the total sum is another partial sum.

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.

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.

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.


C, 161145 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
}

• Perhaps you can save some bytes by moving the declarations of the variables to the first level, and changing i<n;i++ to i++<n (though you may need to deal with some offsets. Jun 4, 2016 at 13:17

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.

• I think !FreeQ[2Tr/@Subsequences@#,Tr@#]& should work, but I won't have 10.4 available to test it for the next 10 days or so. Jun 4, 2016 at 22:18
• @MartinEnder It certainly looks like it'd work, but I'm on 10.2, so that's what I have Jun 4, 2016 at 23:33

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