Nullsummenschutz

38

Einführung

Betrachten Sie eine nicht leere Liste L von ganzen Zahlen. Eine Nullsummenscheibe von L ist eine zusammenhängende Untersequenz von L, deren Summe gleich 0 ist. Beispielsweise ist [1, -3, 2] eine Nullsummenscheibe von [-2, 4, 1, -3, 2, 2 , -1, -1] , aber [2, 2] ist nicht (weil es nicht 0 ergibt) und auch nicht [4, -3, -1] (weil es nicht zusammenhängend ist).

Eine Sammlung von Nullsummenschnitten von L ist eine Nullsummenabdeckung von L, wenn jedes Element zu mindestens einem der Abschnitte gehört. Beispielsweise:

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

Die drei Nullsummen Scheiben A , B und C ein Nullsumme mit Vordruck L . In einem Nullsummen-Cover können mehrere Kopien desselben Slices wie folgt angezeigt werden:

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

Natürlich haben nicht alle Listen eine Nullsummendeckung; Einige Beispiele sind [2, -1] (jede Schicht hat eine Summe ungleich Null) und [2, 2, -1, -1, 0, 1] (die äußerste linke 2 ist kein Teil einer Nullsummenschicht).

Die Aufgabe

Ihre Eingabe ist eine nicht leere Ganzzahl-Liste L , die in einem beliebigen vernünftigen Format erstellt wurde. Ihre Ausgabe ist ein wahrer Wert, wenn L eine Nullsummendeckung hat, und ein falscher Wert, wenn nicht.

Sie können ein vollständiges Programm oder eine Funktion schreiben, und die niedrigste Byteanzahl gewinnt.

Testfälle

[-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
quelle
Behandeln Sie bei "Jedes Element gehört zu einem der Slices" denselben Wert bei verschiedenen Indizes als unterschiedlich?
Genisis
@ngenisis Ja, sie sind unterschiedlich und sollten jeweils in einem Slice auftreten, das den entsprechenden Index enthält.
Zgarb
2
Sollte das dritte falsche Beispiel [2,2,-1,-1,0,1] -> Falsenicht wahr sein, da beide Slices [2,-1,-1]und die [-1,0,1]Addition zu Null und alle ihre Elemente in der ursprünglichen Liste enthalten sind?
dfernan
Die 2 ganz links ist kein Teil einer Nullsummenscheibe. Es ist ein bisschen unklar, aber sie müssen in einem Slice auftreten, das "ihren Index enthält".
Zgarb
Verstanden. Das macht es schwerer. : o)
dfernan

Antworten:

11

Jelly , 13-12 Bytes

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

Probieren Sie es online!

Wie es funktioniert

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
quelle
9

Mathematica, 66 65 Bytes

1 Byte gespart und dank Genisis hoffentlich einen neuen Trick für die Zukunft gelernt!

Zwei gleich lange Alternativen, bei denen es sich um unbenannte Funktionen handelt, die eine Liste von Ganzzahlen als Eingabe und Rückgabe verwenden, Trueoder 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^#]}]&

Tr@#[[i;;j]]Berechnet in beiden Fällen die Summe des Slice der Eingabe von Position izu Position j(1-indiziert). Product[...,{i,k},{j,k,l}]Multipliziert alle diese Slice-Summen als iBereiche über Indizes, die höchstens sind, kund jBereiche über Indizes, die mindestens sind k. (Beachten Sie, dass l=Tr[1^#]definiert ldie Summe sein , 1um alle Kräfte in der Eingabeliste, die einfach die Länge der Liste ist.) Mit anderen Worten, dieses Produkt ist gleich 0 , wenn und nur wenn das kte Element gehört zu einer Nullsumme Scheibe .

In der ersten Version, jedes dieser Produkte ist im Vergleich zu 0und And@@kehrt Truegenau dann , wenn jedes einzelne Produkt entspricht 0. In der zweiten Version wird die Liste der Produkte von der Funktion Norm(der Länge des leindimensionalen Vektors) bearbeitet, die 0genau dann gleich ist, wenn jeder Eintrag gleich ist 0.

Greg Martin
quelle
1
Tr[1^#]Speichert 1Byte von Length@#.
Genisis
Würde 0^arbeiten statt 0==? Ich bin mir nicht sicher, wie Mathematica damit umgeht. (Sie würden 1/ 0anstelle von true/ zurückkehren false)
Cyoce
1
Coole Idee, aber Mathematica kehrt zurück Indeterminatefür 0^0. Auch 1/ 0sind nicht wirklich truthy / falsy in Mathematica-it auch dringend zu machen Golfer getippt glücklich :)
Greg Martin
7

Mathematica, 65 64 Bytes

Dank an ngenisis für das Speichern von 1 Byte.

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

Ich würde lieber eine reine Mustervergleichslösung finden, aber es erweist sich als schwierig (und Dinge wie {___,a__,___}sind immer sehr langwierig).

Martin Ender
quelle
4

Haskell, 94 Bytes

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

Anwendungsbeispiel: 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.

Wie es funktioniert (verwenden wir [-1,1,5,-5]für die Eingabe):

        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
quelle
powersliceist so ein toller Funktionsname.
Zgarb
3

Ruby, 81 Bytes

Probieren Sie es online aus

Einfache Brute-Force-Lösung; Versuchen Sie, für jedes Element des Arrays einen Nullsummen-Slice zu finden, der es enthält.

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

J, 36-35 Bytes

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

Für jede Subsumme füge ich die Indizes des Elements hinzu und behalte die Indizes, wenn f subsum ist, 0und überprüfe dann, ob jeder Index vorhanden ist.

Trick: 1-basierte Indizes einer Liste können mit der #\Länge jedes Präfixes erzeugt werden.

Verwendung:

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

Probieren Sie es hier online aus.

randomra
quelle
Ich denke, Sie können 2 Bytes sparen, indem Sie den Trick zur Basis 1 für die Summierung und eine komponierte Abflachung verwenden#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
Meilen
2

JavaScript (ES6), 109 Byte

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)

Testschnipsel

ETHproductions
quelle
1

Python, 123 120 Bytes

-3 Bytes dank @Zgarb

Füllt eine Liste mit der gleichen Größe wie die Eingabe mit Nullsummenschnitten und überschreibt sie gemäß den Indizes, wobei am Ende die Gleichheit mit dem Original wiederhergestellt wird.

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
quelle
1
Ich denke, Sie können 0anstelle von als Platzhalter verwenden None. Es wird keine Fehlalarme geben, da jeder 0in der Eingabe immer ein Teil oder eine Nullsumme ist.
Zgarb
Du hast recht. Ich dachte darüber nach, kam aber zu dem Schluss, dass es zu Fehlalarmen kommen könnte.
dfernan
0

Scala, 49 Bytes

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

Probiere es bei ideone aus

Verwendung:

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)

Erläuterung:

% =>            //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
quelle
Ich bin mir nicht ganz sicher, wie das funktioniert, aber ich denke, es sollte bei einigen der wahrheitsgemäßen Testfälle scheitern.
Zgarb
@Zgarb Ich habe einen Link zu ideone hinzugefügt, damit Sie überprüfen können, ob er korrekt ist. Es ist im Grunde eine rohe Kraft, die jede mögliche Scheibe ausprobiert.
corvus_192
Sie können %als Parameternamen verwenden? Cool!
Cyoce
@Cyoce Sie können so ziemlich jedes Unicode-Zeichen verwenden, außer .,;:()[]{}\"'. Ziemlich nützlich zum Golfen, da sie durch das Parsen von Buchstaben getrennt werden, sodass Sie Leerzeichen sparen können.
corvus_192
Ich habe die Testfälle überprüft, und es scheint, als truegäbe es einen zweiten falschen Fall.
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

Wahrheit = 1 Falsch = Keine

sonrad10
quelle
Dies wird fälschlicherweise 1für den dritten Testfall zurückgegeben.
Zgarb
1
Es wird tatsächlich 1für alle Testfälle mit Ausnahme der ersten beiden falschen zurückgegeben.
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))))

Erzeugt alle Partitionen, deren Summe Null ist, und prüft, ob sie unterschiedliche Indizes für die Länge des Eingabevektors haben.

NikoNyrh
quelle
0

PHP, 104 Bytes

Brute Force und immer noch über 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;

1Nimmt Eingaben von Kommandozeilenargumenten entgegen, für wahr, für falsch leer. Laufen Sie mit -r.

Nervenzusammenbruch

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]enthält den Dateinamen; Wenn Sie mit ausführen -r, wird dies für numerische Operationen ausgeführt -und ausgewertet 0.

Titus
quelle
0

JavaScript (ES6), 102 Byte

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)

Berechnet die Teilsummen für alle Elemente i..jeinschließlich und setzt die relevanten Elemente bvon 1bis zurück, 0wenn eine Nullsumme gefunden wird, und überprüft schließlich, ob keine 1s mehr vorhanden sind.

Neil
quelle