# Sort 9 train cars on 3 paths

On the three paths of a station are A, B, and C types of train cars as shown in the figure.

A locomotive driver (L) can attach from 1 to 9 train cars to a locomotive at any time, move them to the right path, and then return them to any left path.

For example, if the locomotive picks up 2 train cars from track no. 3 to track no. 1, then after such an action, the distribution of train cars along the tracks will be as follows:

1. А C B А C
2. B C А
3. B

We code these actions by one line as: 2 3 1

Question 1.

It is necessary to develop an algorithm for the driver's actions to sort train cars. On each path, the train cars the same type should be (it doesn’t matter which path).

Question 2. It is necessary to show that your solution is the shortest.

• old but good question :)
– Oray
Jun 6 '20 at 8:19
• They are probably not trains, but train cars. Jun 6 '20 at 11:49
• Cool problem! I would be interested to solve a larger case of this. Reminds me of towers of Hanoi. Jun 6 '20 at 12:38
• @AlwaysConfused If the tracks were ♥ / ♦ / ♣ instead of 1 / 2 / 3, then "♦3♥" (231) would mean "move 3 carriages from track ♦ to track ♥". The first and last numbers are which track, and the middle number is how many carriages. Jun 8 '20 at 16:08
• @Chronocidal, I think the first number in the notation is the number of carriages. Not the second one. So 231 means move 2 cars from track 3 to track 1. Jun 10 '20 at 3:41

Here is an optimal solution:

7 moves:
213, 121, 431, 113, 223, 132, 212

Or in full:

 acb
bca
bac

a
bca
baccb

aa
bc
baccb

aaaccb
bc
b

aaacc
bc
bb

aaacc

bbbc

aaacc
c
bbb

aaa
ccc
bbb

Proof of optimality:

There are 6 pairs of adjacent carriages of mismatched types. Each move can break up at most one such adjacent pair by moving away the right carriage to another track. The left-most carriages of the tracks are not all different types - there are two Bs - so at least one of the left-most carriages will have to move as well. Therefore at least 7 moves are necessary. This solution uses 7 moves, so cannot be made shorter.

• Could you please explain how many 7 moves solutions can be?
– Nick
Jun 6 '20 at 6:28
• @Nick: There are a lot of them. I did a computer search, and it says there are 562, of which 179 end as aaa/bbb/ccc and 383 as aaa/ccc/bbb. Jun 7 '20 at 16:06

I reached to a 9-step (8 moves) solution it is as follows:

GIF animated version

Still-image version:

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

(although I could not understand the 123 notation; sorry about it)