Wurde mein Kuchen halbiert?

43

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:

1 2 3 4 Beispiel

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 4Beispiel liegt eine Halbierung zwischen 4 1und 2 3daher wäre die Ausgabe wahr.

Für die Eingabe 1 2 3 4 5gibt es jedoch keine Halbierungslinie, sodass die Ausgabe falsch wäre:

1 2 3 4 5 Beispiel

Zusätzliche Beispiele

Wenn Sie die Zahlen anders anordnen, werden möglicherweise Bisektoren entfernt.
zB 2 1 3 4→ falsch:

2 1 3 4 Beispiel

Befindet sich nur eine Zahl in der Eingabeliste, wird der Kuchen nicht halbiert.
zB 10→ falsch:

10 Beispiel

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)

6 6 12 12 11 1 12 Beispiel

Teilungen können auch dann existieren, wenn sie visuell nicht offensichtlich sind.
zB 1000000 1000001→ falsch:

1000000 1000001 Beispiel

zB 1000000 1000001 1→ wahrheit:

1000000 1000001 1 Beispiel

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

Calvins Hobbys
quelle
30
Ich glaube du meinst Kuchen geschnitten?
Alex A.
@HelkaHomba, können Sie die Sektoren neu anordnen, damit sie funktionieren, und ist das, was Sie mit "anders anordnen von Zahlen" gemeint haben, die Möglichkeit, Bisektoren zu entfernen?
Solomon Ucko
@SolomonUcko Sie dürfen die Sektoren nicht neu anordnen.
Calvins Hobbys
1
Nur [2 1 3 4] der falschen Fälle müssen tatsächlich ausgewertet werden. Die anderen falschen Fälle werden leicht verworfen, weil ihre Summe ungerade ist (oder ihre Länge <2 ist).
Benny Jobigan

Antworten:

12

J, 18 Bytes

5 Bytes dank Dennis.

+/e.[:,/2*+/\-/+/\

@HelkaHomba : Nein.

Verwendungszweck

>> f =: +/e.[:,/2*+/\-/+/\
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic  =: +/\-/+/\
doubled_bm   =: 2 * black_magic
flatten      =: ,/
sum          =: +/
is_member_of =: e.
f =: sum is_member_of monadic flatten doubled_bm

Vorherige 23-Byte-Version:

[:+/[:+/+/=+:@-/~@(+/\)

Verwendungszweck

>> f =: [:+/[:+/+/=+:@-/~@(+/\)
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic =: -/~@(+/\)
double      =: +:
equals      =: =
sum         =: +/
monadic     =: [:
of          =: @
f =: monadic sum monadic sum (sum equals double of black_magic)

Erläuterung

Die Summe aller Teilstrings wird vom black_magic berechnet. Die +/\berechnen die Teilsummen.

Zum Beispiel a b c dwird a a+b a+b+c a+b+c+d.

Das -/~Konstruiert dann eine Subtraktionstabelle basierend auf der Eingabe, so x y zwird:

x-x x-y x-z
y-x y-y y-z
z-x z-y z-z

Bei Anwendung auf a a+b a+b+c a+b+c+dwürde das Ergebnis lauten:

    0  -b -b-c -b-c-d
    b   0   -c   -c-d
  b+c   c    0     -d
b+c+d c+d    d      0

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ält aund sich auch nicht umgibt.

Undichte Nonne
quelle
3
Mit einigen Umstrukturierungen können Sie auf 13 Bytes kommen:+/e.&,2*+/\\.
Zgarb
10

Gelee , 9 8 Bytes

Ḥ+\©_Sf®

Gibt 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

Ḥ+\©_Sf®  Main link. Argument: A (list)

Ḥ         Double all integers in A.
 +\       Take the cumulative sum of 2A.
   ©      Copy; store the result in the register.
    _S    Subtract the sum of A from each partial sum of 2A.
      f®  Filter; intersect this list with the list in the register.
Dennis
quelle
7

Julia, 34 30 29 Bytes

!x=sum(x)∈cumsum!(x,2x).-x'

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

Dennis
quelle
15
Beobachten wir, wie Dennis 5 Antworten gibt, bevor irgendjemand anders eine gibt.
Calvins Hobbys
6

Python 2, 64 Bytes

f=lambda l,s=0:l>[]and(sum(l)==s)|f(l[1:],s+l[0])|f(l,s+l.pop())

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.

xnor
quelle
Eine seltsame Alternative, die Listen gibt:f=lambda l,s=0:l and(sum(l)==s)*l+f(l[1:],s+l[0])+f(l,s+l.pop())
xnor
5

Haskell, 41 Bytes

f l=elem(sum l/2)$scanr(:)[]l>>=scanl(+)0

Die Idee ist zu überprüfen, ob es eine Unterliste gibt, lderen Summe gleich ist sum l/2. Wir generieren die Summen dieser Unterlisten als scanr(:)[]l>>=scanl(+)0. Schauen wir uns an, wie das funktioniertl=[1,2,3]

>> scanr(:)[]l
[[1,2,3],[2,3],[3],[]] 
-- the suffixes of l

>> scanl(+)0 [2,3,4]
[0,2,5,9]
-- the cumulative sums of the input

>> scanr(:)[]l>>=scanl(+)0
[0,1,3,6,0,2,5,0,3,0]
-- the cumulative sums of the suffixes of l, flattened to a single list

Alte 43 Bytes:

f l|c<-scanl1(+)l=elem(sum l/2)$(-)<$>c<*>c

Erzeugt die Liste cder kumulierten Summen. Überprüfen Sie dann, ob sich zwei dieser Summen unterscheiden, indem Sie sum l/2prüfen, ob es sich um ein Element der Liste der Unterschiede handelt (-)<$>c<*>c.

xnor
quelle
4

Pyth, 10 9 Bytes

}sQmysd.:

Testen Sie es im Pyth-Compiler .

Wie es funktioniert

       .:  Generate the list of all adjacent sublists.
   m       Map over the result:
     sd       Add the integers of the sublist.
    y         Double the sum.
 sQ        Compute the sum of the input.
}          Check if it belongs to the list of doubled sublist sums.
Dennis
quelle
4

Eigentlich 21 Bytes

;Σ@2*;lR@τ╗`╜V♂Σi`Míu

Probieren Sie es online!

Dieses Programm gibt a 0für falsche Fälle und eine positive Ganzzahl für wahre Fälle aus.

Erläuterung:

;Σ@2*;lR@τ╗`╜V♂Σi`Míu
;Σ                     sum of copy of input
  @2*                  double values in other copy
     ;lR               copy, range(1, len(input)+1)
        @τ             append other copy to itself
          ╗            save in reg0
           `╜V♂Σi`M    map: generate cyclic cumulative sums
                   íu  1-based index of sum of input (0 if not found)

Nicht konkurrierende Version, 10 Bytes

;Σ@2*σ;)-∩

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:

;Σ@2*σ;)-∩
;Σ          sum of copy of input
  @2*       multiply values in other copy by 2
     σ;     two copies of cumulative sum
       )-   subtract sum of input from each element in one copy
         ∩  set intersection with other copy
Mego
quelle
4

Python 2, 76 74 70 66 Bytes

def f(x):n=sum(x);print n in[2*sum(x[k/n:k%n])for k in range(n*n)]

Vielen Dank an @xnor für das Golfen mit 4 bis 8 Bytes!

Teste es auf Ideone . (größere Testfälle ausgeschlossen)

Dennis
quelle
Ich erkannte , Sie tun können , n=sum(x)zu tun n in ...; Es tut nicht weh, einen größeren Wert für zu verwenden n.
xnor
Oh, das ist klug. Danke!
Dennis
3

MATL , 10 Bytes

EYst!-Gs=z

Die Ausgabe ist die Anzahl der Bisektoren.

Probieren Sie es online!

Erläuterung

Gleicher Ansatz wie Dennis 'Julia-Antwort .

E       % Implicit input. Multiply by 2 element-wise 
Ys      % Cumulative sum 
t!-     % Compute all pairwise differences. Gives a 2D array 
Gs      % Sum of input 
=       % Test for equality, element-wise 
z       % Number of nonzero elements. Implicit display 
Luis Mendo
quelle
3

Rubin, 60 53 Bytes

->a{a.any?{r=eval a*?+;a.rotate!.any?{|i|0==r-=2*i}}}

Generiert alle möglichen Partitionen, indem jede Umdrehung des Eingabearrays und anschließend alle Segmente der Länge 1 ... verwendet nwerden. Dabei nhandelt 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.

Ventero
quelle
2

JavaScript (ES6), 83 Byte

a=>a.map(_=>a.slice(--n).map(m=>s.push(t+=m),t=0),s=[],n=a.length)&&s.includes(t/2)

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

Neil
quelle
2

Dyalog APL, 12 Bytes

+/∊2×+\∘.-+\

Testen Sie es mit TryAPL .

Wie es funktioniert

+/∊2×+\∘.-+\  Monadic function train. Right argument: y (vector)

     +\   +\  Yield the cumulative sum of y.
       ∘.-    Compute all differences of all partial sums.
              This computes the sums of all adjacent subvectors of y that do not
              contain the first value, their negatives, and 0's in the diagonal.
   2×         Multiply all differences by 2.
+/            Yield the sum of y.
  ∊           Test for membership.
Dennis
quelle
2

Python 2 , 47 Bytes

k=t=1
for x in input():t<<=x;k|=t*t
print k&k/t

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.

k=t=0
for x in input():t+=x;k|=4**t
print k&k>>t

Probieren Sie es online!

Die Idee ist, die Menge der kumulativen Summen tals Bits von zu speichern, wobei das gesetzte kBit 2*tanzeigt, dass tes sich um eine kumulative Summe handelt. Dann prüfen wir, ob sich zwei kumulative Summen um die Hälfte der Listensumme (final t) unterscheiden, indem wir kdies bitweise verschieben und &mit dem Original arbeiten, um zu sehen, dass das Ergebnis ungleich Null ist (truey).

xnor
quelle
1

APL, 25 Zeichen

Vorausgesetzt, die Liste ist in gegeben X ← 1 2 3 4.

(+/X)∊∘.{2×+/⍺↑⍵↓X,X}⍨⍳⍴X←⎕

Erläuterung:

Beachten Sie zunächst, dass APL das Formular von rechts nach links auswertet. Dann:

  • X←⎕ Nimmt die Benutzereingabe und speichert sie in X

  • ⍴X gibt die Länge von X

  • ⍳⍴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.

    • Nun zum ⍺↑⍵↓X,XTeil: X,XVerkettet X einfach mit sich selbst; und nehmen und fallen lassen.
    • +/verkleinert / faltet +die Liste auf der rechten Seite um

    Also 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⍨idxist einfach idx ∘.brace idx. ( ist die diagonale Karte; ∘.ist das äußere Produkt)

    Das ergibt also eine ⍴XBy- ⍴XMatrix, die die doppelte Summe aller verbundenen Unterlisten enthält.

     4  6  8  2
    10 14 10  6
    18 16 14 12
    20 20 20 20
    

    Das Letzte, was wir tun müssen, ist zu überprüfen, ob die Summe von Xirgendwo in dieser Matrix ist.

  • Womit wir machen (+/X)∊matrix.
user2070206
quelle
1

Brachylog , 6 Bytes

sj+~+?

Probieren Sie es online!

Ausgaben durch Erfolg oder Misserfolg, Drucken true.oder false.Ausführen als Programm.

s         A contiguous sublist of the input
 j        with all of its items duplicated
  +       sums to
   ~+     the sum of the elements of
     ?    the input.
Nicht verwandte Zeichenfolge
quelle
1

C 161 145 129 Bytes

  • Dank @LeakyNun konnten einige Bytes gespart werden
  • Dank @ceilingcat konnten einige Bytes gespart werden
i;j;k;t;r;s;f(x,n)int*x;{for(t=i=k=r=0;i<n;)t+=x[i++];for(;++k<n;i=n)for(;i--;r|=2*s==t)for(s=0,j=i;j<i+k;)s+=x[j++%n];return r;}

Ungolfed online versuchen

int f(int*x,int n)
{
    int t=0;

    for(int i=0;i<n;i++)
    {
        t += x[i];
    }

    for(int k=1;k<n;k++) // subset-size
    {
        for(int i=0,s;i<n;i++) // where to start
        {
            s=0;

            for(int j=i;j<i+k;j++) // sum the subset
            {
                s+=x[j%n];
            }

            if(2*s==t) return 1; // TRUE
        }
    }

    return 0; // FALSE
}
Khaled.K
quelle
Vielleicht können Sie einige Bytes speichern , indem Sie die Deklarationen der Variablen auf der ersten Ebene bewegt und das Ändern i<n;i++zu i++<n(auch wenn man mit einigen Verschiebungen behandeln müssen kann.
Undichte Nun
0

Haskell, 68 Bytes

f l|x<-[0..length l]=any(sum l==)[2*(sum$take a$drop b l)|a<-x,b<-x]

Die Funktion ferstellt 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 Sie takeoder dropmehr Elemente in der Liste enthalten sind.

fehlerhaft
quelle
0

Mathematica, 48 Bytes

!FreeQ[Outer[Plus,#,-#],Last@#/2]&@Accumulate@#&

Anonyme Funktion, ähnlich wie bei den zahlreichen anderen Antworten.

Outer[Plus, #, -#]Wenn Sie auf Accumulate@#(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@#)/2ist , nicht aus der resultierenden Tabelle abwesend ist , und Last@#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 !FreeQist nett im Vergleich zu MemberQ, da es keine Reduzierung der Tabelle erfordert, die es prüft, und es ein Byte speichert.

LLlAMnYP
quelle
Ich denke, !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.
Martin Ender
@MartinEnder Es sieht auf jeden Fall so aus, als würde es funktionieren, aber ich bin auf 10.2, also habe ich das
LLlAMnYP
0

APL (NARS), Zeichen 95, Bytes 190

{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}

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:

0001,0010,0100,1000 2^(0..4) 1 2 4  8 
0011,0110,1100,                3 6 12
0111,1110,                       7 14
1111                               15

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

c←{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}

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:

  f←{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}
  f¨(1 2 3 4)(6 6 12 12 12 11 1 12)(1000000 1000001 1)(1 2 3)(1 1)(42 42)
1 1 1 1 1 1 
  f¨(1 2 3 4 5)(2 1 3 4)(,10)(1000000 1000001)(,1)(1 2)(3 1 1)
0 0 0 0 0 0 0 
RosLuP
quelle