Cubiertas de suma cero

38

Introducción

Considere una lista no vacía L de enteros. Un segmento de suma cero de L es una subsecuencia contigua de L cuya suma es igual a 0. Por ejemplo, [1, -3, 2] es un segmento de suma cero de [-2, 4, 1, -3, 2, 2 , -1, -1] , pero [2, 2] no lo es (porque no suma 0), y tampoco lo es [4, -3, -1] (porque no es contiguo).

Una colección de cortes de suma cero de L es una cubierta de suma cero de L si cada elemento pertenece al menos a uno de los cortes. Por ejemplo:

L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B =        [1, -3, 2]
C =                  [2, -1, -1]

Los tres de suma cero rebana A , B y C forman una cubierta de suma cero de L . Pueden aparecer varias copias del mismo segmento en una portada de suma cero, como esta:

L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B =        [-1, -1, 2]
C =                [2, -1, -1]

Por supuesto, no todas las listas tienen una cobertura de suma cero; algunos ejemplos son [2, -1] (cada segmento tiene una suma distinta de cero) y [2, 2, -1, -1, 0, 1] (el 2 más a la izquierda no es parte de un segmento de suma cero).

La tarea

Su entrada es una lista entera no vacía L , tomada en cualquier formato razonable. Su salida será un valor verdadero si L tiene una cobertura de suma cero, y un valor falso si no.

Puede escribir un programa completo o una función, y gana el conteo de bytes más bajo.

Casos de prueba

[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True
Zgarb
fuente
Por "cada elemento pertenece a uno de los sectores", ¿está tratando el mismo valor en diferentes índices como distinto?
ngenisis
@ngenisis Sí, son distintos y cada uno debe aparecer en un segmento que contenga el índice correspondiente.
Zgarb
2
No debería el tercer ejemplo Falsy [2,2,-1,-1,0,1] -> Falseser Truthy ya que ambas rodajas [2,-1,-1]y [-1,0,1]agregar a cero y todos sus elementos están en la lista original?
dfernan
El 2 más a la izquierda no es parte de ningún segmento de suma cero. No está claro, pero tienen que aparecer en un segmento que "contiene su índice".
Zgarb
Entendido. Eso lo hace más difícil. : o)
dfernan

Respuestas:

11

Jalea , 13 12 bytes

JẆịS¥ÐḟċþJḄẠ

Pruébalo en línea!

Cómo funciona

JẆịS¥ÐḟċþJḄẠ  Main link. Argument: A (array)

J             Yield all indices of A.
 Ẇ            Window; yield all slices of indices.
     Ðḟ       Filter; keep slices for which the link to the left returns 0.
    ¥           Combine the two atoms to the left into a dyadic chain.
  ị               Retrieve the elements of A at the slice's indices.
   S              Take the sum.
         J    Yield the indices of A.
       ċþ     Count table; count how many times each index appears in each table.
          Ḅ   Unbinary; convery the array of counts of each index from base 2 to 
              integer. This yields 0 iff an index does not appear in any slice.
           Ạ  All; return 1 iff all integers are non-zero.
Dennis
fuente
9

Mathematica, 66 65 bytes

¡Ahorré 1 byte y, con suerte, aprendí un nuevo truco para el futuro, gracias a ngenisis!

Dos alternativas igualmente largas, ambas funciones sin nombre que toman una lista de enteros como entrada y regresan Trueo False:

And@@Table[0==Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

0==Norm@Table[Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

En ambos casos, Tr@#[[i;;j]]calcula la suma de la porción de la entrada de una posición ia otra j(1 indexado). Product[...,{i,k},{j,k,l}]multiplica todas estas sumas de corte, como irangos sobre índices que son como máximo ky jrangos sobre índices que son al menos k. (Tenga en cuenta que se l=Tr[1^#]define lcomo la suma de 1todas las potencias en la lista de entrada, que es simplemente la longitud de la lista). En otras palabras, este producto es igual a 0 si y solo si el kelemento th pertenece a un segmento de suma cero .

En la primera versión, cada uno de esos productos se compara 0y And@@regresa Trueprecisamente cuando cada producto es igual 0. En la segunda versión, la función Norm(la longitud del lvector -dimensional) actúa sobre la lista de productos , que es igual 0si y solo si cada entrada es igual 0.

Greg Martin
fuente
1
Tr[1^#]guarda 1byte de Length@#.
ngenisis
¿ 0^Funcionaría en lugar de 0==? No estoy seguro de cómo Mathematica maneja eso. (volvería 1/ en 0lugar de true/ false)
Cyoce
1
Buena idea, pero Mathematica regresa Indeterminatepor 0^0. Además, 1/ 0no son realmente veraces / falsos en Mathematica: está demasiado tipeado para hacer felices a los golfistas :)
Greg Martin
7

Mathematica, 65 64 bytes

Gracias a ngenisis por guardar 1 byte.

Union@@Cases[Subsequences[x=Range@Tr[1^#]],a_/;Tr@#[[a]]==0]==x&

Prefiero encontrar una solución de coincidencia de patrones pura, pero está demostrando ser complicado (y cosas como {___,a__,___}siempre son muy largas).

Martin Ender
fuente
4

Haskell, 94 bytes

import Data.Lists
g x=(1<$x)==(1<$nub(id=<<[i|(i,0)<-fmap sum.unzip<$>powerslice(zip[1..]x)]))

Ejemplo de uso: g [-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True.

Cómo funciona (usemos [-1,1,5,-5]para entrada):

        zip[1..]x  -- zip each element with its index
                   -- -> [(1,-1),(2,1),(3,5),(4,-5)]
      powerslice   -- make a list of all continuous subsequences
                   -- -> [[],[(1,-1)],[(1,-1),(2,1)],[(1,-1),(2,1),(3,5)],[(1,-1),(2,1),(3,5),(4,-5)],[(2,1)],[(2,1),(3,5)],[(2,1),(3,5),(4,-5)],[(3,5)],[(3,5),(4,-5)],[(4,-5)]]
    <$>            -- for each subsequence
   unzip           --   turn the list of pairs into a pair of lists
                   --   -> [([],[]),([1],[-1]),([1,2],[-1,1]),([1,2,3],[-1,1,5]),([1,2,3,4],[-1,1,5,-5]),([2],[1]),([2,3],[1,5]),([2,3,4],[1,5,-5]),([3],[5]),([3,4],[5,-5]),([4],[-5])]
  fmap sum         --   and sum the second element
                   --   -> [([],0),([1],-1),([1,2],0),([1,2,3],5),([1,2,3,4],0),([2],1),([2,3],6),([2,3,4],1),([3],5),([3,4],0),([4],-5)]
 [i|(i,0)<-    ]   -- take all list of indices where the corresponding sum == 0
                   -- -> [[],[1,2],[1,2,3,4],[3,4]]
 id=<<             -- flatten the list
                   -- -> [1,2,1,2,3,4,3,4]
nub                -- remove duplicates
                   -- -> [1,2,3,4]

(1<$x)==(1<$    )  -- check if the above list has the same length as the input list. 
nimi
fuente
powerslicees un gran nombre de función.
Zgarb
3

Ruby, 81 bytes

Pruébalo en línea

Solución simplista de fuerza bruta; para cada elemento de la matriz, intente encontrar un segmento de suma cero que lo contenga.

->a{(0..l=a.size).all?{|i|(0..i).any?{|j|(i..l).any?{|k|a[j..k].inject(:+)==0}}}}
Tinta de valor
fuente
3

J, 36 35 bytes

#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\

Para cada subsumo agrego los índices del elemento y mantengo los índices si subsum es 0y luego verifico si cada índice está presente.

Truco: se pueden generar índices basados ​​en 1 de una lista, es #\decir, la longitud de cada prefijo.

Uso:

   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1 _1 2
1
   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1
0

Pruébelo en línea aquí.

randomra
fuente
Creo que puede guardar 2 bytes usando el truco base 1 para la suma y usando un aplanamiento compuesto#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
millas
2

JavaScript (ES6), 109 bytes

f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)

Fragmento de prueba

ETHproducciones
fuente
1

Python, 123 120 bytes

-3 bytes gracias a @Zgarb

Rellena una lista con el mismo tamaño que la entrada con sectores de suma cero y sobrescribe según los índices, devolviendo su igualdad al original al final.

def f(l):
 s=len(l);n=[0]*s
 for i in range(s):
  for j in range(i,s+1):
   if sum(l[i:j])==0:n[i:j]=l[i:j]
 return n==l
dfernan
fuente
1
Creo que puedes usar 0como marcador de posición en lugar de None. No habrá falsos positivos, porque cada 0entrada siempre es parte o un segmento de suma cero.
Zgarb
Tienes razón. Pensé en eso pero terminé concluyendo que podría generar falsos positivos.
dfernan
0

Scala, 49 bytes

% =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)

Pruébalo en ideone

Uso:

val f:(Seq[Int]=>Boolean)= % =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)
f(Seq(4, -2, -2)) //returns true

Sin golf:

array=>(1 to array.size)
  .flatMap(n => array.sliding(n))
  .exists(slice => slice.sum == 0)

Explicación:

% =>            //define a anonymouns function with a parameter called %
  (1 to %.size) //create a range from 1 to the size of %
  flatMap(      //flatMap each number n of the range
    %sliding    //to an iterator with all slices of % with length n
  )exists(      //check whether there's an iterator with a sum of 0
    _.sum==0
  )
corvus_192
fuente
No estoy exactamente seguro de cómo funciona esto, pero creo que debería fallar en algunos de los casos de prueba verdaderos.
Zgarb
@Zgarb Agregué un enlace a ideone, para que pueda verificar que sea correcto. Básicamente es una fuerza bruta, probando cada rebanada posible.
corvus_192
¿Se puede usar %como nombre de parámetro? ¡Guay!
Cyoce
@Cyoce Puede usar prácticamente cualquier carácter Unicode excepto .,;:()[]{}\"'. Bastante útil para jugar al golf, ya que se separan de las letras por el análisis, por lo que puede ahorrar algo de espacio en blanco.
corvus_192
Revisé los casos de prueba, y parece dar truepara el segundo caso falso.
Zgarb
0

Python, 86 bytes

def f(l):
 r=range(len(l))
 if[i for i in r for j in r if sum(l[j:j+i+1])==0]:return 1

Verdad = 1 Falsy = Ninguno

sonrad10
fuente
Esto regresa incorrectamente 1para el tercer caso de prueba.
Zgarb
1
En realidad, regresa 1para todos los casos de prueba, excepto los dos primeros falsos.
dfernan
0

Clojure, 109 bytes

#(=(count %)(count(set(flatten(for[r[(range(count %))]l r p(partition l 1 r):when(=(apply +(map % p))0)]p))))

Genera todas las particiones que suman cero, verifica que tenga índices distintos de "longitud de vector de entrada".

NikoNyrh
fuente
0

PHP, 104 bytes

Fuerza bruta y aún más de 99 bytes. :-(

for($p=$r=$c=$argc;$s=--$p;)for($i=$c;$s&&$k=--$i;)for($s=0;$k<$c&&($r-=!$s+=$argv[$k++])&&$s;);echo!$r;

toma información de los argumentos de la línea de comandos, 1para la verdad, vacía para la falsedad. Corre con -r.

Descompostura

for($p=$r=$argc;$s=$p--;)   # loop $p from $argc-1 to 0 with dummy value >0 for $s
    for($i=$p;$s&&$k=$i--;)     # loop $i (slice start) from $p to 1, break if sum is 0
        for($s=0;                   # init sum to 0
            $k<$argc                # loop $k (slice end) from $i to $argc-1
            &&($r-=!$s+=$argv[$k++])    # update sum, decrement $r if sum is 0
            &&$s;);                     # break loop if sum is 0
echo!$r;                    # $r = number of elements that are not part of a zero-sum slice

$argv[0]contiene el nombre del archivo; si corre con-r , será -y evaluará 0para operaciones numéricas.

Titus
fuente
0

JavaScript (ES6), 102 bytes

a=>(g=f=>a.map((_,i)=>f(i)))(i=>g(j=>j<i||(t+=a[j])||g(k=>b[k]&=k<i|k>j),t=0),b=g(_=>1))&&!/1/.test(b)

Calcula las sumas parciales para todos los elementos i..jinclusive, y restablece los elementos relevantes de bfrom 1a 0cuando encuentra una suma cero, finalmente verificando que no quedan 1s.

Neil
fuente