It's a very nice application of stacks. Consider that a freight train has n railroad cars. Each to be left at different station. They're numbered 1 through n & freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination. To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e. 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between input & output tracks (i.e. holding track). The figure shows a shunting yard with three holding tracks H1, H2 & H3, also n = 9. The n cars of freight train begin in the input track & are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5,8,1,7,4,2,9,6,3 from back to front. Later cars are rearranged in desired order. To rearrange cars, we examine the cars on the input track. If the car being examined is next one in the output arrangement, we move it directly to output track. If not, we move it to the holding track & leave it there until it's time to place it to the output track. The holding tracks operate in a LIFO manner as the cars enter & leave these tracks from top. When rearranging cars, following moves are permitted: A car may be moved from front (i.e. right end) of the input track to the top of one of the holding tracks or to the end of the output track. A car may be moved from the top of holding track to end of the output track The requirement of rearrangement of cars on any holding track is that the cars should be arranged in ascending order from top to bottom. A general assignment rule should be followed that says that a new car should be moved to the holding tack that has the closest smaller number item on the top. Write a function Rearrange(inputTrack) that takes a list of cars in the input track and arranges them on the output track using three holding tracks as described above. The function will return a list of tuples describing movements of cars. The format of the tuple would be (Car#, , ) where From and To belongs to the set {"I", "O", "H1", "H2", "H3"} representing Input track, output track and the three decks. If the re-arrangement is not possible, return "Re-Arrangement Not Possible!" Sample input and output: >>> Rearrange([5, 8, 1, 7, 4, 2, 9, 6, 3]) [(3, 'I', 'H1'), (6, 'I', 'H2'), (9, 'I', 'H3'), (2, 'I', 'H1'), (4, 'I', 'H2'), (7, 'I', 'H3'), (1, 'I', 'O'), (2, 'H1', 'O'), (3, 'H1', 'O'), (4, 'H2', 'O'), (8, 'I', 'H1'), (5, 'I', 'O'), (6, 'H2', 'O'), (7, 'H3', 'O'), (8, 'H1', 'O'), (9, 'H3', 'O')] >>> Rearrange([1, 9, 8, 7, 6, 5, 4, 3, 2]) Re-Arrangement Not Possible!nt is not possible, return "Re-Arrangement Not Possible!"
It's a very nice application of stacks. Consider that a freight train has n railroad cars. Each to be left at different station. They're numbered 1 through n & freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination.
To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e. 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between input & output tracks (i.e. holding track).
The figure shows a shunting yard with three holding tracks H1, H2 & H3, also n = 9. The n cars of freight train begin in the input track & are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5,8,1,7,4,2,9,6,3 from back to front. Later cars are rearranged in desired order.
To rearrange cars, we examine the cars on the input track. If the car being examined is next one in the output arrangement, we move it directly to output track. If not, we move it to the holding track & leave it there until it's time to place it to the output track. The holding tracks operate in a LIFO manner as the cars enter & leave these tracks from top.
When rearranging cars, following moves are permitted:
- A car may be moved from front (i.e. right end) of the input track to the top of one of the holding tracks or to the end of the output track.
- A car may be moved from the top of holding track to end of the output track
The requirement of rearrangement of cars on any holding track is that the cars should be arranged in ascending order from top to bottom. A general assignment rule should be followed that says that a new car should be moved to the holding tack that has the closest smaller number item on the top.
Write a function Rearrange(inputTrack) that takes a list of cars in the input track and arranges them on the output track using three holding tracks as described above.
The function will return a list of tuples describing movements of cars. The format of the tuple would be (Car#, <From>, <To>) where From and To belongs to the set {"I", "O", "H1", "H2", "H3"} representing Input track, output track and the three decks.
If the re-arrangement is not possible, return "Re-Arrangement Not Possible!"
Sample input and output:
>>> Rearrange([5, 8, 1, 7, 4, 2, 9, 6, 3])
[(3, 'I', 'H1'), (6, 'I', 'H2'), (9, 'I', 'H3'), (2, 'I', 'H1'), (4, 'I', 'H2'), (7, 'I', 'H3'), (1, 'I', 'O'), (2, 'H1', 'O'), (3, 'H1', 'O'), (4, 'H2', 'O'), (8, 'I', 'H1'), (5, 'I', 'O'), (6, 'H2', 'O'), (7, 'H3', 'O'), (8, 'H1', 'O'), (9, 'H3', 'O')]
>>> Rearrange([1, 9, 8, 7, 6, 5, 4, 3, 2])
Re-Arrangement Not Possible!nt is not possible, return "Re-Arrangement Not Possible!"
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
