Le tri des crêpes est le terme familier pour le problème mathématique du tri d'une pile de crêpes désordonnée par ordre de taille lorsqu'une spatule peut être insérée à n'importe quel point de la pile et utilisée pour retourner toutes les crêpes au-dessus. Un nombre de crêpes P (n) est le nombre minimum de flips requis pour n crêpes. 1

En 1979, un jeune Bill Gates et Christos Papadimitriou, ont écrit un article prouvant une limite supérieure de P (n) = (5n + 5) / 3 . 2

Je pense qu'il est prudent de supposer que Gates (et / ou Papadimitriou) a écrit un programme pour effectuer le tri des crêpes en utilisant l'algorithme qu'ils ont développé (peut-être plus tard que 1979). Étant donné que Gates était un programmeur qualifié, ils ont probablement essayé de jouer ce code du mieux qu'ils le pouvaient, mais la taille du code source n'est pas accessible au public (AFAIK).

Défi:

Créez une fonction / programme qui effectue le tri des crêpes, où le nombre maximal de flips ne dépasse pas la limite trouvée par Gates et Papadimitriou. ³ Vous pouvez choisir si vous voulez que la liste monte ou descend, tant qu'elle est cohérente.

Vous pouvez supposer que n <50 . Vous devez donc limiter le nombre de flips à (certaines valeurs n sélectionnées au hasard ):

 n   P(n)
38   65
49   83
50   85

La sortie doit être la position de la spatule avant chaque retournement. La sortie peut être zéro ou un index, et vous pouvez choisir si vous comptez en haut ou en bas.

Règles supplémentaires:

• Le runtime doit être déterministe
• Il n'y a pas de limite de temps fixe, mais vous devez pouvoir fournir la sortie d'une liste de 50 éléments

Listes de tests:

Je ne peux pas fournir les listes les plus dures (si c'est le cas, j'écrirais un article, pas un défi), donc je vais fournir des listes aléatoires de nombres sur lesquels vous pouvez tester vos fonctions / programmes. Je pourrais en ajouter d'autres s'il s'avère que ces listes étaient "faciles".

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

Espérons que Bill Gates et Papadimitriou verront ce défi et fourniront leur code, afin que nous puissions déterminer si vous les avez en fait devancés.

_{³ De meilleures limites supérieures ont été trouvées, mais vous n'avez pas besoin de vous en préoccuper.}

Python 2 (PyPy) , 238 235 222 octets

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 espaces = tabulation)

Essayez-le en ligne!

Enregistrement de 13 octets en empruntant une méthode de classement d'une liste .

DFS avec une heuristique simple qui vérifie si un flip sépare une paire de "crêpes" qui seraient adjacentes lors du tri. Trie par ordre croissant. La sortie est indexée 0 à partir de la gauche où 0 retourne les 2 premiers et ainsi de suite. Le nombre de mouvements utilisés est (5/3)*n+1 < 5/3*(n+1)où (18/11)*n < (5/3)*n+1 < 5/3*(n+1)et (18/11)*nest une limite supérieure plus stricte trouvée en 2009 .