Boxcar Shunting Algorithm

• Download source files - 56.3 Kb

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.