2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Must the following condition hold : "All As, Bs and Cs must be respectively in first, second and third lane respectively."? I mean, Can it be: BBB AAA CCC ? i.e. in essence, can all similar trains be together in any lane or must they only be in the lanes mentioned? Also in the link you have mentioned the code : $a \text{ } b \text{ } c$ where $a$ trains are take from from lane $b$ to lane $c$. Is it allowed to modify it as follows: $a \text{ } b \text{ } c \text{ } d$ where $d$ represents the number of trains left at the destination i.e. $d\le a$? $\endgroup$
    – John Brookfields
    Jun 8 '20 at 14:20
  • 1
    $\begingroup$ (Continuation of the above comment ) So, if the remaining trains or $k$ trains $(k\le d)$ are to be left at destination $c$, then we denote it by $0 \text{ } 0 \text{ } c \text{ } k$ $\endgroup$
    – John Brookfields
    Jun 8 '20 at 14:23
  • $\begingroup$ @JohnBrookfields Yes I have fixed lanes in specific order AAABBBCCC because to make practical moves such fixed order would be required. $\endgroup$
    – Always Confused
    Jun 8 '20 at 16:46
  • 1
    $\begingroup$ I am afraid not. The innermost train in the first lane shall be fixed for optimizing the algorithm. So if the trains are distributed viz: BAC ACB CBA, then it will be practical (more efficient) to implement BBB AAA CCC $\endgroup$
    – John Brookfields
    Jun 8 '20 at 16:50
  • 1
    $\begingroup$ Yes @AlwaysConfused. That's what I said in my comment #1 too. To be more precise, $a\text{ }b\text{ }c$ means move the last (rightmost) $a$ trains from lane $b$ to lane $c$ $\endgroup$
    – John Brookfields
    Jun 8 '20 at 16:58
2
$\begingroup$

Q1: Base algorithm.

train 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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ One or both moves used in picking up all cars might not reduce the total number of mismatched connected cars, because joining the cars into one line might create two more mismatched pairs which were not there before. So your method may be up to two moves away from optimal. $\endgroup$
    – Jaap Scherphuis
    Jun 12 '20 at 19:34
  • $\begingroup$ Yes, that's correct. I do not have a valid answer to part 2 then. $\endgroup$
    – SE - stop firing the good guys
    Jun 12 '20 at 22:04

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.