13,896,966 members
alternative version

#### Stats

42.3K views
17 bookmarked
Posted 13 Jan 2006
Licenced

# Boxcar Shunting Algorithm

, 19 Jan 2006
An interesting algorithm with two solutions.

## Problem

I ran across this problem when preparing for a programming contest in college.

A freight train has N boxcars, each of which is to be left at a different station. Assume that the stations are numbered 1 through N and that the freight train visits these stations in the order N through 1. The boxcars are labeled by their destination. To facilitate their removal from the train, the boxcars must be arranged so that they are in the order 1 to N from the front of the train to the back of the train. When the boxcars are in this order, the last car is detached at each station.

The boxcars can be rearranged at a shunting yard that has an input track, an output track, and K holding tracks between the input tracks and output tracks. The N boxcars in the freight train enter the shunting yard on the input track in a random order and leave on the output track in the proper ascending order. Due to the physical nature of the railroad tracks, there are only two moves possible in the shunting yard:

1. A boxcar may be moved from the front (right end, where boxcar 3 is in Figure 1) of the input track to the top of one of the holding tracks or to the rear (left end, where boxcar 9 is in Figure 2) of the output track.
2. A boxcar may be moved from the top of a holding track to the rear of the output track. Figure 1 depicts a train with 9 cars arriving on the input track of a shunting yard with 3 holding tracks. Figure 2 depicts the same train leaving the shunting yard after having its cars rearranged in proper ascending order of destination.

Write a program that decides if a given freight train with N boxcars can be rearranged in a shunting yard with K holding tracks.

For our purpose, we are only concerned with how many holding tracks are required to rearrange the boxcars, then we can easily check if that meets the original problem constraint.

## Solution 1 - The hard way

My first thought was to solve this problem the same way it would be carried out in the field. I replaced the holding tracks with stacks, and wrote the algorithm to rearrange the boxcars. Expressing the algorithm was easy once I figured out the whole process from beginning to end:

for (int j = 0; j < incoming.size(); j++)
{
int cur = incoming[j];
if (cur - 1 == out)
{
out = cur;
bool move;
do
{
move = false;
for (int i = 0; i < holds.size(); i++)
{
if (holds[i].size() > 0 &&
holds[i].top() - 1 == out)
{
move = true;
out = holds[i].top();
holds[i].pop();
}
}
}
while (move);
}
else
{
for (int i = 0; i < holds.size(); i++)
{
if (holds[i].empty())
{
holds[i].push(cur);
break;
}
else if (cur < holds[i].top())
{
holds[i].push(cur);
break;
}
}
if (i == holds.size())
{
holds.push_back(newstack);
holds[i].push(cur);
}
}
}

## Demo

The demo project just takes the user input from the command line, pushing the boxcars into a vector, and calls the shunting function.

A list of licenses authors might use can be found here

## Share

 Web Developer United States
No Biography provided

## You may also be interested in...

 First Prev Next
 Where is the easy way ? xiedong4-Feb-06 19:44 xiedong 4-Feb-06 19:44
 Difference in the output of Hard way and easy way. Arvind Bharti18-Jan-06 20:18 Arvind Bharti 18-Jan-06 20:18
 Re: Difference in the output of Hard way and easy way. Will Gray19-Jan-06 4:09 Will Gray 19-Jan-06 4:09
 That is not the boxcar problem I remember from Dijkstra antoncl15-Jan-06 22:44 antoncl 15-Jan-06 22:44
 Re: That is not the boxcar problem I remember from Dijkstra Will Gray16-Jan-06 3:41 Will Gray 16-Jan-06 3:41
 Last Visit: 20-Mar-19 11:27     Last Update: 20-Mar-19 11:27 Refresh 1