La clasificación de panqueques es el término coloquial para el problema matemático de clasificar una pila desordenada de panqueques en orden de tamaño cuando se puede insertar una espátula en cualquier punto de la pila y usarla para voltear todos los panqueques por encima de ella. Un número de panqueque P (n) es el número mínimo de volteos necesarios para n panqueques. 1

En 1979, un joven Bill Gates y Christos Papadimitriou escribieron un documento que prueba un límite superior de P (n) = (5n + 5) / 3 . 2

Creo que es seguro asumir que Gates (y / o Papadimitriou) escribieron un programa para realizar la clasificación de panqueques usando el algoritmo que desarrollaron (posiblemente más tarde de 1979). Como Gates era un programador experto, probablemente intentaron jugar este código lo mejor que pudieron, pero el tamaño del código fuente no está disponible públicamente (AFAIK).

Desafío:

Cree una función / programa que realice la clasificación de panqueques, donde el número máximo de volteos no exceda el límite encontrado por Gates y Papadimitriou. ³ Puede elegir si desea que la lista suba o baje, siempre que sea coherente.

Puede suponer que n <50 . Por lo tanto, debe limitar el número de volteos a (algunos valores n seleccionados al azar ):

 n   P(n)
38   65
49   83
50   85

La salida debe ser la posición de la espátula antes de cada volteo. La salida puede ser cero o un índice, y puede elegir si cuenta desde arriba o abajo.

Reglas adicionales:

• El tiempo de ejecución debe ser determinista.
• No hay un límite de tiempo fijo, pero debe poder proporcionar la salida para una lista con 50 elementos

Listas de prueba:

No puedo proporcionar las listas más difíciles (de ser así, escribiría un artículo, no un desafío), así que proporcionaré algunas listas aleatorias de números en los que puede probar sus funciones / programas. Podría agregar otros si resulta que estas listas son "fáciles".

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

Con suerte, Bill Gates y Papadimitriou verán este desafío y proporcionarán su código, para que podamos determinar si realmente los superó.

_{³ Se han encontrado mejores límites superiores, pero no necesita preocuparse por ellos.}

Python 2 (PyPy) , 238 235 222 bytes

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 espacios = pestaña)

Pruébalo en línea!

Se guardaron 13 bytes tomando prestado un método para clasificar una lista .

DFS con una heurística simple que verifica si un flip separa un par de "panqueques" que serían adyacentes cuando se clasifican. Lo ordena en orden ascendente. La salida está indexada en 0 desde la izquierda, donde 0 voltea los primeros 2 y así sucesivamente. El número de movimientos utilizados es (5/3)*n+1 < 5/3*(n+1)dónde (18/11)*n < (5/3)*n+1 < 5/3*(n+1)y (18/11)*nes un límite superior más estricto que se encontró en 2009 .