Napisz program lub funkcję, która pobierze niepustą listę liczb całkowitych dodatnich. Możesz założyć, że jest on wprowadzany w rozsądnym dogodnym formacie, takim jak "1 2 3 4"lub [1, 2, 3, 4].

Liczby na liście wprowadzania reprezentują wycinki pełnego wykresu kołowego, gdzie każdy rozmiar wycinka jest proporcjonalny do odpowiadającej mu liczby, a wszystkie wycinki są rozmieszczone wokół wykresu w podanej kolejności.

Na przykład ciasto dla 1 2 3 4:

Pytanie, na które musi odpowiedzieć kod, brzmi: czy wykres kołowy jest kiedykolwiek podzielony na dwie części ? To znaczy, czy jest jakaś idealnie prosta linia z jednej strony koła na drugą, dzieląca ją symetrycznie na dwie części?

Trzeba wstawić truthy wartość, jeśli istnieje co najmniej jeden dwusieczna i wyprowadzać falsy wartość jeśli nie ma nikogo .

W tym 1 2 3 4przykładzie istnieje podział między, 4 1a 2 3więc wynik byłby prawdziwy.

Ale dla danych wejściowych 1 2 3 4 5nie ma dwusiecznych, więc dane wyjściowe byłyby fałszywe:

Dodatkowe przykłady

Różne układanie liczb może usuwać dwusieczne.
np. 2 1 3 4→ falsy:

Jeśli na liście wejściowej znajduje się tylko jedna liczba, ciasto nie jest podzielone na dwie części.
np. 10→ falsy:

Może być wiele dwusiecznych. Dopóki jest więcej niż zero, dane wyjściowe są zgodne z prawdą.
np. 6 6 12 12 12 11 1 12→ prawda: (są tutaj 3 dwusieczne)

Podziały mogą istnieć, nawet jeśli nie są wizualnie oczywiste.
np. 1000000 1000001→ falsy:

np. 1000000 1000001 1→ prawda:

(Podziękowania dla nces.ed.gov za wygenerowanie wykresów kołowych.)

Przypadki testowe

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

Punktacja

Najkrótszy kod w bajtach wygrywa. Tiebreaker to wcześniejsza odpowiedź.

J, 18 bajtów

5 bajtów dzięki Dennisowi.

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

@HelkaHomba : Nie.

Stosowanie

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

Nie golfił

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

Poprzednia 23-bajtowa wersja:

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

Stosowanie

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

Nie golfił

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

Wyjaśnienie

Suma wszystkich podciągów obliczana jest przez black_magic. +/\Obliczania sum częściowych.

Na przykład a b c dstaje się a a+b a+b+c a+b+c+d.

-/~Następnie konstruuje tabelę odejmowania na podstawie danych wejściowych, więc x y zstaje się:

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

Po zastosowaniu do a a+b a+b+c a+b+c+dwyniku będzie:

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

Obliczało to sumy wszystkich podciągów, które nie zawierają a.

To gwarantuje, że wystarczy, ponieważ jeśli jedna sekcja zawiera a, druga sekcja nie będzie zawierać, aa także nie będzie się owijała.

Galaretka , 9 8 bajtów

Ḥ+\©_Sf®

Zwraca niepustą listę (prawda) lub pustą listę (fałsz). Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Ḥ+\©_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.

Julia, 34 30 29 bajtów

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

Dzięki @GlenO za grę w golfa z 1 bajtu!

Wypróbuj online!

Jak to działa

Po zapisaniu skumulowanej sumy 2x w x odejmujemy wektor wiersza x ' od wektora kolumny x , uzyskując macierz wszystkich możliwych różnic. Zasadniczo, to oblicza sumy wszystkich sąsiednich subarrays z X , które nie zawierają pierwszą wartość, swoje negatywy i 0 „sw przekątnej.

Na koniec sprawdzamy, czy suma oryginalnej tablicy x należy do wygenerowanej macierzy. W takim przypadku suma co najmniej jednej z sąsiednich podlist jest równa dokładnie połowie połowy całej listy, co oznacza, że ​​istnieje co najmniej jeden dwusieczny.

Python 2, 64 bajty

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

Rekurencyjnie próbuje usunąć elementy z przodu lub końca, dopóki suma tego, co pozostaje, jest równa sumie tego, co zostało usunięte, które jest przechowywane s. Zajmuje wykładniczy czas na długości listy.

Dennis zapisał 3 bajty pop.

Haskell, 41 bajtów

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

Chodzi o sprawdzenie, czy istnieje lista podrzędna, lktórej suma jest równa sum l/2. Sumy tych podlist generujemy jako scanr(:)[]l>>=scanl(+)0. Zobaczmy, jak to działal=[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

Stare 43 bajty:

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

Generuje listę csum skumulowanych. Następnie sprawdza, czy dowolne dwie z tych sum różnią się sum l/2, sprawdzając, czy jest to element listy różnic (-)<$>c<*>c.

Pyth, 10 9 bajtów

}sQmysd.:

Przetestuj w kompilatorze Pyth .

Jak to działa

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

Właściwie 21 bajtów

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

Wypróbuj online!

Ten program wypisuje 0dla przypadków fałszywych i dodatnią liczbę całkowitą dla przypadków prawdziwych.

Wyjaśnienie:

;Σ@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)

Wersja niekonkurencyjna, 10 bajtów

;Σ@2*σ;)-∩

Wypróbuj online!

Ten program wyświetla pustą listę fałszywych przypadków i niepustą listę w przeciwnym razie. Zasadniczo jest to odpowiedź na galaretkę Dennisa . Jest niekonkurencyjny, ponieważ funkcja skumulowanej sumy i różnicy wektoryzacji po dacie wyzwania.

Wyjaśnienie:

;Σ@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

Python 2, 76 74 70 66 bajtów

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

Dzięki @xnor za grę w golfa przy 4 8 bajtach!

Przetestuj na Ideone . (z wyłączeniem większych przypadków testowych)

MATL , 10 bajtów

EYst!-Gs=z

Dane wyjściowe to liczba dwusiecznych.

Wypróbuj online!

Wyjaśnienie

To samo podejście, co odpowiedź Dennisa Julii .

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 

Rubin, 60 53 bajty

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

Generuje wszystkie możliwe partycje, biorąc każdy obrót tablicy wejściowej, a następnie biorąc wszystkie wycinki o długości 1 .. n, gdzie njest rozmiar tablicy wejściowej. Następnie sprawdza, czy istnieje jakaś partycja z sumą równą połowie całkowitej sumy tablicy wejściowej.

JavaScript (ES6), 83 bajty

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

Generuje wszystkie możliwe sumy, a następnie sprawdza, czy połowa ostatniej sumy (która jest sumą całej listy) pojawia się na liście. (Generowanie sum w nieco niezręcznej kolejności w celu ustalenia sumy, którą muszę mieć na końcu, powoduje zapis 4 bajtów).

Dyalog APL, 12 bajtów

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

Przetestuj za pomocą TryAPL .

Jak to działa

+/∊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.

Python 2 , 47 bajtów

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

Wypróbuj online!

Wróciłem 2,75 lat później, aby pokonać moje stare rozwiązanie o ponad 25%, stosując nową metodę.

Ta dłuższa o 1 bajt wersja jest nieco jaśniejsza.

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

Wypróbuj online!

Chodzi o to, aby przechowywać zestaw sum skumulowanych tjako bity k, ustawiając bit 2*twskazujący, że tjest to suma skumulowana. Następnie sprawdzamy, czy dowolne dwie sumy skumulowane różnią się o połowę sumy listy (końcowe t), przesuwając bit ktak bardzo i robiąc bitowo &z oryginałem, aby zobaczyć, że wynik jest niezerowy (prawda).

APL, 25 znaków

Zakładając, że lista jest podana w X ← 1 2 3 4.

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

Wyjaśnienie:

Pierwsza uwaga, że ​​APL ocenia formę od prawej do lewej. Następnie:

• X←⎕ pobiera dane wejściowe użytkownika i zapisuje je X

• ⍴X podaje długość X

• ⍳⍴X liczby od 1 do ⍴X

• A ⍺i ⍵in {2×+/⍺↑⍵↓X,X}to lewy i prawy argument funkcji dynamicznej, którą definiujemy w nawiasach klamrowych.

  • Teraz ⍺↑⍵↓X,Xczęść: X,Xpo prostu konkatenuje X ze sobą; ↑i ↓biorą i upuszczają.
  • +/zmniejsza / zwija się +nad listą po prawej stronie

  Więc 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 jest tylko idx ∘.brace idx . ( ⍨to mapa ukośna; ∘.jest produktem zewnętrznym)

  Więc to daje nam ⍴XBy⍴X matrycę, która zawiera dwa razy sumy wszystkich podłączonych podlist.

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

  Ostatnią rzeczą, którą musimy zrobić, to sprawdzić, czy suma X jest gdzieś w tej macierzy.

• Z czym robimy (+/X)∊matrix.

Brachylog , 6 bajtów

sj+~+?

Wypróbuj online!

Wyprowadza przez sukces lub awarię, drukowanie true.lub false.jeśli działa jako program.

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

C, 161 145 129 bajtów

• zapisano kilka bajtów dzięki @LeakyNun
• zapisano kilka bajtów dzięki @ceilingcat

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 spróbuj online

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
}

Haskell, 68 bajtów

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

Funkcja fnajpierw tworzy listę sum wszystkich możliwych wycinków danej listy. Następnie porównuje się z całkowitą sumą elementów listy. Jeśli otrzymamy w pewnym momencie połowę całkowitej sumy, wiemy, że mamy podział. Używam również faktu, że jeśli ty takelub dropwięcej elementów niż jest na liście, Haskell nie zgłasza błędu.

Mathematica, 48 bajtów

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

Funkcja anonimowa, podobna w działaniu do wielu innych odpowiedzi.

Outer[Plus, #, -#]podczas działania Accumulate@# (który z kolei działa na listę danych wejściowych, podając listę kolejnych sum) generuje zasadniczo tę samą tabelę, co na dole odpowiedzi Dziurawej Zakonnicy.

!FreeQ[..., Last@#/2]sprawdza, czy nie(Last@#)/2 jest nieobecny w wynikowej tabeli, orazLast@# jest ostatnim z kolejnych sum, tj. sumą wszystkich elementów listy wejściowej.

Jeśli ta odpowiedź jest nieco interesująca, nie jest to spowodowane nowym algorytmem, ale bardziej sztuczkami specyficznymi dla Mathematica; np. !FreeQjest fajny w porównaniu do MemberQ, ponieważ nie wymaga spłaszczania stołu, sprawdza i oszczędza bajt.

APL (NARS), znaki 95, bajty 190

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

Rozważ jedną tablicę danych wejściowych z 4 elementów: 1 2 3 4. Jak możemy wybrać użyteczne dla tej partycji ćwiczenia tego zestawu? Po tym, jak niektórzy uważają, że podział tych 4 elementów, których możemy użyć, jest opisany liczbą binarną po lewej stronie:

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

(1001 lub 1011 ecc może być w tym zestawie, ale już mamy 0110 i 0100 ecc), więc wystarczy napisać jedną funkcję, która z liczby elementów tablicy wejściowej zbuduje te liczby binarne ...

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

że z wejścia 1 2 4 8 [2 ^ 0..lenBytesArgument-1] znajdź 3 6 12, 7 14, 15; więc znajdź binarny z tych liczb i używając ich znajdź odpowiednie partycje tablicy wejściowej ... Testowałem funkcję c tylko dla tego wejściowego 4 elementów, ale wydaje się, że jest w porządku dla innej liczby elementów ...

test:

  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