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
[2,2,-1,-1,0,1] -> False
ser 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?Respuestas:
Jalea ,
1312 bytesPruébalo en línea!
Cómo funciona
fuente
Mathematica,
6665 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
True
oFalse
:En ambos casos,
Tr@#[[i;;j]]
calcula la suma de la porción de la entrada de una posicióni
a otraj
(1 indexado).Product[...,{i,k},{j,k,l}]
multiplica todas estas sumas de corte, comoi
rangos sobre índices que son como máximok
yj
rangos sobre índices que son al menosk
. (Tenga en cuenta que sel=Tr[1^#]
definel
como la suma de1
todas 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 elk
elemento th pertenece a un segmento de suma cero .En la primera versión, cada uno de esos productos se compara
0
yAnd@@
regresaTrue
precisamente cuando cada producto es igual0
. En la segunda versión, la funciónNorm
(la longitud dell
vector -dimensional) actúa sobre la lista de productos , que es igual0
si y solo si cada entrada es igual0
.fuente
Tr[1^#]
guarda1
byte deLength@#
.0^
Funcionaría en lugar de0==
? No estoy seguro de cómo Mathematica maneja eso. (volvería1
/ en0
lugar detrue
/false
)Indeterminate
por0^0
. Además,1
/0
no son realmente veraces / falsos en Mathematica: está demasiado tipeado para hacer felices a los golfistas :)Mathematica,
6564 bytesGracias a ngenisis por guardar 1 byte.
Prefiero encontrar una solución de coincidencia de patrones pura, pero está demostrando ser complicado (y cosas como
{___,a__,___}
siempre son muy largas).fuente
Haskell, 94 bytes
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):fuente
powerslice
es un gran nombre de función.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.
fuente
J,
3635 bytesPara cada subsumo agrego los índices del elemento y mantengo los índices si subsum es
0
y 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:
Pruébelo en línea aquí.
fuente
#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
JavaScript (ES6), 109 bytes
Fragmento de prueba
Mostrar fragmento de código
fuente
Python,
123120 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.
fuente
0
como marcador de posición en lugar deNone
. No habrá falsos positivos, porque cada0
entrada siempre es parte o un segmento de suma cero.Scala, 49 bytes
Pruébalo en ideone
Uso:
Sin golf:
Explicación:
fuente
%
como nombre de parámetro? ¡Guay!.,;:()[]{}\"'
. 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.true
para el segundo caso falso.Python, 86 bytes
Verdad = 1 Falsy = Ninguno
fuente
1
para el tercer caso de prueba.1
para todos los casos de prueba, excepto los dos primeros falsos.Clojure, 109 bytes
Genera todas las particiones que suman cero, verifica que tenga índices distintos de "longitud de vector de entrada".
fuente
PHP, 104 bytes
Fuerza bruta y aún más de 99 bytes. :-(
toma información de los argumentos de la línea de comandos,
1
para la verdad, vacía para la falsedad. Corre con-r
.Descompostura
$argv[0]
contiene el nombre del archivo; si corre con-r
, será-
y evaluará0
para operaciones numéricas.fuente
JavaScript (ES6), 102 bytes
Calcula las sumas parciales para todos los elementos
i..j
inclusive, y restablece los elementos relevantes deb
from1
a0
cuando encuentra una suma cero, finalmente verificando que no quedan1
s.fuente