Faster Burned Pancake Sorting

O algoritmo de Gates que vimos no exercício anterior ordena rapidamente uma pilha de panquecas que não estão queimadas a aumentar o tamanho dos blocos de panquecas já ordenadas. Isto é muito mais rápido que o algoritmo que move em cada passo a panqueca maior para o fundo das panquecas ainda não ordenadas. O algoritmo de Gates ordena uma pilha de n panquecas em menos que (5n + 5)/3 passos no pior caso, enquanto que o algoritmo simplório precisa de no máximo 2n passos. Gates é então cerca de 3 vezes mais rápido no pior caso.

Neste exercício, vamos explorar uma adaptação da mesma ideia das panquecas queimadas. Isto foi publicado primeiramente por David X. Cohen e Manuel Blum. David Cohen co-fundou uns anos depois a série de TV Futurama, cheia de piadas matemáticas. Definitivamente, pessoas interessantes estudaram este singelo problema da panqueca...

O algoritmo de Cohen é um pouco mais fácil que o algoritmo de Gates já que ele distingue menos casos:

Caso 1: pelo menos uma panqueca está de cabeça para cima na pilha. Seja p a maior destas panquecas. Observe que p + 1 deve portanto estar de cabeça para baixo, a menos que p = n (e neste caso não existe a panqueca p + 1).

Caso 2: Todas as panquecas estão de cabeça para baixo. De novo, distinguimos dois sub-casos.

Como pode ver, alcançamos um "join" em duas viradas nos casos 1 ou 2.a. Já que precisamos alcançar n junções para ordenar a pilha, podemos ordenar a pilha em 2n passos se o caso 2.b não ocorrer.

Este caso 2.b necessita um tratamento particular já que é obviamente impossível juntar duas panquecas em apenas duas viradas. Mas por sorte, uma única configuração bem específica da pilha cai neste caso da figura. Podemos então utilizar o algoritmo seguinte, conhecido por tirar vantagem desta configuração. Este algoritmo ordena toda a pilha em exatamente 2n passos.

Repita n vezes
    vire a pilha toda de n panquecas
    Vire as (n-1) panquecas mais de cima

Pode parecer mágica, mas funciona de verdade, como é mostrado no exemplo abaixo.

Portanto, em todo caso, o algoritmo de Cohen trata de ordenar a pilha de panquecas queimadas em 2n passos em todos os casos. Uma vitória sobre o algoritmo simplório para panquecas queimadas que precisa de 3n passos.

Não se preocupe. Este exercício é muito difícil, então tudo bem se não conseguir de primeira. Adicione alguns logs relevantes ao seu código para entender onde parou de funcionar corretamente. Certifique-se de usar o método isSelected() de forma que os seus logs apenas apareçam no mundo que estiver a ser exibido no momento. Em particular, pode ajudar se imprimir textualmente o estado do mundo cada vez que adentrar no loop principal.