Programming Project: Railroad Car Rearrangement

Introduction

A freight train has n railroad cars, each of which is going to be left at a different station. Assume that the stations are numbered 0 through n 1, the railroad cars are labeled accordingly by their destination. To facilitate removal of the railroad cars from the train, the cars must be reordered so that they are also in the order 0 through n 1 from front to back. For example, when n = 9 and initially the cars are in the order (f ront)2, 5, 8, 1, 3, 6, 0, 7, 4(back), they should be rearranged in the order (f ront)0, 1, 2, 3, 4, 5, 6, 7, 8(back).

The cars are reordered at a shunting yard that has an input track, an output track, and k holding tracks between the input and output tracks. The n cars in initial order starts up in the input track and are to finish in the output track in the order 0 through n 1. We begin the rearrangement by examining the cars in the input track from front to back, aiming at finding the first car that can be moved to the output track by moving the other examined cars into the holding tracks. (For example, we will move the cars 2, 5, 8, 1, 3, 6 one by one into the holding tracks before we move car 0 to the output track.) Then we look for the next car(car 1 in the example) by examining the input track and the holding tracks. The process goes on until all the cars are moved to the output track. Be reminded that at any particular time of the rearrangement, we always look for some car that is to be moved to the output track.

The holding tracks can operate as stacks. i.e., in a LIFO manner as cars enter and leave these tracks. More precisely, only the following two operations are permitted.

• A car may be moved from the front of the input track to the top of one of the holding tracks or to the back of the output track.

• A car may be moved from the top of a holding track to the back of the output track. The holding tracks can, alternatively, operate as queues. i.e., in a FIFO manner as cars enter and

leave these tracks. More precisely, only the following two operations are permitted.

• A car may be moved from the front of the input track to the rear of one of the holding tracks or to the back of the output track.

• A car may be moved from the front of a holding track to the back of the output track.

2.2 Holding tracks (stacks) details

• The cars in a holding track (with stack) must be in an increasing order from top to bottom, otherwise the rearrangement cannot work.

• When there are more than one available holding tracks (i.e., the tracks that satisfy the in- creasing order), a new car u must be placed to the holding track that has at its top a car with the smallest car v such that v > u. This is called assignment rule.

• However, empty holding tracks are preferred to non-empty tracks. That is, whenever there are empty holding tracks, a new car will be placed to one of them.

• For some initial order may require more holding tracks: there are cases that all holding tracks are employed, and placing a new car to any of them will break the assignment rule. (For example, for an initial order (f ront)1, 2, ..., n 1, 0(back), n 1 holding tracks are required.)

2.3 Holding tracks (queues) details

• The cars in a holding track (with queue) must be in an increasing order from front to rear, otherwise the rearrangement cannot work.

• When there are more than one available holding tracks (i.e., the tracks that satisfy the in- creasing order), a new car u must be placed to the holding track that has at its rear a car with the largest car v such that u > v. This is called assignment rule.

2

• Non-empty holding tracks are preferred to empty tracks. That is, whenever there are non- empty and feasible holding tracks, a new car will be placed to a non-empty holding track that satisfies the assignment rule.

• For some initial order may require more holding tracks: there are cases that all holding tracks are employed, and placing a new car to any of them will break the assignment rule. (For example, for an initial order (f ront)n 1, ..., 1, 0(back), n 1 holding tracks are required.)

2.4 What to do

• Download the starter code from the course web site. Read the starter code and make sure you understand how it works before attempting to modify it.

• Design modifications to the starter code for the methods that described in the Introduction and Details sections.

• Update the starter code with your modifications.

• Run the code and your simulation. Note that running as1.java with your implementation, the output should be

  INSERT car 2 into stack track 0 INSERT car 5 into stack track 1 INSERT car 8 into stack track 2 INSERT car 1 into stack track 0 INSERT car 3 into stack track 1 INSERT car 6 into stack track 2 output car 0 directly 

  output car 1 from stack track 0 output car 2 from stack track 0 output car 3 from stack track 1 INSERT car 7 into stack track 0 output car 4 directly 

  output car 5 from stack track 1 output car 6 from stack track 2 output car 7 from stack track 0 output car 8 from stack track 2 

  INSERT car 2 into queue track 2 INSERT car 5 into queue track 2 INSERT car 8 into queue track 2 INSERT car 1 into queue track 1 INSERT car 3 into queue track 1 INSERT car 6 into queue track 1 output car 0 directly 

  output car 1 from queue track 1 output car 2 from queue track 2 output car 3 from queue track 1 INSERT car 7 into queue track 1 output car 4 directly 

  output car 5 from queue track 2 output car 6 from queue track 1 output car 7 from queue track 1 output car 8 from queue track 2