Classificação de panquecas é o termo coloquial para o problema matemático de classificar uma pilha desordenada de panquecas em ordem de tamanho, quando uma espátula pode ser inserida em qualquer ponto da pilha e usada para virar todas as panquecas acima dela. Um número de panqueca P (n) é o número mínimo de inversões necessárias para n panquecas. 1

Em 1979, um jovem Bill Gates e Christos Papadimitriou escreveram um artigo comprovando um limite superior de P (n) = (5n + 5) / 3 . 2

Eu acho que é seguro assumir que Gates (e / ou Papadimitriou) escreveu um programa para realizar a classificação de panquecas usando o algoritmo que eles desenvolveram (possivelmente depois de 1979). Como Gates era um programador qualificado, eles provavelmente tentaram jogar esse código da melhor maneira possível, mas o tamanho do código-fonte não está disponível ao público (AFAIK).

Desafio:

Crie uma função / programa que execute a classificação de panquecas, em que o número máximo de inversões não exceda o limite encontrado por Gates e Papadimitriou. ³ Você pode escolher se deseja que a lista suba ou desça, desde que seja consistente.

Você pode assumir que n <50 . Portanto, você deve limitar o número de movimentos para (alguns valores n selecionados aleatoriamente ):

 n   P(n)
38   65
49   83
50   85

A saída deve ser a posição da espátula antes de cada inversão. A saída pode ser zero ou indexada um e você pode escolher se conta a partir da parte superior ou inferior.

Regras adicionais:

• O tempo de execução deve ser determinístico
• Não há limite de tempo fixo, mas você deve poder fornecer a saída para uma lista com 50 elementos

Listas de teste:

Não posso fornecer as listas mais difíceis (se sim, escreveria um artigo, não um desafio); portanto, fornecerei algumas listas aleatórias de números nos quais você pode testar suas funções / programas. Eu poderia adicionar outras pessoas se essas listas forem "fáceis".

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

Felizmente, Bill Gates e Papadimitriou verão esse desafio e fornecerão o código deles, para que possamos determinar se você realmente os superou.

_{³ Melhores limites superiores foram encontrados, mas você não precisa se preocupar com eles.}

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 espaços = tabulação)

Experimente online!

Economizou 13 bytes emprestando um método para classificar uma lista .

DFS com uma heurística simples que verifica se um flip separa um par de "panquecas" que seriam adjacentes quando classificadas. Classifica em ordem crescente. A saída é indexada em 0 a partir da esquerda, onde 0 inverte os 2 primeiros e assim por diante. O número de movimentos usados ​​é (5/3)*n+1 < 5/3*(n+1)onde (18/11)*n < (5/3)*n+1 < 5/3*(n+1)e (18/11)*né um limite superior mais apertado encontrado em 2009 .