Extendable Train Swapping Problem

Question

Extended Train Swapping Problem

Part 1: Normal Train Swapping Problem

In the 1996 CCC (Canadian Computing Competition), the first Stage 2 problem was a Train Swapping Problem. You can visit the link here. Essentially, you have a bunch of numbered trains, and you want to find out how many train swaps you need to get them in order, and each train swap operation allows you to swap two adjacent trains. Since train carriages can run either way, nobody cares about the fact that the train carriages face the other way when swapped. This is pretty easy; all you need to do is:

Find the number of steps to bubble-sort it; it's the most efficient sorting algorithm when you can only make adjacent element swaps

So, I made a harder one.

Part 2: How this challenge works

Essentially, you can now swap more than just adjacent trains. With a longer rotating platform, you can swap the position of multiple trains. For example, with a rotating platform of length 4, you can swap both the inner and outer pairs at the same time, so 1 2 3 4 becomes 4 3 2 1. Here are some examples for different rotating platform sizes:

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

Essentially, you're just inverting a sublist of the entire train. To clarify, in each move, you can only swap exactly N trains.

Part 3: Specifications

Input

Your input must take in two things: the length of the rotating platform, and the order of the train carriages. You may also require the number of train carriages if you wish. The order of the train carriages is given by an ordered list of numbers (each number representing a train carriage), so you can read the input as space-separated integers, newline-separated integers, an array, etc.

Output

You must output the optimal (minimum) number of swaps needed to get the carriages all into the order 1 2 3 ... N. If there is no solution, output -1, No solution, or some other consistent message. You may not output to stderr.

Scoring

This is a code-golf challenge, so scoring is in bytes. The solution with the lowest number of bytes as of September 1st, 2016 will be the accepted one.

Examples

Problem 1 Input

4
2
1 3 2 4

Output

1

Explanation
This is pretty trivial; with a rotating platform of length 2, it's the same as the normal train swapping problem. Swap the 2 and the 3.

Problem 2 Input

4
3
1 3 2 4

Output

No solution (or an equivalent consistent message).

Problem 3 Input

9
3
1 4 5 6 3 8 7 2 9

Output

4

Explanation

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

Standard loopholes apply

Good luck!

EDIT 1: Made the input format more flexible. Thanks to @Mego!
EDIT 2: Clarified that a rotating platform of length 4 swaps both the inner and outer pairs. Thanks to @TimmyD!
EDIT 3: Clarified that you must make permutations of length N exactly, not at most. Thanks to @Zgarb!

Answer 1

Perl, 120 bytes

Includes +6 for -Xapi (- and space are counted too because both the -i and the $' in the code make it impossible to combine the options with -e)

Run with the input on STDIN and the platform length after the -i option, e.g.

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

Prints -2 if there is no solution

trains.pl:

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

if N <= 9 then you can gain 5 more bytes:

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