Problema de cambio de tren extendido

Parte 1: problema normal de intercambio de trenes

En 1996 CCC (Canadian Computing Competition), el primer problema de la Etapa 2 fue un problema de intercambio de trenes. Puedes visitar el enlace aquí . Esencialmente, tiene un montón de trenes numerados y desea saber cuántos intercambios de trenes necesita para ponerlos en orden, y cada operación de intercambio de trenes le permite intercambiar dos trenes adyacentes. Dado que los vagones de tren pueden correr de cualquier manera, a nadie le importa el hecho de que los vagones de tren se enfrentan al otro lado cuando se intercambian. Esto es bastante fácil; todo lo que necesitas hacer es:

Encuentra el número de pasos para clasificarlo en burbujas; es el algoritmo de clasificación más eficiente cuando solo puede realizar intercambios de elementos adyacentes

Entonces, hice una más difícil.

Parte 2: cómo funciona este desafío

Esencialmente, ahora puede intercambiar más que solo trenes adyacentes. Con una plataforma giratoria más larga, puede intercambiar la posición de múltiples trenes. Por ejemplo, con una plataforma giratoria de longitud 4, puede intercambiar los pares internos y externos al mismo tiempo, por lo que se 1 2 3 4convierte 4 3 2 1. Aquí hay algunos ejemplos para diferentes tamaños de plataforma giratoria:

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

Esencialmente, solo está invirtiendo una sublista de todo el tren. Para aclarar, en cada movimiento, solo puedes intercambiar exactamente N trenes.

Parte 3: Especificaciones

Entrada

Su entrada debe incluir dos cosas: la longitud de la plataforma giratoria y el orden de los vagones del tren. También puede requerir la cantidad de vagones de tren si lo desea. El orden de los vagones del tren viene dado por una lista ordenada de números (cada número representa un vagón del tren), por lo que puede leer la entrada como enteros separados por espacios, enteros separados por nueva línea, una matriz, etc.

Salida

Debe generar el número óptimo (mínimo) de intercambios necesarios para que todos los carros estén en el orden 1 2 3 ... N. Si no hay solución, la producción -1, No solutiono algún otro mensaje coherente. No puede enviar a stderr.

Puntuación

Este es un desafío de código de golf , por lo que la puntuación está en bytes. La solución con el menor número de bytes a partir del 1 de septiembre de 2016 será la aceptada.

Ejemplos

Problema 1 Entrada

4
2
1 3 2 4

Salida

1

Explicación
Esto es bastante trivial; Con una plataforma giratoria de longitud 2, es lo mismo que el problema normal de intercambio de trenes. Cambiar el 2y el 3.

Problema 2 Entrada

4
3
1 3 2 4

Salida

No solution (or an equivalent consistent message).

Problema 3 Entrada

9
3
1 4 5 6 3 8 7 2 9

Salida

4

Explicación

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

Se aplican lagunas estándar

¡Buena suerte!

EDITAR 1 : hizo que el formato de entrada sea más flexible. Gracias a @Mego!
EDIT 2 : aclaró que una plataforma giratoria de longitud 4 intercambia los pares internos y externos. Gracias a @TimmyD!
EDITAR 3 : Aclaró que debe hacer permutaciones de longitud Nexactamente, como máximo. Gracias a @Zgarb!

Perl, 120 bytes

Incluye +6 para -Xapi( -y el espacio también se cuenta porque tanto el -iy el $'en el código hacen que sea imposible combinar las opciones con -e)

Ejecute con la entrada en STDIN y la longitud de la plataforma después de la -iopción, p. Ej.

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

Imprime -2si no hay solución

trains.pl:

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

si N <= 9entonces puedes ganar 5 bytes más:

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