Introdução
Considere uma lista não vazia L de números inteiros. Uma fatia de soma zero de L é uma subsequência contígua de L cuja soma é igual a 0. Por exemplo, [1, -3, 2] é uma fatia de soma zero de [-2, 4, 1, -3, 2, 2 , -1, -1] , mas [2, 2] não é (porque não soma 0), e nem [4, -3, -1] (porque não é contíguo).
Uma coleção de fatias de soma zero de L é uma cobertura de soma zero de L se cada elemento pertencer a pelo menos uma das fatias. Por exemplo:
L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B = [1, -3, 2]
C = [2, -1, -1]
Os três fatias de soma zero Um , B e C formam uma tampa de soma-zero de L . Várias cópias da mesma fatia podem aparecer em uma capa de soma zero, assim:
L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B = [-1, -1, 2]
C = [2, -1, -1]
Obviamente, nem todas as listas têm uma cobertura de soma zero; alguns exemplos são [2, -1] (cada fatia tem soma diferente de zero) e [2, 2, -1, -1, 0, 1] (o 2 mais à esquerda não faz parte de uma fatia de soma zero).
A tarefa
Sua entrada é uma lista inteira não vazia L , tirada em qualquer formato razoável. Sua saída será um valor verdadeiro se L tiver uma cobertura de soma zero e um valor falso se não.
Você pode escrever um programa completo ou uma função, e a menor contagem de bytes vence.
Casos de teste
[-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 vez que ambas as fatias[2,-1,-1]
e[-1,0,1]
adicione a zero e todos os seus elementos estão na lista original?Respostas:
Geléia ,
1312 bytesExperimente online!
Como funciona
fonte
Mathematica,
6665 bytesEconomizei 1 byte e espero que tenha aprendido um novo truque para o futuro, graças ao ngenisis!
Duas alternativas igualmente longas, ambas funções sem nome, pegando uma lista de números inteiros como entrada e retornando
True
ouFalse
:Nos dois casos,
Tr@#[[i;;j]]
calcula a soma da fatia da entrada de posiçãoi
em posiçãoj
(indexada 1).Product[...,{i,k},{j,k,l}]
multiplica todas essas somas de fatia, comoi
intervalos acima de índices que são no máximok
ej
intervalos acima de índices que são pelo menosk
. (Observe quel=Tr[1^#]
definel
como a soma de1
todas as potências da lista de entrada, que é simplesmente o comprimento da lista.) Em outras palavras, este produto é igual a 0 se e somente se ok
elemento th pertencer a uma fatia de soma zero .Na primeira versão, cada um desses produtos é comparado
0
eAnd@@
retornaTrue
exatamente quando cada produto é igual0
. Na segunda versão, a lista de produtos é acionada pela funçãoNorm
(o comprimento dol
vetor -dimensional), que é igual a0
se e somente se todas as entradas forem iguais0
.fonte
Tr[1^#]
salva1
byte deLength@#
.0^
trabalhar em vez de0==
? Não tenho certeza de como o Mathematica lida com isso. (você retornaria1
/ em0
vez detrue
/false
)Indeterminate
para0^0
. Além disso,1
/0
não são realmente truthy / Falsas no Mathematica-lo está também fortemente tipado para fazer golfistas feliz :)Mathematica,
6564 bytesObrigado a ngenisis por economizar 1 byte.
Prefiro encontrar uma solução pura de correspondência de padrões, mas está se mostrando complicada (e coisas como
{___,a__,___}
sempre são muito longas).fonte
Haskell, 94 bytes
Exemplo 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
.Como funciona (vamos usar
[-1,1,5,-5]
para entrada):fonte
powerslice
é um ótimo nome de função.Ruby, 81 bytes
Experimente online
Solução simplista de força bruta; para cada elemento da matriz, tente encontrar uma fatia de soma zero que a contenha.
fonte
J,
3635 bytesPara cada subsum, adiciono os índices do elemento e mantenho os índices se subsum for
0
e, em seguida, verifico se todos os índices estão presentes.Truque: índices baseados em 1 de uma lista podem ser gerados com o
#\
comprimento de cada prefixo.Uso:
Experimente online aqui.
fonte
#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
JavaScript (ES6), 109 bytes
Snippet de teste
Mostrar snippet de código
fonte
Python,
123120 bytes-3 bytes graças a @Zgarb
Preenche uma lista com o mesmo tamanho da entrada com fatias de soma zero e sobrescreve de acordo com os índices, retornando sua igualdade ao original no final.
fonte
0
como espaço reservado em vez deNone
. Não haverá falsos positivos, porque cada0
entrada é sempre parte ou uma fatia de soma zero.Scala, 49 bytes
Experimente em ideone
Uso:
Ungolfed:
Explicação:
fonte
%
como um nome de parâmetro? Legal!.,;:()[]{}\"'
. Bastante útil para jogar golfe, porque elas são separadas das letras pela análise, para que você possa economizar algum espaço em branco.true
o segundo caso falso.Python, 86 bytes
Verdade = 1 Falsia = Nenhuma
fonte
1
para o terceiro caso de teste.1
para todos os casos de teste, exceto os dois primeiros casos falsos.Clojure, 109 bytes
Gera todas as partições que somam zero, verifica se possui índices distintos de "comprimento do vetor de entrada".
fonte
PHP, 104 bytes
Força bruta e ainda com mais de 99 bytes. :-(
recebe entrada dos argumentos da linha de comando,
1
por verdade, vazia por falsidade. Corra com-r
.demolir
$argv[0]
contém o nome do arquivo; se executado-r
, será-
e avaliará se0
para operações numéricas.fonte
JavaScript (ES6), 102 bytes
Calcula as somas parciais para todos os elementos
i..j
, inclusive, e redefine os elementos relevantes deb
de1
para0
quando encontrar uma soma zero, finalmente verificando se não há mais1
restos.fonte