Wprowadzenie
Załóżmy, że masz linijkę o numerach od 0 do r-1 . Umieszczasz mrówkę między dowolnymi dwoma liczbami, a zaczyna ona pełzać nieregularnie na linijce. Linijka jest tak wąska, że mrówka nie może chodzić z jednej pozycji do drugiej bez chodzenia po wszystkich liczbach pomiędzy. Gdy mrówka po raz pierwszy chodzi po numerze, zapisujesz go, a to daje permutację liczb r . Mówimy, że permutacja jest niespokojna, jeśli może być wygenerowana w ten sposób przez mrówkę. Alternatywnie permutacja p jest niespokojna, jeśli każdy wpis p [i] oprócz pierwszego znajduje się w odległości 1 od jakiegoś poprzedniego wpisu.
Przykłady
Permutacja długości-6
4, 3, 5, 2, 1, 0
jest mrówką, ponieważ 3 jest w odległości 1 od 4 , 5 w odległości 1 od 4 , 2 w odległości 1 od 3 , 1 w odległości 1 od 2 , a 0 w odległości 1 od 1 . Permutacja
3, 2, 5, 4, 1, 0
nie jest mrówką, ponieważ 5 nie znajduje się w odległości 1 od 3 lub 2 ; mrówka musiałaby przejść przez 4, aby dostać się do 5 .
Zadanie
Biorąc pod uwagę permutację liczb od 0 do r-1 dla około 1 ≤ r ≤ 100 w dowolnym rozsądnym formacie, wypisz prawdziwą wartość, jeśli permutacja jest antsy, i wartość fałsz, jeśli nie.
Przypadki testowe
[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True
Ciekawostka: dla r ≥ 1 istnieją dokładnie 2 kombinacje antsy r-1 o długości r .
Odpowiedzi:
Pyth, 7 bajtów
Wypróbuj online. (Uwzględniono tylko małe przypadki testowe ze względu na wykładniczy czas działania). Wyjścia 2 dla Truthy, 0 dla Falsey.
Innymi słowy,
gdzie
subseq
wypisuje, czy elementy pierwszej listy pojawiają się w kolejności na drugiej liście, niekoniecznie obok siebie.subseq
Odbywa się w Pyth biorąc wszystkie podgrupy drugiej listy, które utrzymują kolejność elementów, a licząc liczbę wystąpień pierwszej listy. To zajmuje czas wykładniczy.Dlaczego to działa? Aby permutacja była mrówką, przejście od 0 do n-1 musi polegać na przejściu tylko w lewo, a następnie w prawo. Jest tak, ponieważ elementy większe niż pierwszy element muszą zwiększać się od lewej do prawej, a te mniejsze niż to muszą zmniejszać się od lewej do prawej.
Jeśli dublujemy listę, umieszczając odwróconą kopię po jej lewej stronie, ten spacer idzie teraz tylko w prawo.
I odwrotnie, dowolne przesunięcie w prawo od tej listy kopii lustrzanych odpowiada przejściu lewej i prawej strony oryginalnej listy. To prawo jest posortowanym podsekwencją od 0 do n-1. Na liście mrówek ta posortowana podsekwencja jest unikalna, z wyjątkiem arbitralnego wyboru między dwiema sąsiadującymi kopiami oryginalnego pierwszego elementu.
źródło
Haskell, 46 bajtów
Sprawdza, czy różnica wektorów maksymów biegowych i minimów bieżących wynosi [0,1,2,3 ...].
Zgarb zapisał 2 bajty
(%)=scanl1
.źródło
(#)=scanl1
?JavaScript (ES6), 45
Pomyślałem, że jest to zbyt proste, aby wymagać wyjaśnienia, ale jest pewna sztuczka, i na wszelki wypadek, oto moja pierwsza wersja, przed golfem
Uwaga:
a
zamiast tego użyto kodu golfowegok
, ponieważ nie potrzebuję odwoływać się do oryginalnej tablicy wewnątrzevery
wywołania. Unikam więc zanieczyszczania globalnej przestrzeni nazw przy ponownym użyciu parametruTest
źródło
f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
Python 2, 49 bajtów
Sprawdza, czy każdy prefiks listy zawiera wszystkie liczby od jego min. Do maks. Włącznie. Czyni to, sprawdzając, czy różnica wartości maksymalnej i minimalnej jest mniejsza niż jego długość.
54 bajty:
Sprawdza, czy ostatni element jest albo o jeden mniej niż min pozostałych elementów, albo o jeden więcej niż ich maksimum. Następnie usuwa ostatni element i powtarza się. Na liście z jednym elementem wyświetla True.
Można to również sprawdzić poprzez zabawne, ale dłuższe zrozumienie listy.
Chciałbym skorzystać z nierówności
min(l)-2<l.pop()<max(l)+2
, alepop
najpierw muszą się zdarzyć. Korzystanie z programu do wyświetlania za pomocą kodu błędu prawdopodobnie byłoby krótsze.źródło
Mathematica, 42 bajty
Używa dopasowania wzorca do próby znalezienia przedrostka,
a
którego maksymalna różnica od następnego elementub
jest większa niż1
(i neguje wynikMatchQ
).źródło
Perl,
393835 bajtówObejmuje +1 dla
-p
Podaj sekwencję na STDIN:
antsy.pl
:źródło
MATL , 11 bajtów
Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
To oblicza macierz wszystkich bezwzględnych różnic par i zachowuje górną trójkątną część. Wynik jest prawdziwy, jeśli we wszystkich kolumnach oprócz pierwszej jest co najmniej 1 wartość.
źródło
R,
726460 bajtówPermutacja jest niespokojna wtedy i tylko wtedy, gdy wszystkie jej lewe podermutacje są ciągłe (tj. Mają różnicę jeden po sortowaniu).
Jeśli gwarantowane jest, że dane wejściowe mają długość większą niż jeden, możemy zastąpić1:sum(1|v)
jeseq(v)
, co pozwala zaoszczędzić cztery bajty.seq(v)
W jeśli zachowuje się inaczej, kiedy stan wejścia ma długość jednego --- generuje sekwencję1:v
zamiastseq_along(v)
. Jednak na szczęście okazuje się, żeTRUE
w tym przypadku jest to pożądane zachowanie. To samo dzieje się również w przypadku danych wejściowych o zerowej długości.W R
T
jest wstępnie ustawioną zmienną równąTRUE
(ale R pozwala ją przedefiniować).TRUE
jest również uważany za równy1
.Podziękowania dla @Billywob za kilka pomocnych ulepszeń oryginalnego rozwiązania.
źródło
scan
zaoszczędzi ci dwa bajty. W takim przypadku jest to dokładnie ta sama liczba bajtów, co wfor
podejściu pętlowym:v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1)
co byłoby o 2 bajty krótsze niż wektoryzowane podejście.T
. Będzie edytować.05AB1E , 7 bajtów
Wypróbuj online! lub jako zmodyfikowany zestaw testów .
Wyjaśnienie
Wykorzystuje proces opisany przez Xnora w swojej genialnej odpowiedzi na pytanie Pyth .
Zwraca 2 za prawdziwe przypadki i 0 za fałsz.
źródło
Perl, 63 bajty
Zauważ, że @Gabriel Banamy wymyślił krótszą (55 bajtów) odpowiedź . Ale myślę, że to rozwiązanie jest nadal interesujące, więc publikuję je.
Liczba bajtów obejmuje 62 bajty kodu i
-n
flagi.Aby uruchomić:
Krótkie wyjaśnienia : konwertuje każdą liczbę
k
na jednoargumentową reprezentacjęk+1
(+1
jest to konieczne, aby0
s nie zostały zignorowane). Następnie dla każdej liczbyk+1
(wyrażonej jako unary as1(1*)
) sprawdzamy, czy w poprzedzającym ciągu znaków (do których odwołuje się ) występuje albok
($1
wstrzymujek
), albok+2
(co jest wtedy ). Jeśli nie, ustawiamy zero. Na końcu drukujemy, co będzie, jeśli nigdy nie ustawimy go na zero lub zero w przeciwnym razie.11$1
$-backtick
$.
$.
1
źródło
Brain-Flak
302 264256 bajtówPodziękowania dla Kreatora pszenicy za oszczędność 46 bajtów
Na górze stosu będzie 1 dla prawdy i 0 dla fałszu.
Prawda: wypróbuj online!
Falsy: Wypróbuj online!
Chodzi o to, aby utrzymać minimalną i maksymalną liczbę, którą mrówka odwiedził na stosie. Następnie porównaj każdą liczbę z obydwoma i zaktualizuj odpowiedni. Jeśli następna liczba nie jest o 1 mniejsza niż min lub o 1 większa od maksimum, wyjdź z pętli i zwróć false.
Krótkie wyjaśnienie:
źródło
([]){({}[()]<({}<>)<>>)}{}
z([]){{}({}<>)<>([])}{}
zaoszczędzić kilka bajtów więcejGalaretka ,
987 bajtówWypróbuj online!
Tłumaczenie galaretki odpowiedzi xnora.
Stare rozwiązania:
Wypróbuj online!
Działa bardzo podobnie do mojej odpowiedzi Pyth poniżej:
źródło
»\_«\⁼Ṣ
ale jest znacznie bardziej wydajnaŒBŒPċṢ
i;\Ṣ€IỊȦ
powinien zaoszczędzić jeden bajt w każdym podejściu.UŒBŒPċṢ
co nie zapisuje żadnych bajtów. AleỊ
to jest miłe; Źle odczytałem ten atom, aby wypisać logiczne NIE tego, co faktycznie zrobił.U
(lub@
teraz, kiedy o tym myślę). Jeśli tablica jest mrówką, podobnie jak tablica odwrócona, nie?[2, 1, 3, 0]
jest niespokojny, ale[0, 3, 1, 2]
nie jest.CJam (
2120 bajtów)Zestaw testów online
Sekcja
Wykorzystuje to obserwację xnora w jego odpowiedzi Haskella, że różnica między maksimum i minimum pierwszych
n
elementów powinna wynosićn-1
.Alternatywne podejście (także 20 bajtów)
Zestaw testów online
To sprawdza bezpośrednio, że każdy element po pierwszym jest w odległości 1 od poprzedniego elementu. Ponieważ wejście jest permutacją, a zatem nie powtarza wartości, jest to wystarczający test. Dzięki Martinowi za 1-bajtową oszczędność.
Sekcja
źródło
{_{a+_)f-:z1&,*}*^!}
Java,
100987975 bajtówDawniej:
Zapisane 3 bajty przez zastąpienie
true
ifalse
z1>0
i0>1
.Oszczędność 23 bajtów dzięki doskonałym sugestiom Petera Taylora!
Nie golfowany:
Śledzić najwyższych i najniższych wartości postrzegane dotychczas jako
m
an
; tylko zaakceptować nową wartość, jeśli jest tom + 1
czyn - 1
to znaczy wyższej lub niższej wartości; zainicjuj wysoką wartość,m
do wartości mniejszej niż pierwszy element, aby „dopasować” się za pierwszym razem w pętli. Uwaga: jest to algorytm online czasu liniowego. Wymaga tylko trzech słów pamięci, dla bieżących, najwyższych jak dotąd i najniższych jak dotąd wartości, w przeciwieństwie do wielu innych rozwiązań.Jeśli następna wartość nie trafi zarówno w górną, jak i dolną część zakresu, najniższa jak dotąd wartość jest ustawiona na,
-1
a wtedy dolna granica nigdy nie może przejść do zera. Następnie wykrywamy sekwencję mrówek, sprawdzając, czy niska wartośćn
osiągnęła zero.(Niestety jest to mniej wydajne, ponieważ zawsze musimy spojrzeć na całą sekwencję, zamiast ratować się po pierwszym złym numerze, ale ciężko jest się kłócić z 23-bajtowymi oszczędnościami (!), Gdy inne rozwiązania używają O (n ^ 2 ) i zbliża się czas wykładniczy.)
Stosowanie:
Uwaga: można to również napisać bez korzystania z bibliotek lambda Java 8:
Java 7, 89 bajtów
źródło
int m,n;m=n=a[0];--m;
może byćint n=a[0],m=n-1;
kosztownereturn
ielse
można go zmniejszyći==m+1?m++:n=(i==n-1)?i:-1;return n==0;
(lub coś podobnego - nie testowałem tego).m++
im+=1
tam, więc nadal potrzebujęif
ielse
, i traci aspekt zwarcia przy pierwszej złej wartości, ale to duża poprawa. Dziękuję Ci!j
i przypisać do niej wynik, ale podejrzewam, że byłby to lepszy sposób.g
, ale nie udało mi się uruchomić. (Używam Java 9-ea + 138, może to różnica między Javą 8 a Javą 9?) Mogę spróbować ponownie jutro.n-=i==m+1?m-m++:i==n-1?1:n+1;
Pyth ( widelec ), 13 bajtów
Nie. Spróbuj w Internecie link do tego rozwidlenia Pyth. Widelec zawiera funkcję
.+
deltas, która nie jest częścią standardowej biblioteki Pyth.Wyjaśnienie:
źródło
Perl,
6654 +1 = 55 bajtów+1 bajt dla
-n
.Wyjaśnienie:
Drukuje 0, jeśli fałsz, 1, jeśli prawda.
-11 bajtów dzięki @Dada
źródło
perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.'
:-n
zamiast tego<>=~
pozwala pozbyć się/r
modyfikatora. użyj,\d+
a następnie$&
zamiast(\d+)
i$1
.!@a
zamiast0>$#a
.$.&=
zamiast$.&&=
.push@a,$&
zamiast@a=(@a,$&)
Brainfuck, 60 bajtów
Permutacja jest podawana w bajtach bez separatorów i bez kończącej nowej linii. Ponieważ
\x00
występuje w danych wejściowych, jest to przeznaczone do implementacji zEOF = -1
. Dane wyjściowe są\x00
dla false i\x01
true.W przypadku permutacją
\x01
do góry dochr(r)
pozostawia się, po czym można wymienić wszystkie przypadki,+
z,
na wynik 57 zEOF = 0
realizacji.Wypróbuj online (wersja 57-bajtowa): Dane wejściowe można podać jako permutację dowolnego ciągłego zakresu bajtów z wyłączeniem
\x00
, a dane wyjściowe będą w\x00
przypadku fałszu, a minimalna wartość w zakresie true.Śledzimy do tej pory min i max i dla każdej postaci po pierwszej sprawdzamy, czy jest to min-1, max + 1, czy żadna. W przypadku żadnego z nich przenieś wskaźnik poza normalną przestrzeń roboczą, aby komórki lokalne stały się zerowe.
Układ pamięci normalnej przestrzeni roboczej na początku głównej pętli to
c a b 0 0
gdzie
c
jest obecny znak,a
jest min ib
jest max. (W przypadku wersji 60-bajtowej wszystko jest obsługiwane z przesunięciem 1 z powodu,+
.)źródło
Brachylog , 22 bajty
Wypróbuj online!
Wyjaśnienie
Nie znalazłem zwięzłego sposobu sprawdzenia, czy lista zawiera kolejne liczby całkowite, czy nie. Najkrótsze, jakie znalazłem, to wygenerowanie zakresu między pierwszym a ostatnim elementem tej listy i sprawdzenie, czy ten zakres jest oryginalną listą.
źródło
1
. Nie wiem, jak łatwo jest w Brachylog.Partia, 133 bajty
Pobiera dane wejściowe jako argumenty wiersza polecenia. Wychodzi z poziomem błędu 0 dla sukcesu, 1 dla niepowodzenia.
źródło
J, 14 bajtów
Jest to oparte na metodzie @ xnor .
Wyjaśnienie
źródło
Java, 170 bajtów
Tablica
x
ma wartości od 0 do maksymalnej liczby w kolejności (Python byłby tutaj znacznie lepszy ...). Pętla cofa się, próbując dopasować najniższy (x[b]
) lub najwyższy (x[e]
) numer jeszcze nie napotkany; jeśli tak, liczba ta może zostać osiągnięta na tym etapie.Testuj kod tutaj .
źródło
Mathematica, 47 bajtów
Trochę dłużej niż rozwiązanie Martina Endera (niespodzianka niespodzianka!). Ale to jeden z moich bardziej nieczytelnych wysiłków, więc to dobrze: D
Wyjaśnienie:
źródło
Java 7,
170169 bajtówKod niepoznany i testowy:
Wypróbuj tutaj.
Wydajność:
źródło