Based on 9-trains puzzle

Question

Based on this problem, we have got some algorithms that can sort the 9 train cars in a given specific arrangement. But say if the 9 train cars are given in any-arrangement?

Say

ABC
ABC
ABC

or

ACB
BCA
BCA

or

ABC
BCA
CAB

etc.

then what algorithm can be designed so that the locomotive engine L can automatically sort the trains into

AAA
BBB
CCC

(in this definite order)

Q1. Write a flow chart algorithm for the locomotive engine to sort the train cars (not necessarily the minimal).

Q2. Write a flow chart algorithm for the locomotive engine to sort the train cars in the shortest way.

Answer 1

Q1: Base algorithm.

We can then apply the following optimizations:

Optimization 1:

We don't always have to pick up all cars from a track at the beginning. We can leave all the last ones that are already on the right track.

Optimization 2:

If all cars on a track are already on the right track to begin with, we don't have to go into that track at all.

Optimization 3:

We can detach multiple last cars at once if they are always equal (and we will always do that if it is the case).

Q2: Proof that the optimized algorithm is always optimal (partial)

Minimum number of steps:

Different cars coupled together have to be broken up. A wrong car on the end of a track would have to be broken up from the end.

Maximum number of steps per move:

A move consists of one break up, moving out, and moving in again then attaching. Thus, at most 1 step can be performed per move.

Number of steps performed by the algorithm per move;

When picking up cars at first, the algorithm never breaks up two equal cars. When detaching cars later, the algorithm never break apart two equal cars. Therefore, the algorithm always achieves the maximum number of steps per move.

However:

During the first part, the algorithm may combine together unequal cars, potentially making it suboptimal