Antsy permutacje

37

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 .

Zgarb
źródło
7
Jest to bardzo interesujące wyzwanie z wieloma różnymi rozwiązaniami: liczę co najmniej 7 unikatowych strategii, które były dotychczas stosowane.
ETHproductions
1
Zorganizowana forma wprowadzania permutacji ma duży wpływ na różnorodność podejść. Warunek bycia mrówką można wyrazić na różne sposoby, które są nierówne na listach ogólnych.
xnor
1
Jestem rozczarowany, że nie ma jeszcze rozwiązania ANTSI C.
NoSeatbelts

Odpowiedzi:

18

Pyth, 7 bajtów

/y+_QQS

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.

/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

Innymi słowy,

lambda l: subseq(sorted(l), concat(reverse(l), l))

gdzie subseqwypisuje, czy elementy pierwszej listy pojawiają się w kolejności na drugiej liście, niekoniecznie obok siebie. subseqOdbywa 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.

[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1      
 2  ^        
    3     ^
          4

Jeśli dublujemy listę, umieszczając odwróconą kopię po jej lewej stronie, ten spacer idzie teraz tylko w prawo.

[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |             
 0     ^      |             
       1      | ^           
              | 2  ^        
              |    3     ^  
              |          4                                  

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.

xnor
źródło
7
Możesz go zmniejszyć do 6 bajtów, używając ... tylko żartu.
jwg
2
Jest coś ohydnego w stosowaniu wykładniczego podejścia do problemu z oczywistym rozwiązaniem w czasie liniowym, nawet jeśli ładnie gra w golfa.
David Conrad
@ jwg Tak naprawdę uwierzę. Jeśli liczba list wziąłaby argumenty w odwrotnej kolejności, można uzyskać 6 bajtów, przyjmując dwa dane wejściowe bez pośrednictwa.
xnor
ayyyyy, przechodząc do strony pyta: D
Maltysen
11

Haskell, 46 bajtów

(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Sprawdza, czy różnica wektorów maksymów biegowych i minimów bieżących wynosi [0,1,2,3 ...].

l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]  
difference =    [0, 1, 2, 3, 4]

Zgarb zapisał 2 bajty (%)=scanl1.

xnor
źródło
To takie sprytne! +1
Gabriel Benamy
1
Czy możesz zapisać niektóre bajty, definiując (#)=scanl1?
Zgarb
1
@Zgarb Dzięki, zapomniałem, że możesz to zrobić.
xnor
9

JavaScript (ES6), 45

a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

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

a => {
  k = []; // I'll put a 1 in this array at position of each value 
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Uwaga: azamiast tego użyto kodu golfowego k, ponieważ nie potrzebuję odwoływać się do oryginalnej tablicy wewnątrz everywywołania. Unikam więc zanieczyszczania globalnej przestrzeni nazw przy ponownym użyciu parametru

Test

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[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`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g), 
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

edc65
źródło
Naprawdę ładne. Próbowałem tego podejścia z rekurencją, ale nie mogę uzyskać go poniżej 65:f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
ETHproductions
Jak to działa? Czy używasz magicznej listy do modyfikowania?
Zgarb
@Zgarb wyjaśnienie dodał
edc65
6

Python 2, 49 bajtów

f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

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:

f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

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.

lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

Chciałbym skorzystać z nierówności min(l)-2<l.pop()<max(l)+2, ale popnajpierw muszą się zdarzyć. Korzystanie z programu do wyświetlania za pomocą kodu błędu prawdopodobnie byłoby krótsze.

xnor
źródło
6

Mathematica, 42 bajty

!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Używa dopasowania wzorca do próby znalezienia przedrostka, aktórego maksymalna różnica od następnego elementu bjest większa niż 1(i neguje wynik MatchQ).

Martin Ender
źródło
6

Perl, 39 38 35 bajtów

Obejmuje +1 dla -p

Podaj sekwencję na STDIN:

antsy.pl <<< "2 1 3 0"

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++
Ton Hospel
źródło
2
Z trudem próbuję to zrozumieć ... Chcesz trochę wyjaśnić? dzięki :-) (tylko główny pomysł powinien wystarczyć)
Dada,
4

MATL , 11 bajtów

&-|R1=a4L)A

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ść.

&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results
Luis Mendo
źródło
4

R, 72 64 60 bajtów

v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

Permutacja 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)je seq(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:vzamiast seq_along(v). Jednak na szczęście okazuje się, że TRUEw 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 Tjest wstępnie ustawioną zmienną równą TRUE(ale R pozwala ją przedefiniować). TRUEjest również uważany za równy 1.

Podziękowania dla @Billywob za kilka pomocnych ulepszeń oryginalnego rozwiązania.

JDL
źródło
1
Czytanie danych wejściowych scanzaoszczędzi ci dwa bajty. W takim przypadku jest to dokładnie ta sama liczba bajtów, co w forpodejś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.
Billywob
Fajny pomysł i myślę, że mogę go poprawić, nadużywając T. Będzie edytować.
JDL
3

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

s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

Aby uruchomić:

perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Krótkie wyjaśnienia : konwertuje każdą liczbę kna jednoargumentową reprezentację k+1( +1jest to konieczne, aby 0s nie zostały zignorowane). Następnie dla każdej liczby k+1(wyrażonej jako unary as 1(1*)) sprawdzamy, czy w poprzedzającym ciągu znaków (do których odwołuje się ) występuje albo k( $1wstrzymuje k), albo k+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

Dada
źródło
3

Brain-Flak 302 264 256 bajtów

Podzię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:

([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack 
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily 
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack
Riley
źródło
Sprawdziłbym redukcje pop pop. Widzę już kilka miejsc, w których można użyć tej strategii.
Wheat Wizard
@WheatWizard Jestem pewien, że jest ich kilka, po prostu jeszcze nie miałem czasu je opracować. Dzięki za przypomnienie.
Riley
Cieszę się, że przynajmniej ma to dla ciebie sens O_O
Gabriel Benamy
Można również zastąpić wystąpień ([]){({}[()]<({}<>)<>>)}{}z ([]){{}({}<>)<>([])}{}zaoszczędzić kilka bajtów więcej
Pszenica Kreatora
3

Galaretka , 9 8 7 bajtów

;@UŒPċṢ

Wypróbuj online!

Tłumaczenie galaretki odpowiedzi xnora.

Stare rozwiązania:

;\Ṣ€IỊȦ
;\Ṣ€IE€P

Wypróbuj online!

Działa bardzo podobnie do mojej odpowiedzi Pyth poniżej:

;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?
Steven H.
źródło
Konwersja innej metody xnor na galaretkę ma również 7 bajtów, »\_«\⁼Ṣale jest znacznie bardziej wydajna
mile
ŒBŒPċṢi ;\Ṣ€IỊȦpowinien zaoszczędzić jeden bajt w każdym podejściu.
Dennis
Niestety, pierwszy nie działa, ponieważ potrzebowałbym odbicia odwróconego wejścia, 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ł.
Steven H.
Nie jestem pewien, dlaczego miałbyś U(lub @teraz, kiedy o tym myślę). Jeśli tablica jest mrówką, podobnie jak tablica odwrócona, nie?
Dennis
1
Niekoniecznie: [2, 1, 3, 0]jest niespokojny, ale [0, 3, 1, 2]nie jest.
Steven H.,
3

CJam ( 21 20 bajtów)

{:A,{_)A<$2*)@-#},!}

Zestaw testów online

Sekcja

Wykorzystuje to obserwację xnora w jego odpowiedzi Haskella, że ​​różnica między maksimum i minimum pierwszych nelementów powinna wynosić n-1.

{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Alternatywne podejście (także 20 bajtów)

{_{a+_)f-:z1&,*}*^!}

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

{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}
Peter Taylor
źródło
Myślę, że to oszczędza? {_{a+_)f-:z1&,*}*^!}
Martin Ender
@MartinEnder, bardzo miło. Co ciekawe, napisałeś, że podobnie jak ja, zamieściłem zupełnie inne podejście z tą samą liczbą bajtów.
Peter Taylor
3

Java, 100 98 79 75 bajtów

a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Dawniej:

a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

Zapisane 3 bajty przez zastąpienie truei falsez 1>0i 0>1.

Oszczędność 23 bajtów dzięki doskonałym sugestiom Petera Taylora!

Nie golfowany:

a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Śledzić najwyższych i najniższych wartości postrzegane dotychczas jako ma n; tylko zaakceptować nową wartość, jeśli jest to m + 1czy n - 1to znaczy wyższej lub niższej wartości; zainicjuj wysoką wartość, mdo 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, -1a wtedy dolna granica nigdy nie może przejść do zera. Następnie wykrywamy sekwencję mrówek, sprawdzając, czy niska wartość nosią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:

import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Uwaga: można to również napisać bez korzystania z bibliotek lambda Java 8:

Java 7, 89 bajtów

boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}
David Conrad
źródło
Dobra obsługa specjalnego przypadku. int m,n;m=n=a[0];--m;może być int n=a[0],m=n-1;kosztowne returni elsemożna go zmniejszyć i==m+1?m++:n=(i==n-1)?i:-1;return n==0;(lub coś podobnego - nie testowałem tego).
Peter Taylor,
@PeterTaylor Fantastic! Niestety, Java nie dopuszcza żadnych efektów ubocznych, takich jak m++i m+=1tam, więc nadal potrzebuję ifi else, i traci aspekt zwarcia przy pierwszej złej wartości, ale to duża poprawa. Dziękuję Ci!
David Conrad,
Pozwoli to na skutki uboczne w złożonym wyrażeniu. To, co może się nie podobać, to użycie wyrażenia ogólnego jako instrukcji. W najgorszym przypadku musisz utworzyć zmienną fikcyjną ji przypisać do niej wynik, ale podejrzewam, że byłby to lepszy sposób.
Peter Taylor
@PeterTaylor Cóż, wypróbowałem kilka jego odmian, w tym przypisując je do zmiennej fikcyjnej 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.
David Conrad,
Rozumiem. n-=i==m+1?m-m++:i==n-1?1:n+1;
Peter Taylor,
2

Pyth ( widelec ), 13 bajtów

!sstMM.+MSM._

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:

           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.
Steven H.
źródło
3
Widząc to przekonuje mnie do połączenia tego w Pyth.
isaacg
2

Perl, 66 54 +1 = 55 bajtów

+1 bajt dla -n.

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Wyjaśnienie:

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Drukuje 0, jeśli fałsz, 1, jeśli prawda.

-11 bajtów dzięki @Dada

Gabriel Benamy
źródło
1
Ten jest naprawdę fajny. Możesz zagrać w golfa do 55 bajtów perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.': -nzamiast tego <>=~pozwala pozbyć się /rmodyfikatora. użyj, \d+a następnie $&zamiast (\d+)i $1. !@azamiast 0>$#a. $.&=zamiast $.&&=. push@a,$&zamiast@a=(@a,$&)
Dada
Z jakiegoś powodu mój system powiedział mi, że nowy plik ma 55 bajtów, co jest oczywiście błędne, ponieważ ma tylko 54 znaki, więc ???
Gabriel Benamy
Hmm, to dziwne. (i nie mam pojęcia, skąd to pochodzi). Ale jestem prawie pewien, że to tylko 54 (skrypt PPCG-Design mówi mi 54, a moja aplikacja bytecount również 54).
Dada
2
Czy to możliwe, że liczba bajtów została wyłączona z powodu niepotrzebnego nowego wiersza na końcu pliku?
trichoplax
2

Brainfuck, 60 bajtów

,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

Permutacja jest podawana w bajtach bez separatorów i bez kończącej nowej linii. Ponieważ \x00występuje w danych wejściowych, jest to przeznaczone do implementacji z EOF = -1. Dane wyjściowe są \x00dla false i \x01true.

W przypadku permutacją \x01do góry do chr(r)pozostawia się, po czym można wymienić wszystkie przypadki ,+z ,na wynik 57 z EOF = 0realizacji.

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 \x00przypadku 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 cjest obecny znak, ajest min i bjest max. (W przypadku wersji 60-bajtowej wszystko jest obsługiwane z przesunięciem 1 z powodu ,+.)

Mitch Schwartz
źródło
1

Brachylog , 22 bajty

:@[fb:{oLtT,Lh:T:efL}a

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

:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L
Fatalizować
źródło
Zakres od pierwszego do ostatniego to jedno podejście, które przyszło mi do głowy w CJam. Drugi to sort, różnice par, sprawdź, czy wszystkie 1. Nie wiem, jak łatwo jest w Brachylog.
Peter Taylor
@PeterTaylor Niestety nie ma krótkiej metody generowania kolejnych par (lub bezpośredniego obliczania różnic par) niestety (na razie).
Fatalize
1

Partia, 133 bajty

@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

Pobiera dane wejściowe jako argumenty wiersza polecenia. Wychodzi z poziomem błędu 0 dla sukcesu, 1 dla niepowodzenia.

Neil
źródło
1

J, 14 bajtów

/:~-:>./\-<./\

Jest to oparte na metodzie @ xnor .

Wyjaśnienie

/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted
mile
źródło
1

Java, 170 bajtów

boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Tablica xma 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 .

AlexRacer
źródło
0

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

#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Wyjaśnienie:

#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list
Greg Martin
źródło
0

Java 7, 170 169 bajtów

import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Kod niepoznany i testowy:

Wypróbuj tutaj.

import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 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 }));
    System.out.println(c(new int[]{ 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 }));
    System.out.println(c(new int[]{ 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 }));
  }
}

Wydajność:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true
Kevin Cruijssen
źródło