Escriba un programa o función que incluya una lista no vacía de enteros positivos. Puede suponer que se ingresa en un formato razonable y conveniente como "1 2 3 4"o [1, 2, 3, 4].

Los números en la lista de entrada representan los segmentos de un gráfico circular completo donde cada tamaño de segmento es proporcional a su número correspondiente y todos los sectores se organizan alrededor del gráfico en el orden dado.

Por ejemplo, el pastel para 1 2 3 4es:

La pregunta que debe responder su código es: ¿alguna vez se divide el gráfico circular ? Es decir, ¿hay alguna vez una línea perfectamente recta desde un lado del círculo al otro, dividiéndola simétricamente en dos?

Es necesario para la producción de un Truthy valor si existe al menos una bisectriz y la salida de un Falsy valor si no hay ninguno .

En el 1 2 3 4ejemplo hay una bisección entre 4 1y, 2 3por lo tanto, el resultado sería verdadero.

Pero para la entrada 1 2 3 4 5no hay bisectriz, por lo que la salida sería falsa:

Ejemplos adicionales

Organizar números de manera diferente puede eliminar las bisectrices.
por ejemplo, 2 1 3 4falso:

Si solo hay un número en la lista de entrada, el pastel no está dividido en dos.
por ejemplo, 10falso:

Puede haber múltiples bisectrices. Mientras haya más de cero, la salida es verdadera.
ej. 6 6 12 12 12 11 1 12→ verdad: (hay 3 bisectrices aquí)

Las bisecciones pueden existir incluso si no son visualmente obvias.
por ejemplo, 1000000 1000001falso:

p. ej. 1000000 1000001 1→ verdad:

(Gracias a nces.ed.gov por generar los gráficos circulares).

Casos de prueba

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

Tanteo

El código más corto en bytes gana. Tiebreaker es la respuesta anterior.

J, 18 bytes

5 bytes gracias a Dennis.

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

@HelkaHomba : No.

Uso

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

Sin golf

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

Versión anterior de 23 bytes:

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

Uso

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

Sin golf

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

Explicación

Black_magic calcula la suma de todas las subcadenas. El +/\calcular las sumas parciales.

Por ejemplo, se a b c dconvierte a a+b a+b+c a+b+c+d.

El -/~entonces construye una tabla de sustracción basado en la entrada, por lo que x y zse convierte en:

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

Cuando se aplica a a a+b a+b+c a+b+c+d, el resultado sería:

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

Esto calculó las sumas de todas las subcadenas que no contiene a.

Esto garantiza que sea suficiente, ya que si una bisección contiene a, la otra bisección no contendrá ay tampoco se envolverá.

Jalea , 9 8 bytes

Ḥ+\©_Sf®

Devuelve una lista no vacía (verdad) o una lista vacía (falsedad). Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

Ḥ+\©_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, 34 30 29 bytes

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

¡Gracias a @GlenO por jugar golf en 1 byte!

Pruébalo en línea!

Cómo funciona

Después de almacenar la suma acumulativa de 2x en x , restamos el vector de fila x ' del vector de columna x , produciendo la matriz de todas las diferencias posibles. Esencialmente, esto calcula las sumas de todas las subcadenas adyacentes de x que no contienen el primer valor, sus negativos y los 0 en la diagonal.

Finalmente, probamos si la suma de la matriz original x pertenece a la matriz generada. Si este es el caso, la suma de al menos una de las sublistas adyacentes es igual a exactamente la mitad de la suma de la lista completa, lo que significa que hay al menos una bisectriz.

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

Recurrentemente intenta eliminar elementos del frente o del final hasta que la suma de lo que queda sea igual a la suma de lo que se eliminó, lo que se almacena es s. Toma tiempo exponencial en la longitud de la lista.

Dennis guardó 3 bytes con pop.

Haskell, 41 bytes

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

La idea es verificar si hay una sublista de lcuya suma sea igual sum l/2. Generamos las sumas de estas sublistas como scanr(:)[]l>>=scanl(+)0. Veamos cómo funciona esto conl=[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

Antiguos 43 bytes:

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

Genera la lista cde sumas acumulativas. Luego, verifica si dos de estas sumas difieren sum l/2verificando si es un elemento de la lista de diferencias (-)<$>c<*>c.

Pyth, 10 9 bytes

}sQmysd.:

Pruébelo en el compilador Pyth .

Cómo funciona

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

En realidad, 21 bytes

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

Pruébalo en línea!

Este programa imprime un 0para casos falsos y un entero positivo para casos verdaderos.

Explicación:

;Σ@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)

Versión no competitiva, 10 bytes

;Σ@2*σ;)-∩

Pruébalo en línea!

Este programa genera una lista vacía para casos falsos y una lista no vacía de lo contrario. Es esencialmente un puerto de la respuesta de Dennis's Jelly . No es competitiva porque la suma acumulativa y la funcionalidad de diferencia vectorizada son posteriores al desafío.

Explicación:

;Σ@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, 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)]

¡Gracias a @xnor por jugar golf en 4 8 bytes!

Pruébalo en Ideone . (casos de prueba más grandes excluidos)

MATL , 10 bytes

EYst!-Gs=z

La salida es el número de bisectrices.

Pruébalo en línea!

Explicación

El mismo enfoque que la respuesta de Dennis a Julia .

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 

Rubí, 60 60 53 bytes

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

Genera todas las particiones posibles tomando cada rotación de la matriz de entrada y luego tomando todas las rebanadas de longitud 1 .. n, donde nes el tamaño de la matriz de entrada. Luego verifica si existe alguna partición con una suma de la mitad de la suma total de la matriz de entrada.

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)

Genera todas las sumas posibles, luego verifica si la mitad de la última suma (que es la suma de la lista completa) aparece en la lista. (Generar las sumas en el orden un poco incómodo para organizar la suma que necesito ser la última guarda 4 bytes).

Dyalog APL, 12 bytes

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

Pruébelo con TryAPL .

Cómo funciona

+/∊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.

Python 2 , 47 bytes

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

Pruébalo en línea!

Regresé 2,75 años después para superar mi antigua solución en más del 25% con un nuevo método.

Esta versión más larga de 1 byte es un poco más clara.

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

Pruébalo en línea!

La idea es almacenar el conjunto de sumas acumulativas tcomo bits de k, estableciendo el bit 2*tpara indicar que tes una suma acumulativa. Luego, verificamos si dos sumas acumulativas difieren en la mitad de la suma de la lista (final t) cambiando ktanto el bit y haciendo bit &a bit con el original para ver que el resultado no es cero (verdad).

APL, 25 caracteres

Asumiendo que la lista se da en X ← 1 2 3 4.

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

Explicación:

Primera nota que APL evalúa el formulario de derecha a izquierda. Luego:

• X←⎕ toma la entrada del usuario y la almacena en X

• ⍴X da la longitud de X

• ⍳⍴X los números del 1 al ⍴X

• El ⍺y ⍵en {2×+/⍺↑⍵↓X,X}son el argumento izquierdo y derecho de una función diádica que estamos definiendo dentro de las llaves.

  • Ahora para la ⍺↑⍵↓X,Xparte: X,Xsimplemente concatena X consigo mismo; ↑y ↓son tomar y soltar.
  • +/reduce / se pliega +sobre la lista a su derecha

  Entonces 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⍨idxes justo idx ∘.brace idx. ( ⍨es el mapa diagonal; ∘.es el producto externo)

  Entonces esto nos da una matriz ⍴Xby ⍴Xque contiene el doble de las sumas de todas las sublistas conectadas.

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

  Lo último que tenemos que hacer es verificar si la suma de Xestá en algún lugar dentro de esta matriz.

• Lo que hacemos con (+/X)∊matrix.

Brachylog , 6 bytes

sj+~+?

Pruébalo en línea!

Salidas por éxito o fracaso, impresión true.o false.si se ejecuta como un programa.

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, 161 145 129 bytes

• ahorró algunos bytes gracias a @LeakyNun
• ahorrado algunos bytes gracias a @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 tratar en línea

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
}

Haskell, 68 bytes

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

La función fprimero crea una lista de las sumas de todos los segmentos posibles de la lista dada. Luego se compara con la suma total de elementos de la lista. Si llegamos a un punto en la mitad de la suma total, entonces sabemos que tenemos una bisección. También estoy usando el hecho de que si usted takeo dropmás elementos de los que hay en la lista, Haskell no arroja un error.

Mathematica, 48 bytes

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

Función anónima, similar en acción a las numerosas otras respuestas.

Outer[Plus, #, -#], al actuar sobre Accumulate@#(que a su vez actúa sobre la lista de entrada, dando una lista de totales sucesivos) genera esencialmente la misma tabla, como en la parte inferior de la respuesta de Leaky Nun.

!FreeQ[..., Last@#/2]comprueba si no(Last@#)/2 está ausente de la tabla resultante y es el último de los totales sucesivos, es decir, la suma de todos los elementos de la lista de entrada.Last@#

Si esta respuesta es algo interesante, no se debe a un nuevo algoritmo, sino a los trucos específicos de Mathematica; por ejemplo, !FreeQes agradable, en comparación con MemberQ, ya que no requiere un aplanamiento de la tabla que verifica y guarda un byte.

APL (NARS), caracteres 95, bytes 190

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

Considere una matriz de entrada de 4 elementos: 1 2 3 4. ¿Cómo podemos elegir lo útil para esta partición de ejercicio de ese conjunto? Después de que algunos piensan que la partición de estos 4 elementos que podemos usar se describe en el número binario de la izquierda:

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

(1001 o 1011 ecc podrían estar en ese conjunto, pero ya tenemos 0110 y 0100 ecc), así que solo para escribir una función que a partir del número de elemento de la matriz de entrada construya estos números binarios ... sería:

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

que de la entrada 1 2 4 8 [2 ^ 0..lenBytesArgument-1] encuentre 3 6 12, 7 14, 15; así que encuentre el binario de estos números y utilícelos para encontrar las particiones correctas de la matriz de entrada ... Probé la función c solo para esos 4 elementos de entrada, pero parece que está bien para otro número de elementos ...

prueba:

  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