introduction

Considérons une liste non vide L d'entiers. Une tranche de somme nulle de L est une sous-séquence contiguë de L dont la somme est égale à 0. Par exemple, [1, -3, 2] est une tranche de somme nulle de [-2, 4, 1, -3, 2, 2 , -1, -1] , mais [2, 2] n’est pas (car sa somme ne correspond pas à 0), ni non plus [4, -3, -1] (car il n’est pas contigu).

Une collection de tranches à somme nulle de L est une couverture à somme nulle de L si chaque élément appartient à au moins une des tranches. Par exemple:

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

Les trois tranches somme nulle A , B et C forment un couvercle somme nulle de L . Plusieurs copies de la même tranche peuvent apparaître dans une couverture à somme nulle, comme ceci:

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

Bien sûr, toutes les listes n’ont pas une couverture à somme nulle; quelques exemples sont [2, -1] (chaque tranche a une valeur non nulle somme) et [2, 2, -1, -1, 0, 1] (la plus à gauche 2 ne fait pas partie d'une tranche de somme nulle).

La tâche

Votre entrée est une liste entière non vide L , prise dans n’importe quel format raisonnable. Votre sortie doit être une valeur de vérité si L a une couverture à somme nulle et une valeur de fausseté sinon.

Vous pouvez écrire un programme complet ou une fonction, et le nombre d'octets le plus faible gagne.

Cas de test

[-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

Gelée , 13 à 12 octets

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

Essayez-le en ligne!

Comment ça marche

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.

Mathematica, 66 65 octets

Sauvé 1 octet, et j'espère appris une nouvelle astuce pour l'avenir, grâce à ngenisis!

Deux alternatives également longues, qui sont toutes deux des fonctions non nommées prenant une liste d’entiers en entrée et retournant Trueou 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^#]}]&

Dans les deux cas, Tr@#[[i;;j]]calcule la somme de la tranche de l'entrée de position ien position j(indexé 1). Product[...,{i,k},{j,k,l}]multiples ensemble toutes ces sommes de tranche, comme des iplages sur des indices qui sont au plus ket des jplages sur des indices au moins k. (Notez que l=Tr[1^#]définit lcomme étant la somme de 1toutes les puissances de la liste d'entrée, qui est simplement la longueur de la liste.) En d'autres termes, ce produit est égal à 0 si et seulement si l' kélément th appartient à une tranche à somme nulle .

Dans la première version, chacun de ces produits est comparé 0et est And@@renvoyé Trueprécisément lorsque tous les produits sont égaux 0. Dans la deuxième version, la fonction Norm(la longueur du lvecteur -dimensional) agit sur la liste des produits , ce qui équivaut à 0si et seulement si toutes les entrées sont égales 0.

Mathematica, 65 64 octets

Merci à ngenisis d’avoir économisé 1 octet.

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

Je préférerais trouver une solution de correspondance de modèle pure, mais elle s'avère délicate (et les choses comme {___,a__,___}sont toujours super longues).

Haskell, 94 octets

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

Exemple d'utilisation: 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 .

Comment ça marche (utilisons [-1,1,5,-5]pour la saisie):

        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. 

Ruby, 81 octets

Essayez-le en ligne

Solution simpliste de force brute; Pour chaque élément du tableau, essayez de trouver une tranche à somme nulle qui la contient.

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

J, 36 35 octets

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

Pour chaque subsum, j'ajoute les index de l'élément et je garde les index ssi subsum est 0 , puis vérifie si tous les index sont présents.

Astuce: les index basés sur 1 d'une liste peuvent être générés avec #\ longueur de chaque préfixe.

Usage:

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

Essayez-le en ligne ici.

JavaScript (ES6), 109 octets

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)

Extrait de test

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)

I.textContent = I.textContent.replace(/.+/g,x=>x+` (${f(eval(x.split(" ")[0]))})`)

<pre id=I>[-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</pre>

Python, 123 120 octets

_{-3 octets grâce à @Zgarb}

Remplit une liste avec la même taille que l'entrée avec des tranches à somme nulle et les écrase selon les index, en renvoyant son égalité à l'original à la fin.

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

Scala, 49 octets

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

Essayez chez ideone

Usage:

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

Ungolfed:

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

Explication:

% =>            //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
  )

Python, 86 octets

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

Vérité = 1 Falsy = Aucune

Clojure, 109 octets

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

Génère toutes les partitions dont la somme est égale à zéro et vérifie qu’il possède des index distincts "longueur du vecteur d’entrée".

PHP, 104 octets

Force brute et toujours plus de 99 octets. :-(

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;

prend les arguments de la ligne de commande, 1 pour vérité, vide pour fausseté. Courez avec -r.

panne

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]contient le nom du fichier; s'il est exécuté avec -r, il le sera -et sera évalué à 0des opérations numériques.

JavaScript (ES6), 102 octets

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)

Calcule les sommes partielles pour tous les éléments i..j inclus et réinitialise les éléments pertinents de bde 1à 0quand il trouve une somme nulle, vérifiant enfin qu'il ne reste plus de 1s.