Minimising the number of bus changes in a matrix

[ 42,  45,  47,  x,  x] -> stop1 to stop2
[ 45,  47,  42,  88,  x] -> stop2 to stop3
[ 21,  77,  42,  x,  x] -> stop3 to stop4
[ 22,  47,  42,  88,  x] -> stop4 to stop5
[ 23,  47,  42,  x,  x] -> stop5 to stop6
[ 24,  47,  42,  8,  91] -> stop6 to stop7
[ 25,  13,  42,  3,  84] -> stop7 to stop8
[ 26,  10,  11,  4,  54] -> stop8 to stop9
[ 27,  9,  8,  88,   71] -> stop9 to stop10

x is there just for formatting. The first row means that there are only three buses from stop1 to stop2(42, 45, 47).

I have this matrix like structure where each row represents the buses going from one stop to another. I need to minimize the number of bus changes a person has to make to go from stop1 to stop10.

For example one of the output should be 42, 42, 42, 42, 42, 42, 42, 26, 27 another can be 42, 42, 42, 42, 42, 42, 42, 10, 9. If the number of changes is more than three I can discard the result.

What's the most optimal way to achieve this as brute forcing through it is pretty unefficient right now?

Solution

You could go through the array once, and keep a set of buses that are common to the visited stops. As soon as none such buses can be found, take the previous set, choose one bus from it, and fill the result with that bus for that many stops.

Then put all buses at the current stop in the set, and repeat the operation for the subsequent stops, ...etc.

Here is the algorithm coded in ES6 JavaScript. It uses a Set to allow constant-time access to the items (buses) it stores.

// Helper function: given a reduced set of buses, and a count,
//   add one of those buses as the bus to take during that many stops
function addToResult(common, count, result) {
    let bus = common.values().next().value; // pick any available bus
    while (count > 0) {
        result.push(bus);
        count--;
    }
}

// Main algorithm
function getBusRide(stops) {
    if (stops.length === 0) return [];

    let result = [],
        count = 0,
        common;
    for (let buses of stops) {
        if (count == 0) { // First iteration only
            common = new Set(buses); // all buses are candidate
            count = 1;
        } else {
            let keep = new Set();
            for (let bus of buses) {
                // Only keep buses as candidate when they 
                //     are still served here
                if (common.has(bus)) keep.add(bus);
            }
            if (keep.size == 0) { // Need to change bus
                addToResult(common, count, result);
                count = 0;
                keep = new Set(buses); // all buses are candidate
            }
            common = keep;
            count++;
        }
    }
    addToResult(common, count, result);
    return result;
}

// Sample input
const stops = [
    [ 42,  45,  47],
    [ 45,  47,  42,  88],
    [ 21,  77,  42],
    [ 22,  47,  42,  88],
    [ 23,  47,  42],
    [ 24,  47,  42,  8,  91],
    [ 25,  13,  42,  3,  84],
    [ 26,  10,  11,  4,  54],
    [ 27,  9,  8,  88,   71]
];

// Apply the algorithm
console.log(getBusRide(stops));

.as-console-wrapper { max-height: 100% !important; top: 0; }

This algorithm runs in O(n) where n is the total number of values in the input, so in the example n = 37.