Listy samoograniczające
Rozważ niepustą listę L zawierającą nieujemne liczby całkowite. Prowadzony w L oznacza ciągłą podlistę jednakowych elementów, które nie mogą być dłuższe. Na przykład przebiegi [0,0,1,1,3,3,3,3,2,1,1] wynoszą [0,0], [1,1], [3,3,3], [2 ], [1,1] . Lista L jest samoograniczająca, jeśli dla każdej liczby całkowitej N ≥ 1 liczba wystąpień N jest mniejsza lub równa liczbie przebiegów N-1 . Powyższa lista nie jest samoograniczająca, ponieważ występują 4 wystąpienia 1 , ale tylko jeden ciąg 0 s.
Oto przykład listy samoograniczającej się: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . To ma
- 5 serii 0 i 5 wystąpień 1 ,
- 4 serie po 1 i 2 wystąpieniach po 2 ,
- 2 serie 2 i 1 wystąpienie 3 ,
- 1 seria 3 i 1 wystąpienie 4 ,
- 1 seria 4 i brak wystąpień 5 ,
- brak wystąpień innych liczb całkowitych.
Zadanie
Twoim zadaniem jest zdecydować, czy lista jest samoograniczająca. Mówiąc ściślej, twój wkład będzie niepustą listą nieujemnych liczb całkowitych. Jeśli lista jest samoograniczająca, twoje wyniki będą zgodne z prawdą; w przeciwnym razie będzie to fałsz. Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie.
Najniższa liczba bajtów w każdym języku programowania jest zwycięzcą. Obowiązują standardowe zasady gry w golfa .
Przypadki testowe
Prawdziwe przypadki:
[0]
[1,0]
[0,1,1,0,2]
[3,1,1,0,0,2,0,0]
[5,0,4,1,3,0,2,2,0,1,1,1,0]
[0,0,1,1,0,0,1,1,0,0,2,2,0,0]
[6,0,0,0,2,2,1,0,5,0,3,4,0,1,1,1]
[5,0,1,0,0,0,0,4,0,3,1,1,1,2,2,0,0,0,0,0]
[4,5,1,3,2,0,5,2,0,3,0,1,0,1,0,0,0,1,0,0,1,0,3,4,4,0,2,6,0,2,6]
[0,4,1,3,10,6,0,1,3,7,9,5,5,0,7,4,2,2,5,0,1,3,8,8,11,0,0,6,2,1,1,2,0,4]
Instancje Falsy:
[2]
[1,1,0]
[0,0,1,1,1,0,0,2]
[0,1,0,1,1,2,2,3,0,0,4,6]
[1,1,2,1,2,0,2,0,3,0,0,2,2,1,2,3,2,0,1,1,1,0,0,3,3,0]
[3,4,1,0,0,0,5,5,0,2,2,0,0,0,0,0,2,0,1,1,0,4,3,5,4,3]
[1,0,0,0,2,5,3,1,1,0,3,3,1,3,5,4,0,4,0,0,2,0,2,1,1,5,0,0,2,4,4,0,2,0,1,4,4,2,3,3,5,3,4,0,2,0,5]
[4,3,1,0,0,4,6,6,1,0,1,2,1,3,0,1,0,2,0,3,4,0,2,1,1,3,0,2,2,2,0,5,5,0,5,2,5,5,0,4,3,2,3,1,1,3,5,1,4,1,6,2,6,2,4,0,4,0,4,5,3,3,0,0,6,1,0,0,0,6,2,1,0,1,2,6,2,4]
[5,1,1,1,0,2,0,6,1,0,2,1,2,2,5,3,1,0,0,0,3,2,3,0,1,1,0,1,0,1,1,2,0,6,4,1,2,1,1,6,4,1,2,2,4,0,1,2,2,1,3,0,1,2,0,0,0,2,0,2,2,0,1,0,0,1,3,0,0,0,6,2,0,1,0,1,2,1,1,1,0,4,0,0,5,2,0,0,0,4,1,2,2,2,2,0,5,3,2,4,5,0,5]
[2]
, ale takie przypadki powinny być fałszywe, tak.Odpowiedzi:
Perl 6 , 29 bajtów
Wypróbuj online!
Bardzo miłe wyzwanie dla Perla 6. Używa operatora podzbioru w Torby (zestawy ważone liczbą całkowitą). Wyjaśnienie:
źródło
JavaScript (ES6),
9289 bajtówWypróbuj online!
W jaki sposób?
Tablica c [] służy do przechowywania zarówno liczby uruchomień, jak i liczby wystąpień liczb całkowitych. Trasy są zapisywane w nieujemna liczbę całkowitą, a wskaźników zdarzenia są przechowywane w 1's-dopełniacza indeksach ( C [1] = liczba 0 's, C [-2] = liczba 1 jest, etc.).
Indeksy ujemne są w rzeczywistości zapisywane jako właściwości bazowego obiektu tablicowego, a .some () nie iteruje nad nimi.
źródło
Perl 5
-p
,494844 bajtówWypróbuj online!
źródło
Galaretka , 10 bajtów
Wypróbuj online!
Jak to działa
źródło
Galaretka , 19 bajtów
Wypróbuj online!
źródło
Galaretka , 17 bajtów
Wypróbuj online!
źródło
Python 3 , 94 bajty
Wypróbuj online!
źródło
sum(1for ... if x==j!=y)
=>sum(x==j!=y for ...)
.Japt , 21 bajtów
Przetestuj online!
źródło
Stax ,
139 bajtówDennis znalazł znacznie lepszy algorytm . Bezwstydnie przeniosłem go na stax.
Uruchom i debuguj online
Rozpakowane, nieprzygotowane i skomentowane, tak to wygląda.
Uruchom ten
Stara odpowiedź:
Uruchom i debuguj
Powtarza dane wejściowe i sprawdza warunki:
> 0
?occurrences(element) >= runs(element - 1)
?Jeśli którykolwiek z tych warunków jest spełniony dla elementu, ten element jest zgodny. Iff wszystkie elementy są zgodne, wynik jest
1
.Oto rozpakowana, nieposortowana, skomentowana reprezentacja tego samego programu.
Uruchom ten
źródło
Haskell, 80 bajtów
Wypróbuj online!
źródło