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 4
przykładzie istnieje podział między, 4 1
a 2 3
więc wynik byłby prawdziwy.
Ale dla danych wejściowych 1 2 3 4 5
nie 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ź.
źródło
Odpowiedzi:
J, 18 bajtów
5 bajtów dzięki Dennisowi.
@HelkaHomba : Nie.
Stosowanie
Nie golfił
Poprzednia 23-bajtowa wersja:
Stosowanie
Nie golfił
Wyjaśnienie
Suma wszystkich podciągów obliczana jest przez black_magic.
+/\
Obliczania sum częściowych.Na przykład
a b c d
staje sięa a+b a+b+c a+b+c+d
.-/~
Następnie konstruuje tabelę odejmowania na podstawie danych wejściowych, więcx y z
staje się:Po zastosowaniu do
a a+b a+b+c a+b+c+d
wyniku będzie: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ć,a
a także nie będzie się owijała.źródło
+/e.&,2*+/\\.
Galaretka ,
98 bajtówZwraca niepustą listę (prawda) lub pustą listę (fałsz). Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
Jak to działa
źródło
Julia,
343029 bajtówDzię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.
źródło
Python 2, 64 bajty
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
.źródło
f=lambda l,s=0:l and(sum(l)==s)*l+f(l[1:],s+l[0])+f(l,s+l.pop())
Haskell, 41 bajtów
Chodzi o sprawdzenie, czy istnieje lista podrzędna,
l
której suma jest równasum l/2
. Sumy tych podlist generujemy jakoscanr(:)[]l>>=scanl(+)0
. Zobaczmy, jak to działal=[1,2,3]
Stare 43 bajty:
Generuje listę
c
sum 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
.źródło
Pyth,
109 bajtówPrzetestuj w kompilatorze Pyth .
Jak to działa
źródło
Właściwie 21 bajtów
Wypróbuj online!
Ten program wypisuje
0
dla przypadków fałszywych i dodatnią liczbę całkowitą dla przypadków prawdziwych.Wyjaśnienie:
Wersja niekonkurencyjna, 10 bajtów
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:
źródło
Python 2,
76747066 bajtówDzięki @xnor za grę w golfa przy
48 bajtach!Przetestuj na Ideone . (z wyłączeniem większych przypadków testowych)
źródło
n=sum(x)
zrobićn in ...
; użycie większej wartości nie bolin
.MATL , 10 bajtów
Dane wyjściowe to liczba dwusiecznych.
Wypróbuj online!
Wyjaśnienie
To samo podejście, co odpowiedź Dennisa Julii .
źródło
Rubin,
6053 bajtyGeneruje 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
, gdzien
jest rozmiar tablicy wejściowej. Następnie sprawdza, czy istnieje jakaś partycja z sumą równą połowie całkowitej sumy tablicy wejściowej.źródło
JavaScript (ES6), 83 bajty
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).
źródło
Dyalog APL, 12 bajtów
Przetestuj za pomocą TryAPL .
Jak to działa
źródło
Python 2 , 47 bajtów
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.
Wypróbuj online!
Chodzi o to, aby przechowywać zestaw sum skumulowanych
t
jako bityk
, ustawiając bit2*t
wskazujący, żet
jest to suma skumulowana. Następnie sprawdzamy, czy dowolne dwie sumy skumulowane różnią się o połowę sumy listy (końcowet
), przesuwając bitk
tak bardzo i robiąc bitowo&
z oryginałem, aby zobaczyć, że wynik jest niezerowy (prawda).źródło
APL, 25 znaków
Zakładając, że lista jest podana wX ← 1 2 3 4
.Wyjaśnienie:
Pierwsza uwaga, że APL ocenia formę od prawej do lewej. Następnie:
X←⎕
pobiera dane wejściowe użytkownika i zapisuje jeX
⍴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.⍺↑⍵↓X,X
część:X,X
po prostu konkatenuje X ze sobą;↑
i↓
biorą i upuszczają.+/
zmniejsza / zwija się+
nad listą po prawej stronieWię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 tylkoidx ∘.brace idx
. (⍨
to mapa ukośna;∘.
jest produktem zewnętrznym)Więc to daje nam
⍴X
By⍴X
matrycę, która zawiera dwa razy sumy wszystkich podłączonych podlist.Ostatnią rzeczą, którą musimy zrobić, to sprawdzić, czy suma
X
jest gdzieś w tej macierzy.(+/X)∊matrix
.źródło
Brachylog , 6 bajtów
Wypróbuj online!
Wyprowadza przez sukces lub awarię, drukowanie
true.
lubfalse.
jeśli działa jako program.źródło
C,
161145129 bajtówUngolfed spróbuj online
źródło
i<n;i++
nai++<n
(choć być może będziesz musiał poradzić sobie z niektórymi przesunięciami.Haskell, 68 bajtów
Funkcja
f
najpierw 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 tytake
lubdrop
więcej elementów niż jest na liście, Haskell nie zgłasza błędu.źródło
Mathematica, 48 bajtów
Funkcja anonimowa, podobna w działaniu do wielu innych odpowiedzi.
Outer[Plus, #, -#]
podczas działaniaAccumulate@#
(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.
!FreeQ
jest fajny w porównaniu doMemberQ
, ponieważ nie wymaga spłaszczania stołu, sprawdza i oszczędza bajt.źródło
!FreeQ[2Tr/@Subsequences@#,Tr@#]&
powinien działać, ale nie będę miał 10.4 do przetestowania przez następne 10 dni.APL (NARS), znaki 95, bajty 190
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:
(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 ...
ż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:
źródło