43
\$\begingroup\$

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:

1 2 3 4 example

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:

1 2 3 4 5 example

Additional Examples

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

2 1 3 4 example

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

10 example

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)

6 6 12 12 12 11 1 12 example

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

1000000 1000001 example

e.g. 1000000 1000001 1 → truthy:

1000000 1000001 1 example

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

Improve this question
\$\endgroup\$
4
  • 30
    \$\begingroup\$ I believe you mean piesected? \$\endgroup\$ Commented Jun 4, 2016 at 6:02
  • \$\begingroup\$ @HelkaHomba, can you rearrange the sectors to make it work, and is that what you meant by "arranging numbers differently may remove bisectors"? \$\endgroup\$ Commented Jun 6, 2016 at 15:40
  • \$\begingroup\$ @SolomonUcko You may not rearrange the sectors. \$\endgroup\$ Commented Jun 6, 2016 at 20:48
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Commented Jun 7, 2016 at 10:48

21 Answers 21

Reset to default
12
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ With some restructuring, you can get to 13 bytes: +/e.&,2*+/\\. \$\endgroup\$ Commented Jun 4, 2016 at 15:35
10
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 15
    \$\begingroup\$ Let's watch as Dennis gives 5 answers before anyone else gives one. \$\endgroup\$ Commented Jun 4, 2016 at 4:53
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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()) \$\endgroup\$ Commented Jun 4, 2016 at 8:05
4
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I realized you can do n=sum(x) to do n in ...; it doesn't hurt to use a larger value for n. \$\endgroup\$ Commented Jun 8, 2016 at 9:50
  • \$\begingroup\$ Ooh, that's clever. Thank you! \$\endgroup\$ Commented Jun 8, 2016 at 16:06
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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 }
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 4, 2016 at 13:17
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 4, 2016 at 22:18
  • \$\begingroup\$ @MartinEnder It certainly looks like it'd work, but I'm on 10.2, so that's what I have \$\endgroup\$ Commented Jun 4, 2016 at 23:33
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.