Przerzucanie naleśników

27

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 3można posortować, najpierw odwracając pierwsze 6elementy (całą sekwencję), uzyskując wynik pośredni 3 2 1 4 5 6, a następnie odwracając pierwsze 3elementy, 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 1moż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
daniero
źródło
1
Jakaś poprawna sekwencja, czy powinna to być minimalna długość?
Peter Taylor,
Mała literówka: drugi przykład pokazuje 4 3 2 1zamiast4 2 3 1
beary605
4
(Mój internet się zepsuł, gdy próbowałem to edytować, więc opublikowałem to ponownie) @PeterTaylor Kusiło mnie, aby włączyć do tego jakąś optymalizację, ale postanowiłem tego nie robić. Znalezienie długości minimalnej sekwencji jest w rzeczywistości trudne dla NP , podczas gdy najprostszy, prosty algorytm może znaleźć rozwiązanie, które najwyżej będzie miało długość 2n. I naprawdę nie wiem, jak bym oceniać to jako kod prowokacji / optymalnej rzecz wyjścia, a ja po prostu jak zwykły codegolf więcej :)
daniero
Zastanawiam się, czy ktoś opublikuje swój wpis z tego wyzwania .
grc
Czy sekwencja musi mieć ciągłe wartości? Czy 2 7 5 jest prawidłowym wejściem?

Odpowiedzi:

6

GolfScript, 34/21 znaków

(Dzięki @PeterTaylor za odcięcie 4 znaków)

~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

Test online

Krótsza, 21-znakowa wersja działa tylko z listami zawierającymi unikalne elementy

~].${.2$?.p)p.@\-+}/,

Test online

Obie wersje dają nieoptymalne rozwiązania.


Objaśnienie krótszego rozwiązania:

~]         # read input from stdin
.$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
  .2$?     # grab the index of the element
  .p       # print the index
  )p       # increment and print the index
  .@\-+    # move the element to the front
}/
,          # leave the length of the list on the stack
           # this flips the reverse sorted list to become sorted

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:

1 2 3 4 5 6 7   # let's move the 3rd (0-based) element to the front
# flip the first 3 elements
3 2 1 4 5 6 7
# flip the first 3+1 elements
4 1 2 3 5 6 7

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):

d=map(int,raw_input().split());i=0
while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1
Zmienność
źródło
2
Widzę, że nie spotkałeś się z jednym z przydatnych dziwactw GolfScript: możesz użyć dowolnego tokena jako zmiennej. Nie używasz &nigdzie, więc powinieneś być w stanie zastąpić spodczas &i usuń spacje.
Peter Taylor
@PeterTaylor huh, zastanawiałem się, dlaczego możesz użyć go ^jako zmiennej w wyzwaniu fibonacci;) Dzięki za wskazówkę!
Zmienność
Do wprowadzenia 3 2 1dostaję, 131211co nie jest poprawne.
Howard,
@Howard sprawił, że teraz działa
zmienność
@ Lotność Ostatnia zmiana była trochę za duża ;-) Np. Takich list 2 1 1nie można już posortować.
Howard
11

Python, 91 90 znaków

L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

Odwróć 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.

ito indeks największego naleśnika. L=L[:i:-1]+L[:i]przewraca i+1naleśniki, przewraca len(L)naleśniki, a następnie upuszcza ostatni naleśnik.

Keith Randall
źródło
1
Myślałem, że wolno ci robić klapki. (To znaczy, nie sądziłem, że możesz upuścić naleśniki ze stosu). Czy źle zrozumiałem zasady? Hmm idzie znowu przeczytać stronę wiki Bez względu na to, dobra robota :) Mniej niż 100 znaków jest dla mnie niesamowita!
WendiKidd
@WendiKidd W rzeczywistości chodzi mu o to, że po przewróceniu największego do dołu po prostu ignoruje go i zajmuje się naleśnikami na nim.
AJMansfield
@AJMansfield Ach, rozumiem! Dzięki, to ma sens. Nie mogę odczytać kodu (jestem zbyt nowy w Pythonie), więc źle zrozumiałem wyjaśnienie :) Dzięki!
WendiKidd
2
Prawie ewolucja tego, co napisałem wcześniej. Nie myślałem o usunięciu elementów, ponieważ na początku musiałem sprawdzić poprawność danych wyjściowych (tj. Czy lista jest posortowana później?). Nawiasem mówiąc: Wierzę usuwania przecinek z printWspanialy renderowanie wyjście nieczytelny (1 bajt zapisany :)
Bakuriu
@WendiKidd, po dokładnej inspekcji rzeczywiście usuwa naleśniki; wystarczy tylko dowiedzieć się, jaka jest sekwencja przewrotek, a nie sortować tablicy.
AJMansfield
6

Ruby 1.9 - 109 88 79 znaków

Znacznie bardziej kompaktowa wersja oparta na świetnym rozwiązaniu Pythona Keitha:

a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

Orginalna wersja:

a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}

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):

a=$*.map &:to_i
a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}

Pobiera nieposortowaną listę jako argumenty wiersza polecenia. Przykładowe użycie:

>pc.rb 4 2 3 1
4
2
3
2
Paul Prestidge
źródło
6

GolfScript, 31 29 znaków

~].${1$?).p.2$.,p>-1%\@<+)}%,

Inne rozwiązanie GolfScript można również przetestować online .

Poprzednia wersja:

~].$-1%{1$?).2$>-1%@2$<+.,\);}/

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.

~]         # Convert STDIN (space separated numbers) to array
.$-1%      # Make a sorted copy (largest to smallest)
{          # Iterate over this copy
  1$?)     # Get index of item (i.e. largest item) in the remaining list,
           # due to ) the index starts with one
  .        # copy (i.e. index stays there for output)
  2$>      # take the rest of the list...
  -1%      # ... and reverse it 
  @2$<     # then take the beginning of the list
  +        # and join both. 
           # Note: these operations do both flips together, i.e.
           # flip the largest item to front and then reverse the complete stack
  .,       # Take the length of the list for output
  \);      # Remove last item from list
}/
Howard
źródło
4

Perl, 103 100 znaków

Oczekuje danych wejściowych w wierszu polecenia.

for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

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

chlebak
źródło
3

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

python script.py 4 2 3 1

(2 spacje = tab)

import sys
t=tuple
i=t(map(int,sys.argv[1:]))
g=t(range(1,len(i)+1))
q=[i]
p={}
l={}
while q:
 c=q.pop(0)
 for m in g:
  n=c[:m][::-1]+c[m:]
  if n==g:
   s=[m]
   while c!=i:s+=[l[c]];c=p[c]
   print s[::-1]
   sys.exit()
  elif n not in p:q+=[n];p[n]=c;l[n]=m
mile
źródło
1
Można wymienić sys.exit()z 1/0(w codegolf nie dbasz o to, co zostanie wydrukowane w stderr ...).
Bakuriu,
Jasne, mógłbym zrobić, print s[::-1];1/0żeby ogolić kilka znaków.
mile
BFS jest bardzo interesujący, ale uruchamianie go za pomocą 4 2 3 1daje 2 3 2 4, co w rzeczywistości jest nieprawidłowe.
daniero
1
@daniero W jaki sposób dane wyjściowe są nieprawidłowe? 4 2 3 1-> 2 4 3 1-> 3 4 2 1-> 4 3 2 1->1 2 3 4
Gareth
@Gareth Nie mam pojęcia! I nawet sprawdziłem to dwa razy ... No cóż, nieważne więc :) Ładne rozwiązanie, mile t.
daniero
3

Python2: 120

L=map(int,raw_input().split())
u=len(L)
while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1

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:

n_1 n_2
n_3 n_4
n_5 n_6
...

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

Bakuriu
źródło
[:i][::-1]-> [i-1::-1], [:u][::-1]-> [u-1::-1], zapisuje 2 znaki
Zmienność
W rzeczywistości L[:i]=L[i-1::-1];L[:u]=[u-1::-1]oszczędza kolejne 3 znaki
Zmienność
@Volatility Dzięki za wskazówki. W zestawie.
Bakuriu,
3

Python - 282 znaków

import sys
s=sys.argv[1]
l=s.split()
p=[]
for c in l:
 p.append(int(c))
m=sys.maxint
n=0
while(n==(len(p)-1)):
 i=x=g=0
 for c in p:
  if c>g and c<m:
   g=c
   x=i
  i+=1
 m=g
 x+=1
 t=p[:x]
 b=p[x:]
 t=t[::-1]
 p=t+b
 a=len(p)-n;
 t=p[:a]
 b=p[a:]
 t=t[::-1]
 p=t+b
 print p
 n+=1

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:

Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

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:

import sys

pancakesStr = sys.argv[1]
pancakesSplit = pancakesStr.split()
pancakesAr = []
for pancake in pancakesSplit:
    pancakesAr.append(int(pancake))

smallestSorted = sys.maxint
numSorts = 0

while(numSorts < (len(pancakesAr) - 1)):
    i = 0
    biggestIndex = 0
    biggest = 0
    for pancake in pancakesAr:
        if ((pancake > biggest) and (pancake < smallestSorted)):
            biggest = pancake
            biggestIndex = i
        i += 1

    smallestSorted = biggest  #you've found the next biggest to sort; save it off.
    biggestIndex += 1   #we want the biggestIndex to be in the top list, so +1.

    top = pancakesAr[:biggestIndex]
    bottom = pancakesAr[biggestIndex:]

    top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1)
    pancakesAr = top + bottom   #reconstruct stack

    alreadySortedIndex = len(pancakesAr) - numSorts;

    top = pancakesAr[:alreadySortedIndex]
    bottom = pancakesAr[alreadySortedIndex:]

    top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2)
    pancakesAr = top + bottom   #reconstruct list

    print pancakesAr    #print after each flip

    numSorts += 1

print "Sort completed in " + str(numSorts) + " flips. Final stack: "
print pancakesAr

Podstawowym algorytmem, który zastosowałem, jest ten wymieniony w artykule wiki, do którego link znajduje się w pytaniu :

Najprostszy algorytm sortowania naleśników wymaga co najwyżej 2n-3 przerzutów. W tym algorytmie, będącym odmianą sortowania selekcyjnego, doprowadzamy największy naleśnik, który nie został jeszcze posortowany na górę za pomocą jednego obrotu, a następnie obniżamy go do jego ostatecznej pozycji o jeszcze jedno, a następnie powtarzamy to dla pozostałych naleśników.

WendiKidd
źródło
1
Kilka wskazówek dotyczących gry w golfa: cztery miejsca na wcięcia są marnotrawstwem. Lepiej: użyj jednego miejsca; jeszcze lepiej: łącz tabulatory i spacje, aby jeszcze bardziej ograniczyć.
John Dvorak,
1
t=p[:x] t=t[::-1](Wcięcie 16 +) można zmniejszyć do t=p[:x][::-1](13), a nawet t=p[x-1::-1](12). Wstaw wszystko, co możesz:p=p[x-1::-1]+p[x:]
John Dvorak,
Użyj ujemnych wskaźników, aby liczyć od tyłu. len(a)-nstaje 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:]
John Dvorak,
1
Umm ... powinieneś wydrukować całą sekwencję przewracania, a nie tylko wynik końcowy.
John Dvorak,
Co powiedział Jan Dvorak. Przy okazji, witaj w codegolf. Możesz łatwo zmniejszyć liczbę znaków do połowy za pomocą kilku prostych środków; niektóre z nich zostały wymienione. Również zmienne pośrednie nie są dobre. Zrozumienie listy jest miłe. Ale jeśli używasz sys.argv, możesz równie dobrze pozwolić, aby każda liczba danych wejściowych była argumentem, a następnie map(int,sys.argv[1:])robi to, co teraz robi 6 pierwszych linii. i=x=g=0działa, ale i tak należy zmniejszyć liczbę zmiennych. Dam ci jedno: jest to wpis w pythonie, którego rozumiem najmniej: D
daniero
3

C # - 264 259 252 237 znaków

Wykorzystuje 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 gotodla 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.

using System.Linq;class P{static void Main(string[]a){var n=a.ToList();for(int p
=n.Count;p>0;p--){int i=n.IndexOf(p+"")+1;if(i<p){f:if(i>1)System.Console.Write
(i);n=n.Take(i).Reverse().Concat(n.Skip(i)).ToList();if(i!=p){i=p;goto f;}}}}}

Nie golfowany:

using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var numbers = args.ToList();

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake+"") + 1;
            if (index < pancake)
            {
                flip:

                if (index > 1)
                    System.Console.Write(index);

                numbers = numbers.Take(index)
                                 .Reverse()
                                 .Concat(numbers.Skip(index))
                                 .ToList();

                if (index != pancake)
                {
                    index = pancake;
                    goto flip;
                }
            }
        }
    }
}

Oto moje wstępne rozwiązanie, bez golfa (264 znaki w golfa):

using System.Linq;
using System;

class Program
{
    static void Main(string[] args)
    {
        var numbers = args.Select(int.Parse).ToList();

        Action<int> Flip = howMany =>
        {
            Console.Write(howMany);
            numbers = numbers.Take(howMany)
                             .Reverse()
                             .Concat(numbers.Skip(howMany))
                             .ToList();
        };

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake) + 1;
            if (index < pancake)
            {
                if (index > 1)
                    Flip(index);
                Flip(pancake);
            }
        }
    }
}
Igby Largeman
źródło
Nie obsługuje ciągłych sekwencji - dając nieprawidłowe wyniki przy tych danych wejściowych.
@hatchet: Nie jestem pewien, co masz na myśli. Czy możesz podać mi przykład?
Igby Largeman
Biorąc pod uwagę wartość 1 22, wynik mówi o zrobieniu jednej zamiany, co dałoby wynik 22 1. Myślę, że twój kod oczekuje, że sekwencja będzie zawierać ciągłe liczby (np. 2 4 1 3), ale nie oczekuje danych wejściowych takich jak ( 2 24 5 5 990).
@hatchet: Rzeczywiście, nie podjąłem próby uzupełnienia luk w sekwencji, ponieważ to nie miałoby sensu. Ideą sortowania naleśników jest sortowanie stosu obiektów, a nie grupy dowolnych liczb. Liczba powiązana z każdym obiektem określa jego właściwe położenie na stosie. Dlatego liczby zawsze zaczynają się od 1 i są ciągłe.
Igby Largeman
Nie byłem pewien, ponieważ pytanie brzmiało „sekwencja”, a w matematyce {1, 22} jest prawidłową sekwencją, ale oba przykłady były ciągłymi liczbami. Poprosiłem więc o wyjaśnienia z PO (patrz komentarze do pytania). Myślę, że większość odpowiedzi tutaj poradzi sobie z lukami.
2

Haskell , 72 71 bajtów

h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

Wypróbuj online! Znajduje maksimum, odwraca je do tyłu i rekurencyjnie sortuje pozostałą listę.

Edycja: -1 bajt dzięki BMO

Laikoni
źródło
2

Perl 5.10 (lub wyższy), 66 bajtów

Obejmuje +3dla -n The, use 5.10.0aby doprowadzić język do poziomu perl 5.10 jest uważany za darmowy

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Uruchom z wejściem jako jedną linię na STDIN:

flop.pl <<< "1 8 3 -5 6"

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. 12Na 21)

Ton Hospel
źródło
1

C # - 229

using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}

wersja czytelna

using System;
using System.Linq;
class P {
    static void Main(string[] a) {
        var n = a.ToList();
        Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
        int c = n.Count;
        foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
            d(n.IndexOf(s) + 1); d(c--);
        }
    }
}

źródło