Thread: Need help to implement an algorithm

I have three different data structures:


-int-array with 144 entries called trains, each entry is a different trainID


-Station-array with 367 entries, each entry is a different Station-struct:

Code:

    typedef struct
    {
      int id;
      char name[51];
    }Station;

-Schedule-array with 2548 entries, each is a different Schedule-entry struct:

Code:

    typedef struct
    {
      int trainId;
      int stationId;
      int arrival;     //in minutes, i.e. 2:15am = 135
      int departure;   //in minutes
    }Schedule;

What I have to do, is to find all trains, which overtake an other train and ouput the trainId.
I got a hint from the teacher:

Code:

    For all trains B
       For all trains A
          Find station C, where A departs and B later departs than A (that one where A departs as earliest)
          If such exists:
             For all stations D, where A arrives after C and B also arrives
                If B is on station D earlier than A, then B is overtaker.

I think that should be some for-loops and some if-statements, but i don't get it.


I tried some different nested loops, but it never worked right. When i build it like the hint, how can i compare with the schedule, on which position do I need a loop which iterates over the schedule... Because the trains just have the id, also the station, I always have to look after entries in the schedule, I think this is my main problem.

Here some code from Main, I tried some different ways, i.e. instead of train-loops with schedule-loops, etc.

Code:

    int main (int argc, char *argv[])
    {    
      //lenght of all arrays
      int lengthOfStations = countLines(argv[1]);
      int lengthOfTrains = countLines(argv[2]);
      int lengthOfSchedule = countLines(argv[3]);
    
      int *B = readTrains(argv[2]);
      int *A = readTrains(argv[2]);
      Station *C = readStation(argv[1]);
      Station *D = readStation(argv[1]);
      Schedule *sched = readSchedule(argv[3]);
    
       //qsort(sched, lengthOfSchedule, sizeof(Schedule), compare);
    
      /* HERE I NEED THE NESTED LOOPS */ 

      return 0;
    }

The arguments are like above descripted, when I call readSchedule, then i.e. Schedule B is a Schedule-array with all 2548 schedule-elements, each is in this shape: "trainId stationId arrival departure" (i.e. 28281 6228 392 393). The expected output should be a list from all trains which overtake another train.

TY

Thanks for your reply.
No just one stationId in this case.

My problem is, when I iterate about all trains A and then about all trains B, and then iterate about all stations C, how can I compare this all together the easiest way in the schedule?
Because in the train-"data structure" I have just the trainId and in the station-structure just the stationId.

Then I thought I could handle that when I use schedule-"objects" instead of train-arrays or station-arrays, but that also does not worked right.

a and b have to start at the same station and to arrive at the same station:

Imagine two trains heading for station 1
a starts at 08:00 and arrives at 12:00
b starts at 09:00 and arrives at 11:00
Do they pass?

So a starts at 8 at station1 and arrives at 12 on station2, the same with b, then b overtakes a.

What about this?
a starts at 08:00 and arrives at 12:00 at station 1
b starts at 09:00 and arrives at 11:00 at station 2
Do they pass?

Can't compare this, because they must have at least one same station where they start and one same station where both arrive.

Originally Posted by Salem

So can you write a logical statement that determines whether a passes b ?

What do you mean with passes and which example?

So my problem is still that I do not know how I can compare all three data-structures the easiest way, so that I can build my for-loops and get the right solution.

Sorry, I'm to stupid for that. I don't know the equation of motion and it looks very complicated.

B overtakes A, because b starts after a and arrives before a.

Originally Posted by birdbox

B overtakes A, because b starts after a and arrives before a.

That's exactly correct. The equations of motion don't enter into it. It seems as if there's one giant loop of track with stations along it and all you have to do is determine which trains have "crossed paths" based on their departure and arrival times at two stations they both stopped at.

The given algorithm unpacked a little:

Code:

for all trains T1:
    for all trains T2:
        for all stations SD:  // stations departed from
            if T1 and T2 depart from SD and T2 departs later than T1:
                for all stations SA:  // stations arrived at
                    if T1 and T2 arrive at SA after SD
                           and T2 arrives at SA earlier than T1:
                        T2 must have passed T1

In your code at the end of your first post, reading in the trains and and stations twice indicates a misunderstanding. You only need one copy of the data in memory. Train T1 and T2 are just indices into the array containing the train data. SD and SA are indices into the station array.

Hey thanks!

Originally Posted by algorism

In your code at the end of your first post, reading in the trains and and stations twice indicates a misunderstanding. You only need one copy of the data in memory. Train T1 and T2 are just indices into the array containing the train data. SD and SA are indices into the station array.

Yes absolutely.

But when I try to implement it, then my first problem is on line 4:

Code:

if T1 and T2 depart from SD and T2 departs later than T1:

How can I check that in the schedule?
Maybe I need anywhere another loop which iterates over the schedule-array, so that I can check that if-statement somehow.

no more hints?

Write a schedule lookup function:

Code:

int x1 = lookup(sched, t1, sd);
int x2 = lookup(sched, t2, sd);

if (sched[x2].departure > sched[x1].departure)
    ...

Ok thank you both so much, I think I've got it!