Q1: Base algorithm.
We can then apply the following optimizations:
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.
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.
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.
During the first part, the algorithm may combine together unequal cars, potentially making it suboptimal