8
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Having such a strict input format is not a good idea. Any input format, so long as only the list of train carriages (and optionally the length of this list) and the length of the platform is transmitted, should be acceptable. \$\endgroup\$ – Mego Aug 18 '16 at 20:28
  • \$\begingroup\$ @Mego Okay, I will make the change. \$\endgroup\$ – HyperNeutrino Aug 18 '16 at 21:30
  • 1
    \$\begingroup\$ Does a length-N platform flip exactly N trains, or at most N trains? \$\endgroup\$ – Zgarb Aug 18 '16 at 21:53
  • 1
    \$\begingroup\$ A question can only have 5 tags. I removed array-manipulation because it's so generic as to be virtually useless, and I think the question is better served by the more specific tags I added. \$\endgroup\$ – Peter Taylor Aug 19 '16 at 7:49
  • 1
    \$\begingroup\$ Related: en.wikipedia.org/wiki/Pancake_sorting. \$\endgroup\$ – orlp Aug 19 '16 at 21:06
1
\$\begingroup\$

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;$_--
\$\endgroup\$
  • \$\begingroup\$ Good job; as far as I've tested, this works! +1 & accept \$\endgroup\$ – HyperNeutrino Sep 5 '16 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.