Click here to Skip to main content
13,896,966 members
Click here to Skip to main content
Add your own
alternative version

Stats

42.3K views
384 downloads
17 bookmarked
Posted 13 Jan 2006
Licenced

Boxcar Shunting Algorithm

, 19 Jan 2006
Rate this:
Please Sign up or sign in to vote.
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Will Gray
Web Developer
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
QuestionWhere is the easy way ? Pin
xiedong4-Feb-06 19:44
memberxiedong4-Feb-06 19:44 
GeneralDifference in the output of Hard way and easy way. Pin
Arvind Bharti18-Jan-06 20:18
memberArvind Bharti18-Jan-06 20:18 
GeneralRe: Difference in the output of Hard way and easy way. Pin
Will Gray19-Jan-06 4:09
memberWill Gray19-Jan-06 4:09 
GeneralThat is not the boxcar problem I remember from Dijkstra Pin
antoncl15-Jan-06 22:44
memberantoncl15-Jan-06 22:44 
GeneralRe: That is not the boxcar problem I remember from Dijkstra Pin
Will Gray16-Jan-06 3:41
memberWill Gray16-Jan-06 3:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web04 | 2.8.190306.1 | Last Updated 20 Jan 2006
Article Copyright 2006 by Will Gray
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid