In the MTA Subway system, occasionally cars on a train need to be re-arranged. F
ID: 3669621 • Letter: I
Question
In the MTA Subway system, occasionally cars on a train need to be re-arranged. For instance, assume we label the cars of a train with the number [5,8,1,7,4,2,9,6,3] (the right end of the list is the front of the train - in this case 3), and we would like to arrange the cars like this: [9,8,7,6,5,4,3,2,1].
For this purpose the MTA has special shunting yards. A shunting yard consists of an input track, an output track, and holding tracks. The input and output track operate like queues (in first in first out fashion). The holding tracks have to be used like stacks (in a last in first out fashion): the last train car entering the holding track is the first car to leave the track. In this case there are 3 holding tacks called: S, S, and S.
To reorganize a train, the train dispatcher can use only the following operations:
Move the car at the front of the input track to the back of of the output track.
Move the car at the front of the input track to the top of one of the holding tracks.
Move the car at the top of one of the holding tracks to the back of the output track.
Cars cannot be moved between the holding tracks. Once a car is on a holding track it cannot move back to the input track (since the input track is a queue). The goal is always to organize the train cars in increasing order (front to back on the output track, as in the example).
Answer the following questions:
(a) Provide a solution for this specific input train and 3 holding tracks as a sequence of steps.
(b) Show an example for a train of length 9 that cannot be rearranged in increasing order using 3 holding tracks.
Explanation / Answer
The cars initially are in the order 5,8,1,7,4,2,9,6,3 from back to front.
Let holding tracks be S1, S2 & S3.
a)
The car 3 is at the front, so it can't be output yet, as it to be preceded by cars 1 & 2. So car 3 is detached & moved to holding track S1.
The next car 6 can't be output & it is moved to holding track S2. Because we have to output car 3 before car 6 & this will not possible if we move car 6 to holding track S1.
Now it's obvious that we move car 9 to S3.
The requirement of rearrangement of cars on any holding track is that the cars should be preferred to arrange in ascending order from top to bottom.
So car 2 is now moved to holding track S1 so that it satisfies the previous statement.
If we move car 2 to S2 or S3, then we've no place to move cars 4,5,7,8.
The least restrictions on future car placement arise when the new car is moved to the holding track that has a car at its top with smallest label such that < . We may call it an assignment rule to decide whether a particular car belongs to a specific holding track.
When car 4 is considered, there are three places to move the car S1,S2,S3. The top of these tracks are 2,6,9.So using above mentioned Assignment rule, we move car 4 to S2.
The car 7 is moved to S3.
The next car 1 has the least label, so it's moved to output track.
Now it's time for car 2 & 3 to output which are from S1(in short all the cars from S1 are appended to car 1 on output track).
The car 4 is moved to output track. No other cars can be moved to output track at this time.
The next car 8 is moved to holding track S1.
Car 5 is output from input track. Car 6 is moved to output track from S2, so is the 7 from S3,8 from S1 & 9 from S3.