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
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!