Schreiben Sie ein Programm oder eine Funktion, die eine nicht leere Liste positiver Ganzzahlen enthält. Sie können davon ausgehen, dass die Eingabe in einem angemessenen, praktischen Format wie "1 2 3 4"
oder erfolgt [1, 2, 3, 4]
.
Die Zahlen in der Eingabeliste stellen die Segmente eines vollständigen Kreisdiagramms dar, wobei jede Segmentgröße proportional zu ihrer entsprechenden Nummer ist und alle Segmente in der angegebenen Reihenfolge um das Diagramm angeordnet sind.
Zum Beispiel ist der Kuchen für 1 2 3 4
:
Die Frage, die Ihr Code beantworten muss, lautet: Ist das Kreisdiagramm jemals halbiert ? Das heißt, gibt es jemals eine vollkommen gerade Linie von einer Seite des Kreises zur anderen, die ihn symmetrisch in zwei Teile teilt?
Sie müssen einen Wahrheitswert ausgeben , wenn es mindestens eine Halbierende gibt, und einen falschen Wert, wenn es keine gibt .
In dem 1 2 3 4
Beispiel liegt eine Halbierung zwischen 4 1
und 2 3
daher wäre die Ausgabe wahr.
Für die Eingabe 1 2 3 4 5
gibt es jedoch keine Halbierungslinie, sodass die Ausgabe falsch wäre:
Zusätzliche Beispiele
Wenn Sie die Zahlen anders anordnen, werden möglicherweise Bisektoren entfernt.
zB 2 1 3 4
→ falsch:
Befindet sich nur eine Zahl in der Eingabeliste, wird der Kuchen nicht halbiert.
zB 10
→ falsch:
Es können mehrere Bisektoren vorhanden sein. Solange es mehr als Null gibt, ist die Ausgabe wahr.
zB 6 6 12 12 12 11 1 12
→ wahrheit: (hier sind 3 bisektoren)
Teilungen können auch dann existieren, wenn sie visuell nicht offensichtlich sind.
zB 1000000 1000001
→ falsch:
zB 1000000 1000001 1
→ wahrheit:
(Danke an nces.ed.gov für die Erstellung der Tortendiagramme.)
Testfälle
Truthy
1 2 3 4
6 6 12 12 12 11 1 12
1000000 1000001 1
1 2 3
1 1
42 42
1 17 9 13 2 7 3
3 1 2
10 20 10
Falsy
1 2 3 4 5
2 1 3 4
10
1000000 1000001
1
1 2
3 1 1
1 2 1 2 1 2
10 20 10 1
Wertung
Der kürzeste Code in Bytes gewinnt. Tiebreaker ist frühere Antwort.
quelle
Antworten:
J, 18 Bytes
5 Bytes dank Dennis.
@HelkaHomba : Nein.
Verwendungszweck
Ungolfed
Vorherige 23-Byte-Version:
Verwendungszweck
Ungolfed
Erläuterung
Die Summe aller Teilstrings wird vom black_magic berechnet. Die
+/\
berechnen die Teilsummen.Zum Beispiel
a b c d
wirda a+b a+b+c a+b+c+d
.Das
-/~
Konstruiert dann eine Subtraktionstabelle basierend auf der Eingabe, sox y z
wird:Bei Anwendung auf
a a+b a+b+c a+b+c+d
würde das Ergebnis lauten:Dies berechnet die Summen aller Teilzeichenfolgen, die nicht enthalten sind
a
.Dies ist garantiert ausreichend, da wenn eine Halbierung enthält
a
, die andere Halbierung nicht enthälta
und sich auch nicht umgibt.quelle
+/e.&,2*+/\\.
Gelee ,
98 BytesGibt eine nicht leere Liste (wahr) oder eine leere Liste (falsch) zurück. Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
quelle
Julia,
343029 BytesVielen Dank an @GlenO für das Golfen ab 1 Byte!
Probieren Sie es online!
Wie es funktioniert
Nach dem Speichern der kumulativen Summe von 2x in x subtrahieren wir den Zeilenvektor x ' vom Spaltenvektor x und erhalten die Matrix aller möglichen Differenzen. Im Wesentlichen berechnet diese die Summen aller benachbarten Sub - Arrays von x , die ihre Negativ nicht den ersten Wert enthält, und 0 ‚s in den Diagonalen.
Schließlich testen wir, ob die Summe des ursprünglichen Arrays x zur generierten Matrix gehört. Wenn dies der Fall ist, entspricht die Summe von mindestens einer der benachbarten Unterlisten genau der Hälfte der Summe der gesamten Liste, was bedeutet, dass mindestens eine Halbierende vorhanden ist.
quelle
Python 2, 64 Bytes
Versucht rekursiv, Elemente von der Front oder dem Ende zu entfernen, bis die Summe der verbleibenden Elemente der Summe der gelöschten Elemente entspricht, die gespeichert sind
s
. Nimmt Zeit exponentiell in der Listenlänge.Dennis sparte 3 Bytes mit
pop
.quelle
f=lambda l,s=0:l and(sum(l)==s)*l+f(l[1:],s+l[0])+f(l,s+l.pop())
Haskell, 41 Bytes
Die Idee ist zu überprüfen, ob es eine Unterliste gibt,
l
deren Summe gleich istsum l/2
. Wir generieren die Summen dieser Unterlisten alsscanr(:)[]l>>=scanl(+)0
. Schauen wir uns an, wie das funktioniertl=[1,2,3]
Alte 43 Bytes:
Erzeugt die Liste
c
der kumulierten Summen. Überprüfen Sie dann, ob sich zwei dieser Summen unterscheiden, indem Siesum l/2
prüfen, ob es sich um ein Element der Liste der Unterschiede handelt(-)<$>c<*>c
.quelle
Pyth,
109 BytesTesten Sie es im Pyth-Compiler .
Wie es funktioniert
quelle
Eigentlich 21 Bytes
Probieren Sie es online!
Dieses Programm gibt a
0
für falsche Fälle und eine positive Ganzzahl für wahre Fälle aus.Erläuterung:
Nicht konkurrierende Version, 10 Bytes
Probieren Sie es online!
Dieses Programm gibt eine leere Liste für falsche Fälle und eine nicht leere Liste für andere Fälle aus. Es ist im Wesentlichen eine Portierung von Dennis 'Jelly-Antwort . Es ist nicht konkurrierend, da die kumulative Summe und die vektorisierte Differenzfunktionalität die Herausforderung nach dem Datum bestimmen.
Erläuterung:
quelle
Python 2,
76747066 BytesVielen Dank an @xnor für das Golfen mit
4 bis8 Bytes!Teste es auf Ideone . (größere Testfälle ausgeschlossen)
quelle
n=sum(x)
zu tunn in ...
; Es tut nicht weh, einen größeren Wert für zu verwendenn
.MATL , 10 Bytes
Die Ausgabe ist die Anzahl der Bisektoren.
Probieren Sie es online!
Erläuterung
Gleicher Ansatz wie Dennis 'Julia-Antwort .
quelle
Rubin,
6053 BytesGeneriert alle möglichen Partitionen, indem jede Umdrehung des Eingabearrays und anschließend alle Segmente der Länge 1 ... verwendet
n
werden. Dabein
handelt es sich um die Größe des Eingabearrays. Überprüft dann, ob eine Partition vorhanden ist, deren Summe die Hälfte der Gesamtsumme des Eingabearrays beträgt.quelle
JavaScript (ES6), 83 Byte
Generiert alle möglichen Summen und prüft dann, ob die Hälfte der letzten Summe (die Summe der gesamten Liste) in der Liste angezeigt wird. (Das Erzeugen der Summen in der etwas umständlichen Reihenfolge, um die Summe zu arrangieren, die ich zuletzt sein muss, spart 4 Bytes.)
quelle
Dyalog APL, 12 Bytes
Testen Sie es mit TryAPL .
Wie es funktioniert
quelle
Python 2 , 47 Bytes
Probieren Sie es online!
Ich bin 2,75 Jahre später zurück, um meine alte Lösung mit einer neuen Methode um über 25% zu übertreffen .
Diese 1 Byte längere Version ist etwas übersichtlicher.
Probieren Sie es online!
Die Idee ist, die Menge der kumulativen Summen
t
als Bits von zu speichern, wobei das gesetztek
Bit2*t
anzeigt, dasst
es sich um eine kumulative Summe handelt. Dann prüfen wir, ob sich zwei kumulative Summen um die Hälfte der Listensumme (finalt
) unterscheiden, indem wirk
dies bitweise verschieben und&
mit dem Original arbeiten, um zu sehen, dass das Ergebnis ungleich Null ist (truey).quelle
APL, 25 Zeichen
Vorausgesetzt, die Liste ist in gegebenX ← 1 2 3 4
.Erläuterung:
Beachten Sie zunächst, dass APL das Formular von rechts nach links auswertet. Dann:
X←⎕
Nimmt die Benutzereingabe und speichert sie inX
⍴X
gibt die Länge vonX
⍳⍴X
die Zahlen von 1 bis⍴X
Das
⍺
und⍵
in{2×+/⍺↑⍵↓X,X}
sind das linke und rechte Argument für eine dyadische Funktion, die wir in geschweiften Klammern definieren.⍺↑⍵↓X,X
Teil:X,X
Verkettet X einfach mit sich selbst;↑
und↓
nehmen und fallen lassen.+/
verkleinert / faltet+
die Liste auf der rechten Seite umAlso
2 {2×+/⍺↑⍵↓X,X} 1
=2×+/2↑1↓X,X
=2×+/2↑1↓1 2 3 4 1 2 3 4
==
2×+/2↑2 3 4 1 2 3 4
=2×+/2 3
=2×5
=10
.∘.brace⍨idx
ist einfachidx ∘.brace idx
. (⍨
ist die diagonale Karte;∘.
ist das äußere Produkt)Das ergibt also eine
⍴X
By-⍴X
Matrix, die die doppelte Summe aller verbundenen Unterlisten enthält.Das Letzte, was wir tun müssen, ist zu überprüfen, ob die Summe von
X
irgendwo in dieser Matrix ist.(+/X)∊matrix
.quelle
Brachylog , 6 Bytes
Probieren Sie es online!
Ausgaben durch Erfolg oder Misserfolg, Drucken
true.
oderfalse.
Ausführen als Programm.quelle
C
161145129 BytesUngolfed online versuchen
quelle
i<n;i++
zui++<n
(auch wenn man mit einigen Verschiebungen behandeln müssen kann.Haskell, 68 Bytes
Die Funktion
f
erstellt zunächst eine Liste der Summen aller möglichen Schichten der angegebenen Liste. Dann vergleicht es mit der Gesamtsumme der Listenelemente. Wenn wir irgendwann die Hälfte der Gesamtsumme bekommen, dann wissen wir, dass wir eine Halbierung haben. Ich benutze auch die Tatsache, dass Haskell keinen Fehler auslöst , wenn Sietake
oderdrop
mehr Elemente in der Liste enthalten sind.quelle
Mathematica, 48 Bytes
Anonyme Funktion, ähnlich wie bei den zahlreichen anderen Antworten.
Outer[Plus, #, -#]
Wenn Sie aufAccumulate@#
(was wiederum auf die Eingabeliste einwirkt und eine Liste aufeinanderfolgender Summen angibt) einwirken , wird im Wesentlichen dieselbe Tabelle wie am Ende der Antwort von Leaky Nun generiert.!FreeQ[..., Last@#/2]
überprüft , ob(Last@#)/2
ist , nicht aus der resultierenden Tabelle abwesend ist , undLast@#
ist der letzte der aufeinanderfolgenden Summen, also die Summe aller Elemente der Eingabeliste.Wenn diese Antwort etwas interessant ist, liegt es nicht an einem neuen Algorithmus, sondern eher an den Tricks, die für Mathematica spezifisch sind. zB
!FreeQ
ist nett im Vergleich zuMemberQ
, da es keine Reduzierung der Tabelle erfordert, die es prüft, und es ein Byte speichert.quelle
!FreeQ[2Tr/@Subsequences@#,Tr@#]&
sollte funktionieren, aber ich werde 10.4 nicht zur Verfügung haben, um es für die nächsten 10 Tage oder so zu testen.APL (NARS), Zeichen 95, Bytes 190
Betrachten Sie eine Reihe von Eingaben mit 4 Elementen: 1 2 3 4. Wie können wir die für diese Übung nützliche Partition dieses Satzes auswählen? Nachdem einige der Meinung sind, dass die Partition dieser 4 Elemente, die wir verwenden können, in der Binärzahl auf der linken Seite beschrieben ist:
(1001 oder 1011 ecc könnten in dieser Menge sein, aber wir haben bereits 0110 und 0100 ecc). Man muss also nur eine Funktion schreiben, die aus der Anzahl der Elemente des Eingabearrays diese Binärzahlen aufbaut.
die aus Eingabe 1 2 4 8 [2 ^ 0..lenBytesArgument-1] find 3 6 12, 7 14, 15; Also finde binäre Werte dieser Zahlen und benutze sie, um die richtigen Partitionen des Eingabearrays zu finden ... Ich habe die c-Funktion nur für diese 4 Eingabeelemente getestet, aber anscheinend ist sie für eine andere Anzahl von Elementen in Ordnung ...
Prüfung:
quelle