Sortowanie naleśników jest potocznym określeniem matematycznego problemu sortowania nieuporządkowanego stosu naleśników w kolejności wielkości, gdy szpachelkę można włożyć w dowolnym punkcie stosu i użyć do odwrócenia wszystkich naleśników nad nim. Liczba naleśników P (n) to minimalna liczba przewrotek wymaganych dla n naleśników. 1

W 1979 roku młody Bill Gates i Christos Papadimitriou napisali artykuł potwierdzający górną granicę P (n) = (5n + 5) / 3 . 2)

Myślę, że można bezpiecznie założyć, że Gates (i / lub Papadimitriou) napisał program do sortowania naleśników przy użyciu opracowanego przez nich algorytmu (być może później niż w 1979 r.). Ponieważ Gates był wykwalifikowanym programistą, prawdopodobnie starali się zagrać w ten kod tak dobrze, jak mogli, ale rozmiar kodu źródłowego nie jest publicznie dostępny (AFAIK).

Wyzwanie:

Utwórz funkcję / program, który wykonuje sortowanie naleśników, w którym maksymalna liczba przewrotek nie przekracza granicy znalezionej przez Gatesa i Papadimitriou. ³ Możesz wybrać, czy lista ma być rosnąca, czy malejąca, o ile jest spójna.

Możesz założyć, że n <50 . Dlatego musisz ograniczyć liczbę przerzutów do (niektóre losowo wybrane wartości n ):

 n   P(n)
38   65
49   83
50   85

Wyjściem powinna być pozycja szpatułki przed każdym przerzuceniem. Dane wyjściowe mogą być zerowe lub z jednym indeksem i możesz wybrać, czy liczyć od góry, czy od dołu.

Dodatkowe zasady:

• Środowisko wykonawcze musi być deterministyczne
• Nie ma ustalonego limitu czasu, ale musisz być w stanie dostarczyć dane wyjściowe dla listy zawierającej 50 elementów

Listy testowe:

Nie mogę podać najtrudniejszych list (jeśli tak, napisałbym artykuł, a nie wyzwanie), więc dostarczę losowe listy liczb, na których można przetestować swoje funkcje / programy. Mogę dodać inne, jeśli okaże się, że te listy są „łatwe”.

9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

Miejmy nadzieję, że Bill Gates i Papadimitriou zobaczą to wyzwanie i podadzą swój kod, abyśmy mogli ustalić, czy rzeczywiście ich pokonałeś.

_{³ Znaleziono lepsze górne granice, ale nie musisz się nimi przejmować.}

Python 2 (PyPy) , 238 235 222 bajtów

a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

* (2 spacje = tab)

Wypróbuj online!

Zaoszczędzono 13 bajtów, pożyczając metodę uszeregowania listy .

DFS z prostą heurystyką, która sprawdza, czy klapka oddziela parę „naleśników”, które przylegałyby do siebie przy sortowaniu. Sortuje w kolejności rosnącej. Wyjście jest indeksowane od 0 od lewej strony, gdzie 0 odwraca pierwsze 2 i tak dalej. Liczba użytych ruchów jest (5/3)*n+1 < 5/3*(n+1)tam, gdzie (18/11)*n < (5/3)*n+1 < 5/3*(n+1)i (18/11)*njest ściślejsza górna granica znaleziona w 2009 roku .