Zéro somme couvre

38

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
Zgarb
la source
Par "chaque élément appartient à l'une des tranches", traitez-vous la même valeur à différents indices comme distincte?
ngenisis
@ ngenisis Oui, ils sont distincts et chacun doit apparaître dans une tranche contenant l'index correspondant.
Zgarb
2
Le troisième exemple de fausseté ne devrait-il pas [2,2,-1,-1,0,1] -> Falseêtre la vérité puisque les deux tranches [2,-1,-1]et [-1,0,1]add to zero et que tous leurs éléments sont dans la liste d'origine?
dfernan
Le plus à gauche 2 ne fait partie d'aucune tranche à somme nulle. Ce n'est pas clair, mais ils doivent apparaître dans une tranche qui "contient leur index".
Zgarb
Compris. Cela rend plus difficile. : o)
dfernan

Réponses:

11

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.
Dennis
la source
9

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.

Greg Martin
la source
1
Tr[1^#]enregistre 1octet de Length@#.
ngenisis
Serait 0^travailler au lieu de 0==? Vous ne savez pas comment Mathematica gère cela. (vous reviendriez 1/ 0au lieu de true/ false)
Cyoce
1
Bonne idée, mais Mathematica revient Indeterminatepour 0^0. En outre, 1/ 0ne sont pas réellement truthy / falsy dans Mathematica-il est trop fortement typé pour faire des golfeurs heureux :)
Greg Martin
7

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

Martin Ender
la source
4

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. 
nimi
la source
powersliceest un excellent nom de fonction.
Zgarb
3

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}}}}
Valeur d'encre
la source
3

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.

randomra
la source
Je pense que vous pouvez enregistrer 2 octets en utilisant la base 1 tour pour sommation et en utilisant un composé Aplatir#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
miles
2

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

ETHproductions
la source
1

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
Dfernan
la source
1
Je pense que vous pouvez utiliser 0comme espace réservé au lieu de None. Il n'y aura pas de faux positifs, car chaque 0entrée est toujours une tranche ou une tranche à somme nulle.
Zgarb
Vous avez raison. J'y ai pensé, mais j'ai fini par conclure que cela pouvait entraîner des faux positifs.
dfernan
0

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
  )
corvus_192
la source
Je ne suis pas tout à fait sûr de savoir comment cela fonctionne, mais je pense que cela devrait échouer dans certains cas de test de la vérité.
Zgarb
@Zgarb J'ai ajouté un lien vers ideone afin que vous puissiez vérifier qu'il est correct. C'est fondamentalement une force brute, essayant chaque tranche possible.
corvus_192
Vous pouvez utiliser %comme nom de paramètre? Cool!
Cyoce
@ Cyoce Vous pouvez utiliser à peu près n'importe quel caractère Unicode sauf .,;:()[]{}\"'. Très utile pour jouer au golf, car ils sont séparés des lettres par l'analyse, ce qui vous permet d'économiser de l'espace.
corvus_192
J'ai vérifié les cas de test, et il semble donner truepour le deuxième cas de fausseté.
Zgarb
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

sonrad10
la source
Cela renvoie incorrectement 1pour le troisième cas de test.
Zgarb
1
En fait, il est renvoyé 1pour tous les tests sauf les deux premiers faux.
dfernan
0

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

NikoNyrh
la source
0

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.

Titus
la source
0

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.

Neil
la source