Gleichgewichtsindex einer Sequenz

10

Der Gleichgewichtsindex einer Sequenz ist ein Index, bei dem die Summe der Elemente bei niedrigeren Indizes gleich der Summe der Elemente bei höheren Indizes ist. Zum Beispiel in einer Sequenz A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 ist ein Gleichgewichtsindex, weil:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 ist auch ein Gleichgewichtsindex, weil:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(Summe der Nullelemente ist Null) 7 ist kein Gleichgewichtsindex, da es sich nicht um einen gültigen Index der Sequenz A handelt.

Die Idee ist, ein Programm zu erstellen, das bei gegebener Sequenz (Array) seinen Gleichgewichtsindex (beliebig) oder -1 zurückgibt, wenn keine Gleichgewichtsindizes vorhanden sind.

Cristian
quelle

Antworten:

6

Golfscript 17 16

Da die Form der Eingabe nicht angegeben ist, wird eine Zeichenfolge im Golfscript-Array-Format von stdin übernommen.

~0\{1$+.@+\}/])?

Also lauf wie zB

golfscript.ry eqindex.gs <<<"[-7 1 5 2 -4 3 0]"

Die Idee ist sehr einfach: Es nimmt ein Array von A_iund ordnet es einem Array von zu A_i + 2 SUM_{j<i} A_jund sucht dann nach dem ersten Index, der der Summe des gesamten Arrays entspricht.


Für die Herausforderung von @ mellamokb biete ich an:

~0\{1$+.@+\}/:S;]:A,,{A=S=},`

für 29 Zeichen.

Peter Taylor
quelle
Da Sie leicht die kürzeste Lösung haben,
erkläre
@ Mellamokb, mit meinen Komplimenten.
Peter Taylor
Cool! Jetzt habe ich noch etwas GolfScript zu lernen ...
Mellamokb
5

Python - 72 Zeichen

A=input()
print[i for i in range(len(A))if sum(A[:i])==sum(A[i+1:])]or-1

Übernimmt eine durch Kommas getrennte Eingabe

Gnibbler
quelle
Genial ... dieser gibt alle Gleichgewichtsindizes zurück ... wirklich cool.
Cristian
@Christian: Meins auch.
FUZxxl
Ich verstehe :) Ich weiß eigentlich nicht, wie man Hashkell-Code ausführt ... muss lernen.
Cristian
Christian: Es gibt ghc, einen Compiler und Umarmungen, einen Dolmetscher. Ich würde vorschlagen, Umarmungen herunterzuladen . Es ist besser als das Herunterladen von ghc, da Umarmungen ungefähr 7 MiB betragen, während die gesamte ghc-Verteilung ungefähr 300 MiB beträgt. Mit Umarmungen können Sie einfach eingeben, runhugs FILE.hsum das Programm auszuführen FILE.hs.
FUZxxl
5

Haskell ( 95 83)

e l=[n|n<-[0..length l-1],sum(take n l)==sum(drop(n+1)l)]
main=interact$show.e.read

Liest eine Liste im Haskell-Stil von stdin, z.

[-7,1,5,2,-4,3,0]

und gibt eine Haskell-Style-Liste der Indizes zurück, z.

[3,6]

Das Ergebnis ist [], wenn es keinen Index gibt.

Bitte sagen Sie mir, ob Ihre Spezifikation ein anderes Verhalten wünscht.

Bearbeitungen:

  • (95 → 83): Das Listenverständnis ist kürzer
FUZxxl
quelle
4

C - 96

a[99],*p=a,s;main(){for(;scanf("%d",p)>0;s+=*p++
);for(;p>a;s-=*p)(s-=*--p)||printf("%d\n",p-a);}

Beachten Sie, dass dadurch die Gleichgewichtsindizes in umgekehrter Reihenfolge gedruckt werden.

Beispielnutzung:

$ ./equilibrium <<< "-7 1 5 2 -4 3 0"
6
3
Joey Adams
quelle
3

Ruby (83 77)

a=*$<.map(&:to_i)
p (0...a.size).select{|x|a[0..x].reduce(:+)==a[x..-1].reduce(:+)}

Bearbeiten: Kürzere Version wie von Ventero vorgeschlagen:

a=$<.map &:to_i
p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"}

Die Eingabe ist eine Zahl pro Zeile, die Ausgabe ist eine durch Kommas getrennte Liste von Indizes in eckigen Klammern.

Lars Haugseth
quelle
1
Sie brauchen die Klammern in der ersten Zeile nicht und können einige Zeichen speichern, indem Sie join + eval verwenden, um die Summen zu erhalten: p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"}(Beachten Sie, dass dies für Ruby 1.9 gilt, da
Zeichenliterale
Tolle Vorschläge, danke! Ein bisschen ärgerlich, dass Array # sum nicht im Ruby-Kern ist.
Lars Haugseth
Wenn ich die Klammern in der ersten Zeile entferne, erhalte ich: "SyntaxError: (irb): 17: Syntaxfehler, unerwarteter TAMPER, erwartet $ end"
Lars Haugseth
Zwischen mapund dem kaufmännischen Und muss ein Leerzeichen stehen . Und Sie brauchen den Splat-Operator auch nicht vor dem $<, also würde die gesamte Zeile so aussehen : a=$<.map &:to_i. ;)
Ventero
Ah, nochmals vielen Dank, es war der Splat, der die Syntax ruinierte.
Lars Haugseth
2

JavaScript (161)

P=parseInt;L=prompt().split(',');S=function(A)A.reduce(function(a,b)P(a)+P(b),0);R=[i for(i in L)if(S(L.slice(0,i))==S(L.slice(P(i)+1)))];alert(R.length>0?R:-1);

http://jsfiddle.net/6qYQv/1/

mellamokb
quelle
2

Scala, 108

val l=readline().split(" ").map(w=>w.toInt)
for(i<-0 to l.length-1
if l.take(i).sum==l.drop(i+1).sum)yield i
Benutzer unbekannt
quelle
2

J (12 Zeichen)

Ein monadisches Verb in stillschweigender Notation, das einen Vektor von Gleichgewichtsindizes zurückgibt. Leerzeichen nur zur besseren Lesbarkeit eingefügt.

[: I. +/\. = +/\

Um dies zu erklären, beachten Sie zunächst die explizite Definition. yist der formale Parameter:

3 : 'I. (+/\. y) = (+/\ y)'
  • +fügt seine Argumente hinzu. /ist ein Adverb, das das Verb links davon zwischen die Mitglieder seines rechten Arguments einfügt, z. B. +/ 1 2 3 4dasselbe wie 1 + 2 + 3 + 4.
  • \ist ein Adverb, das das Verb links von ihm auf alle Präfixe des rechten Arguments anwendet. Wenn Sie beispielsweise <ein Kästchen um das Argument zeichnen, wird <\ 1 2 3 4erzeugt

    ┌─┬───┬─────┬───────┐
    │1│1 2│1 2 3│1 2 3 4│
    └─┴───┴─────┴───────┘
    
  • Somit +/\berechnet für jedes Präfixobjekt ihres rechten Arguments der Summe.

  • \.ist wie \, arbeitet aber mit Suffixen anstelle von Präfixen. Somit +/\.berechnet einen Vektor von Summen von Suffixen.
  • =führt einen artikelweisen Vergleich seiner Argumente durch. Zum Beispiel 1 1 3 3 = 1 2 3 4ergibt 1 0 1 0.
  • Somit (+/\. y) = (+/\ y)ergibt sich eins für alle Indizes, bei denen die Suffixsumme gleich der Präfixsumme ist, oder es wird ein Gleichgewicht erzeugt.
  • Gibt für Vektoren mit Nullen und Einsen I.einen Vektor der Indizes zurück, bei denen der Vektor eine Eins enthält.
FUZxxl
quelle
1

Python 2, 70

A=input()
e=i=s=0
for x in A:e=[e,~i][s*2==sum(A)-x];s+=x;i+=1
print~e

Die Idee ist, die laufende Summe zu verfolgen sund zu prüfen, ob sie die Hälfte der Summe des Arrays ohne das aktuelle Element ist und daher gleich der Summe des Arrays nach dem aktuellen Element ist. In diesem Fall aktualisieren wir den Gleichgewichtsindex auf den aktuellen Index. Der letzte Gleichgewichtsindex wird gedruckt oder der Anfangswert, -1falls keiner vorhanden ist.

Tatsächlich speichern wir das Bitkomplement des Gleichgewichtsindex, damit wir es stattdessen auf 0 initialisieren können.

xnor
quelle
0

Python - 114

i=map(lambda x:int(x),raw_input().split(" "));x=0
print map(lambda x:(sum(i[0:x])==sum(i[x+1::])),range(0,len(i)))

Python - 72

i=input()
print map(lambda x:sum(i[0:x])==sum(i[x+1::]),range(0,len(i)))

Gibt an, ob der angegebene Index ein Gleichgewichtsindex ist oder nicht, und druckt nicht die ganzzahligen Unabhängigkeiten, bei denen das Array ausgeglichen ist.

arrdem
quelle
Was meinst du damit, dass es kaputt geht? 6 ist ein Gleichgewichtsindex, da die Elemente davor Null ergeben, keine Elemente danach vorhanden sind und 50 ignoriert wird.
Joey Adams
AH. Vielen Dank für die Klarstellung Joey, ich wusste nicht, dass der Wert bei x ignoriert werden sollte.
Arrdem
0

PHP, 134 Zeichen

<?for($a=explode(",",fgets(STDIN));++$i<($c=count($a));$o.=$s==0?$i:"")for($n=$s=0;$n<$c;)$s+=$n<$i?$a[$n++]:-$a[++$n];echo$o?$o:"-1";

Ich habe einen Juckreiz, dass dies alles andere als ein optimales PHP-Golfspiel ist, aber mir geht einfach der Dampf aus (Gehirn). Zumindest ist es kürzer als mit array_sum und array_splice :-)

Samuli K.
quelle
0

PHP (81)

for($i=count($a)-1,$c=0;$i+1&&$c!=(array_sum($a)-$a[$i])/2;$c+=$a[$i--]);echo $i;

http://3v4l.org/qJvhO

Da keine Eingabe angegeben wurde, muss diese mit dem Array als Variable initialisiert werden $a.

Stephen
quelle