Problema de troca de trem estendido

Parte 1: Problema de Troca Normal de Trem

No CCC de 1996 (Canadian Computing Competition), o primeiro problema do Estágio 2 foi um Problema de Troca de Trem. Você pode visitar o link aqui . Essencialmente, você tem vários trens numerados e deseja descobrir quantas trocas de trem você precisa para ordená-las, e cada operação de troca de trem permite que você troque dois trens adjacentes. Como os vagões podem funcionar de qualquer maneira, ninguém se importa com o fato de os vagões ficarem do outro lado quando trocados. Isso é bem fácil; tudo o que você precisa fazer é:

Encontre o número de etapas para classificá-lo com bolhas; é o algoritmo de classificação mais eficiente quando você só pode fazer trocas de elementos adjacentes

Então, eu fiz um mais difícil.

Parte 2: Como esse desafio funciona

Agora você pode trocar mais do que apenas trens adjacentes. Com uma plataforma rotativa mais longa, você pode trocar a posição de vários trens. Por exemplo, com uma plataforma rotativa 4 de comprimento, é possível trocar ambos os pares de interior e exterior, ao mesmo tempo, de modo que 1 2 3 4se torna 4 3 2 1. Aqui estão alguns exemplos para diferentes tamanhos de plataformas rotativas:

Length 2:
1 2 3 4 5
  ---
1 3 2 4 5

Length 3:
1 2 3 4 5
  -----
1 4 3 2 5

Length 4:
1 2 3 4 5
-------
4 3 2 1 5

Basicamente, você está apenas invertendo uma sub-lista de todo o trem. Para esclarecer, em cada movimento, você só pode trocar exatamente N trens.

Parte 3: Especificações

Entrada

Sua entrada deve incluir duas coisas: o comprimento da plataforma giratória e a ordem das carruagens. Você também pode exigir o número de vagões, se desejar. A ordem das carruagens é dada por uma lista ordenada de números (cada número representa uma carruagem), para que você possa ler a entrada como números inteiros separados por espaço, números separados por nova linha, uma matriz etc.

Resultado

Você deve gerar o número ideal (mínimo) de trocas necessárias para colocar todos os carros no pedido 1 2 3 ... N. Se não houver solução, de saída -1, No solutionou alguma outra mensagem consistente. Você não pode enviar para stderr.

Pontuação

Este é um desafio do código-golfe , portanto a pontuação é em bytes. A solução com o menor número de bytes a partir de 1º de setembro de 2016 será a solução aceita.

Exemplos

Entrada do Problema 1

4
2
1 3 2 4

Resultado

1

Explicação
Isso é bastante trivial; com uma plataforma rotativa de comprimento 2, é o mesmo que o problema normal de troca de trem. Troque oe 2o 3.

Entrada do Problema 2

4
3
1 3 2 4

Resultado

No solution (or an equivalent consistent message).

Entrada do Problema 3

9
3
1 4 5 6 3 8 7 2 9

Resultado

4

Explicação

1 4 5 6 3 8 7 2 9
          -----
1 4 5 6 3 2 7 8 9
      -----
1 4 5 2 3 6 7 8 9
    -----
1 4 3 2 5 6 7 8 9
  -----
1 2 3 4 5 6 7 8 9

Aplicam-se brechas padrão

Boa sorte!

EDIT 1 : Tornou o formato de entrada mais flexível. Graças a @Mego!
EDIT 2 : Esclareceu que uma plataforma rotativa de comprimento 4 troca os pares interno e externo. Obrigado a @TimmyD!
EDIT 3 : Esclarecido que você deve fazer permutações de comprimento Nexatamente, não no máximo. Graças a @Zgarb!

Perl, 120 bytes

Inclui +6 para -Xapi( -e o espaço também é contado porque o -ie o $'no código tornam impossível combinar as opções com-e )

Execute com a entrada STDIN e o comprimento da plataforma após a -iopção, por exemplo

perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"

Impressões -2 se não houver solução

trains.pl:

1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--

se N <= 9você pode ganhar mais 5 bytes:

1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--