RailRoad JAVA

Download:	http://solutionzip.com/downloads/railroad-java/
Suppose a freight train has n railroad cars. The train is going to visit n stations dropping off one car at each station. The railroad cars are unloaded from a ship and can arrive in any arbitrary order. We want to attach the railroad cars to the engine in the order such that at each station, we can simply detach the last car. The different stations are numbered 1 through n and the train will visit the stations in the order n, n-1, n-2, …,2, 1. Each railroad car is labeled with the number of its destination station. Sorting the cars in the order 1 through n from front to back will allows us to simply detach the last car at each station.
The cars unloaded from the ship are on one end of a piece of track (the input track) and they are leave from the other end (the output track). Between these two ends are a number of holding tracks at right angles to the main track which are used to temporarily park cars in the sorting process. The diagram below shows an initial and final configuration with three holding tracks. Initially, all the cars are on the input side. At the end, they should all be on the output side in the correct order.
The following moves are permitted.
• The front car in the input track can be moved directly to the output track
• The front car in the input track can be moved to the top of a holding track
• A car can be moved from the top of a holding track to the output track
Each holding track will be represented by a generic stack. We don’t know how many holding tracks we will have in advance so we will use an ArrayList of generic Stacks (due to the way generics are handled in Java, there is a problem with creating a simple array of generic Stacks. The only coding difference you will encounter is that instead of accessing an element using the array notation , you will use the methods get(i) and set(i,element)).
The strategy for sorting the cars is to examine each car on the input track from front to back. If the current car is the next one needed on the output track, then move it to the output track, otherwise we move it to the top of a holding track.
If the current car moves from the input track to the output track, then the next car needed on the output track may already be on the top of a holding track. In fact the next several needed cars may be on the holding tracks. So after moving a car from the input track to the output track, we do the following. While the minimum car on the top of a holding track is the next one needed on the output track, move the minimum car from the top of its holding track to the output.
If instead the current car moves to the top of a holding track, which holding track should we use? We don’t want to place a bigger car on top of a smaller because this would block the smaller car which we need to access first. So we will only place the car on top of a larger car. Suppose we have a choice of such tracks. E.g. suppose the current car is 2 and the top of two holding tracks are 9 and 5. Suppose we place car 2 on top of car 9 and that the next car is 7. Now we can’t place the 7 on either track (2 and 5 are on top). If instead we had placed the 2 on the 5, we would be able to continue by placing the 7 on the 9. By placing the 2 on the 9, we have eliminated the potential holding spaces for cars 6, 7, and 8 on top of car 9. Hence when there is a choice, we should place the car on top of the smaller one in order to leave as many places open as possible for future cars. In general, if we need to move car i to a holding track, we place it on the holding track whose top element is the smallest element greater than i. If no holding track has a top element greater than i, then we must place the car on an empty track (if no such track is available, we need to report back that we cannot sort the cars). If you are having trouble making sense of this, see the sample output file and figure out why this strategy results in the indicated moves.


Download:	http://solutionzip.com/downloads/railroad-java/