W sortowaniu naleśników jedyną dozwoloną operacją jest odwrócenie elementów jakiegoś prefiksu sekwencji. Albo pomyśl o stosie naleśników: wsuwamy gdzieś w stos szpatułkę i przewracamy wszystkie naleśniki nad szpachelką.
Na przykład sekwencję 6 5 4 1 2 3
można posortować, najpierw odwracając pierwsze 6
elementy (całą sekwencję), uzyskując wynik pośredni 3 2 1 4 5 6
, a następnie odwracając pierwsze 3
elementy, dochodząc do 1 2 3 4 5 6
.
Ponieważ jest tylko jedna operacja, cały proces sortowania można opisać za pomocą sekwencji liczb całkowitych, gdzie każda liczba całkowita jest liczbą elementów / naleśników, które należy uwzględnić w odwróceniu. W powyższym przykładzie sekwencja sortowania będzie 6 3
.
Kolejny przykład: 4 2 3 1
można sortować za pomocą 4 2 3 2
. Oto wyniki pośrednie:
4 2 3 1
flip 4: 1 3 2 4
flip 2: 3 1 2 4
flip 3: 2 1 3 4
flip 2: 1 2 3 4
Zadanie:
Napisz program, który pobiera listę liczb całkowitych i drukuje prawidłową sekwencję sortowania naleśników.
Lista do sortowania może być listą oddzieloną spacjami od standardowego wejścia lub argumentami wiersza poleceń. Wydrukuj listę, jednak jest to wygodne, o ile jest w pewnym stopniu czytelne.
To jest codegolf!
Edytować:
Jak powiedziałem w komentarzach, nie musisz optymalizować wyjścia (znalezienie najkrótszej sekwencji jest trudne NP ). Jednak właśnie zdałem sobie sprawę, że tanim rozwiązaniem byłoby wyrzucanie liczb losowych, dopóki nie uzyskasz pożądanego rezultatu ([nowego?] Typu bogosortu). Żadna z dotychczasowych odpowiedzi tego nie uczyniła, więc teraz deklaruję, że twój algorytm nie powinien polegać na żadnej (pseudo) losowości .
Podczas gdy wszyscy się kopacie, oto wariant bogopancakesort w Ruby 2.0 (60 znaków), aby go wcierać:
a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort
4 3 2 1
zamiast4 2 3 1
Odpowiedzi:
GolfScript, 34/21 znaków
(Dzięki @PeterTaylor za odcięcie 4 znaków)
Test online
Krótsza, 21-znakowa wersja działa tylko z listami zawierającymi unikalne elementy
Test online
Obie wersje dają nieoptymalne rozwiązania.
Objaśnienie krótszego rozwiązania:
Używa innego algorytmu niż większość innych opublikowanych. Zasadniczo chwyta najmniejszy element listy, a dwoma rzutami przesuwa go do przodu, zachowując kolejność pozostałych elementów.
Aby przesunąć n-ty element na przód:
Powtarza tę operację dla każdego elementu w kolejności i kończy się sortowaniem w odwrotnej kolejności. Następnie odwraca całą listę, aby pozostawić ją w pełni posortowaną.
W rzeczywistości algorytm jest odmianą 90-znakowego rozwiązania Pythona (oczywiście moje własne):
źródło
&
nigdzie, więc powinieneś być w stanie zastąpićs
podczas&
i usuń spacje.^
jako zmiennej w wyzwaniu fibonacci;) Dzięki za wskazówkę!3 2 1
dostaję,131211
co nie jest poprawne.2 1 1
nie można już posortować.Python,
9190 znakówOdwróć największy naleśnik na górę, a następnie odwróć cały stos. Usuń największy naleśnik z dołu i powtórz.
i
to indeks największego naleśnika.L=L[:i:-1]+L[:i]
przewracai+1
naleśniki, przewracalen(L)
naleśniki, a następnie upuszcza ostatni naleśnik.źródło
print
Wspanialy renderowanie wyjście nieczytelny (1 bajt zapisany :)Ruby 1.9 -
1098879 znakówZnacznie bardziej kompaktowa wersja oparta na świetnym rozwiązaniu Pythona Keitha:
Orginalna wersja:
Jeśli nie przejmujesz się fałszywymi operacjami (odwracanie stosów wielkości 1 lub odwracanie tego samego stosu dwa razy z rzędu), możesz go nieco skrócić (96 znaków):
Pobiera nieposortowaną listę jako argumenty wiersza polecenia. Przykładowe użycie:
źródło
GolfScript,
3129 znakówInne rozwiązanie GolfScript można również przetestować online .
Poprzednia wersja:
Jak to działa: przewraca największy element na górę, a następnie na ostatnie miejsce na liście. Ponieważ znajduje się teraz we właściwej pozycji, możemy go usunąć z listy.
źródło
Perl,
103100 znakówOczekuje danych wejściowych w wierszu polecenia.
Rozwiązania, które drukuje, są zdecydowanie nieoptymalne. (Miałem program z dużo ładniejszym wyjściem około 24 znaków temu ....)
Logika jest dość interesująca. Zaczyna się od skatalogowania indeksu każdego elementu, gdyby był on posortowany. Następnie przechodzi przez ten katalog od prawej do lewej. Zatem zastosowanie przerzucenia polega na dostosowaniu indeksów poniżej wartości odcięcia, zamiast faktycznego przenoszenia wartości. Po kilku finaglingach udało mi się również uratować kilka postaci, wykonując jednocześnie oba obroty na iterację.
źródło
Python 2 (254)
Proste wyszukiwanie BFS, niektóre elementy są wbudowane, prawdopodobnie można by je bardziej skompresować bez zmiany stylu wyszukiwania. Mam nadzieję, że to pokazuje, jak trochę zacząć grać w golfa (zbyt wiele, by być w prostym komentarzu).
Posługiwać się:
(2 spacje = tab)
źródło
sys.exit()
z1/0
(w codegolf nie dbasz o to, co zostanie wydrukowane w stderr ...).print s[::-1];1/0
żeby ogolić kilka znaków.4 2 3 1
daje2 3 2 4
, co w rzeczywistości jest nieprawidłowe.4 2 3 1
->2 4 3 1
->3 4 2 1
->4 3 2 1
->1 2 3 4
Python2: 120
To nie jest wydajne: nie znajdzie najlepszej sekwencji sortowania, a podana sekwencja może nawet zawierać brak operacji (tj. Odwracanie tylko pierwszego elementu), niemniej jednak wynik jest prawidłowy.
Dane wyjściowe są podane w postaci:
Które powinny być odczytywane jako sekwencji koziołki:
n_1 n_2 n_3 n_4 n_5 n_6 ...
. Jeśli chcesz uzyskać dane wyjściowe takie jak:n_1 n_2 n_3 n_4 n_5 n_6 ...
Po prostu dodaj przecinek do
print
wyciągu.źródło
[:i][::-1]
->[i-1::-1]
,[:u][::-1]
->[u-1::-1]
, zapisuje 2 znakiL[:i]=L[i-1::-1];L[:u]=[u-1::-1]
oszczędza kolejne 3 znakiPython - 282 znaków
Mój pierwszy golf golfowy; Nie mam złudzeń, że wygram , ale dobrze się bawiłem. Nadawanie wszystkim nazwom jednoznakowym sprawia, że lęk jest przerażający, powiem ci! Jest to uruchamiane z wiersza poleceń, przykładowa implementacja poniżej:
Nie ma nic szczególnego ani pomysłowego w sposobie, w jaki to zrobiłem, ale FAQ sugeruje opublikowanie wersji bez golfa dla zainteresowanych czytelników, więc zrobiłem to poniżej:
Podstawowym algorytmem, który zastosowałem, jest ten wymieniony w artykule wiki, do którego link znajduje się w pytaniu :
źródło
t=p[:x]
t=t[::-1]
(Wcięcie 16 +) można zmniejszyć dot=p[:x][::-1]
(13), a nawett=p[x-1::-1]
(12). Wstaw wszystko, co możesz:p=p[x-1::-1]+p[x:]
len(a)-n
staje się-n
;p=p[-n-1::-1]+p[-n:]
. Dalsza gra w golfa przy użyciu właściwych operacji:p=p[~n::-1]+p[-n:]
map(int,sys.argv[1:])
robi to, co teraz robi 6 pierwszych linii.i=x=g=0
działa, ale i tak należy zmniejszyć liczbę zmiennych. Dam ci jedno: jest to wpis w pythonie, którego rozumiem najmniej: DC # -
264 259 252237 znakówWykorzystuje najprostszy algorytm i zapewnia poprawne wyjście bez zbędnych przerzutów. Mógłbym zgolić 7 znaków, jeśli pozwolę, aby zawierały 1 (non-flips) na wyjściu, ale to brzydkie.
I uciekają się do stosowania
goto
dla maksymalnej golfage. Zapisano także niektóre znaki, pozwalając mu wykonywać non-flipy (ale nie drukować ich).Ostatnie ulepszenie: utrzymywanie tablicy wejściowej jako ciągów zamiast konwersji na ints.
Nie golfowany:
Oto moje wstępne rozwiązanie, bez golfa (264 znaki w golfa):
źródło
Haskell ,
7271 bajtówWypróbuj online! Znajduje maksimum, odwraca je do tyłu i rekurencyjnie sortuje pozostałą listę.
Edycja: -1 bajt dzięki BMO
źródło
Perl 5.10 (lub wyższy), 66 bajtów
Obejmuje
+3
dla-n
The,use 5.10.0
aby doprowadzić język do poziomu perl 5.10 jest uważany za darmowyUruchom z wejściem jako jedną linię na STDIN:
Sortuje listę, wielokrotnie znajdując inwersję, przewracając ją do przodu, a następnie odwracając i przewracając wszystko z powrotem do swojej poprzedniej pozycji. Jest to równoważne z zamianą inwersji, więc nie muszę cofać (co jest niewygodne w przypadku łańcuchów, ponieważ odwróciłoby cyfry wartości konwertowanych np.
12
Na21
)źródło
C # - 229
wersja czytelna
źródło