Algorithm to determine when midnight occurs based on segments of a traveling bus

Question

I am writing an importer that takes information from a bus company and provides it in the following format: 1. Stations are numbered with indexes from 0 to n (0,1,2,3,4,5... etc)

2. The provider sends a list of segments: 0->1,0->3,4->5, etc, which represent the trips between the stations. Each station has at least one segment provided.

3. Each segment has an integer that represents how many times time travels past midnight.

So here are a few examples: Example 1:

0->2: 1

0->3: 1

1->2: 0

1->3: 0

Which actually means that midnight occurs only once between station 0 and station 1.

Example 2:

0->2: 1

1->3: 1

2->3: 0

Which means that midnight occurs only once between station 1 and station 2

It is possible that in some cases the information will not be enough to find all midnight crossings, in which case the destination should be skipped.

Is there an algorithm for discovering these things?

My attempts so far: I discovered that if I lay out all of the stations for the second example like:

0--------1--------2--------3

Then I apply the maximum crossings for 0-2 and 1-3, this means that:

0->1 has between 0 and 1 crossings

1->2 has between 0 and 1 crossings

2->3 has between 0 and 1 crossings

After that I apply the third rule - 2->3 has 0 crossings, which leaves me with:

0->1: 0,1

1->2: 0,1

2->3: 0

Which gives me the following combinations:

0,0,0

0,1,1

1,1,0

1,0,0

Then I apply the rules again (position 1 + position 2 should be 1 and position 2 + position 3 should be 1) and I'm left with only:

0,1,0

Which means that midnight occurs once between station 1 and station 2

However, this method requires generating all possible combinations between the numbers, which is not applicable to a programming algorithm. There is a possibility that each segment will have 0,1,2,3 and with 20 stations, that would be 4 to the power of 20 combinations.

Does anyone have another idea on how to do this?

Answer 1

After using @samgak 's solution and converting the segments to variables and creating the matrix, I found a programming algorithm that calculates the final result.

You can find the algorithm in multiple languages here: https://rosettacode.org/wiki/Gaussian_elimination

Here is the PHP answer (that's what I needed):

function swap_rows(&$a, &$b, $r1, $r2)
{
    if ($r1 == $r2) return;

    $tmp = $a[$r1];
    $a[$r1] = $a[$r2];
    $a[$r2] = $tmp;

    $tmp = $b[$r1];
    $b[$r1] = $b[$r2];
    $b[$r2] = $tmp;
}

function gauss_eliminate($A, $b, $N)
{
    for ($col = 0; $col < $N; $col++)
    {
        $j = $col;
        $max = $A[$j][$j];

        for ($i = $col + 1; $i < $N; $i++)
        {
            $tmp = abs($A[$i][$col]);
            if ($tmp > $max)
            {
                $j = $i;
                $max = $tmp;
            }
        }

        swap_rows($A, $b, $col, $j);

        for ($i = $col + 1; $i < $N; $i++)
        {
            $tmp = $A[$i][$col] / $A[$col][$col];
            for ($j = $col + 1; $j < $N; $j++)
            {
                $A[$i][$j] -= $tmp * $A[$col][$j];
            }
            $A[$i][$col] = 0;
            $b[$i] -= $tmp * $b[$col];
        }
    }
    $x = array();
    for ($col = $N - 1; $col >= 0; $col--)
    {
        $tmp = $b[$col];
        for ($j = $N - 1; $j > $col; $j--)
        {
            $tmp -= $x[$j] * $A[$col][$j];
        }
        $x[$col] = $tmp / $A[$col][$col];
    }
    return $x;
}

function test_gauss()
{
    $a = array(
        array(1.00, 0.00, 0.00,  0.00,  0.00, 0.00),
        array(1.00, 0.63, 0.39,  0.25,  0.16, 0.10),
        array(1.00, 1.26, 1.58,  1.98,  2.49, 3.13),
        array(1.00, 1.88, 3.55,  6.70, 12.62, 23.80),
        array(1.00, 2.51, 6.32, 15.88, 39.90, 100.28),
        array(1.00, 3.14, 9.87, 31.01, 97.41, 306.02)
    );
    $b = array( -0.01, 0.61, 0.91, 0.99, 0.60, 0.02 );

    $x = gauss_eliminate($a, $b, 6);

    ksort($x);
    print_r($x);
}

test_gauss();

Answer 2

You could solve this as a system of simultaneous equations using Guaussian elimination.

The number of midnight crossings between adjacent stations are your variables, and your co-efficients will just be 1 for every pair of stations included in a segment and 0 otherwise.

Take the second example:

0->2: 1

1->3: 1

2->3: 0

Think of 0->1 as variable a, 1->2 as variable b and 2->3 as variable c, then you can rewrite as:

a + b = 1

b + c = 1

c = 0

or in matrix form as

[ 1 1 0 ] [ a ]   [ 1 ]
[ 0 1 1 ] [ b ] = [ 1 ]
[ 0 0 1 ] [ c ]   [ 0 ]

(Number of columns in matrix should equal number of pairs of adjacent stations, number of rows is number of equations you have). Solve for a, b, c to find the number of midnight crossings between each pair of stations.

You have an additional constraint that the values are non-negative, so for example if a + b = 0 you know that both a and b are zero because it's not possible for one to be positive and the other negative. So you can just add a = 0 and b = 0 as two more equations to your system.