## DEV Community

Nicolas DUBIEN

Posted on • Updated on

# Advent of PBT 2021 - Day 19 - Solution

Our algorithm was: metroRoute.
Go to the subject itself for more details

CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-19-solution-t470u?file=/src/index.spec.ts&previewwindow=tests

As for many of the properties we have defined so far in this Advent calendar, the idea will be to build some inputs we know a lot about. In other words we will not build fully random ones that would possibly require us to re-implement part of the logic.

For this algorithm we will need two main builders:

• one for maps of metro with known connections between two stations
• one for maps of the metro with a clear absence of path between two stations

For the first of the two the idea is to generate two entities:

• a route of stations: first station will be the departure, last one will be the destination and the route itself is one of the known set of tracks to go from departure to destination
• a set of other tracks: possibly including some that will be used to go more quickly from departure to destination

Written with fast-check:

``````function orientedGraphArbitrary() {
return fc
.record({
// tracks that will compose the known path (starting at node=0)
knownPathExcludingStart: fc.set(
fc.record({ node: fc.integer({ min: 1 }), length: fc.nat() }),
{ compare: (na, nb) => na.node === nb.node }
),
// some more tracks that will compose our graph
extraTracks: fc.array(
fc.record({ from: fc.nat(), to: fc.nat(), length: fc.nat() })
)
})
.chain(({ knownPathExcludingStart, extraTracks }) => {
const departure = 0;
const knownPath = [
departure,
...knownPathExcludingStart.map((n) => n.node)
];
const knownPathTracks = knownPathExcludingStart.map((n, index) => ({
from: index !== 0 ? knownPathExcludingStart[index - 1].node : departure,
to: n.node,
length: n.length
}));
const allTracks = [...knownPathTracks, ...extraTracks];
return fc.record({
knownPath: fc.constant(knownPath),
knownPathTracks: fc.constant(knownPathTracks),
tracks: fc.shuffledSubarray(allTracks, { minLength: allTracks.length })
});
});
}
``````

Our second builder will be responsible to build maps not having routes leading from departure to destination. In order to do so we will generate the following entries:

• a set of tracks going from stations in [0, 9] to stations in [0, 9]
• a set of tracks going from stations in [10, 19] to stations in [10, 19]
• a set of tracks going from stations in [10, 19] to stations in [0, 9]
• departure will be 0
• destination will be 19

So we have no route going from departure to destination.

Written with fast-check:

``````function orientedGraphNoWayArbitrary() {
return fc
.record({
// We consider start = 0 and end = 19.
// We delimit two zones:
// - start zone contains stations 0 to 9 (included)
// - end zone contains stations 10 to 19 (included)
tracksStartZone: fc.array(
fc.record({
from: fc.integer({ min: 0, max: 9 }),
to: fc.integer({ min: 0, max: 9 }),
length: fc.nat()
})
),
tracksEndZone: fc.array(
fc.record({
from: fc.integer({ min: 10, max: 19 }),
to: fc.integer({ min: 10, max: 19 }),
length: fc.nat()
})
),
tracksEndToStart: fc.array(
fc.record({
from: fc.integer({ min: 10, max: 19 }),
to: fc.integer({ min: 0, max: 9 }),
length: fc.nat()
})
)
})
.map((config) => ({
departure: 0,
destination: 19,
tracks: [
...config.tracksStartZone,
...config.tracksEndZone,
...config.tracksEndToStart
]
}));
}
``````

## Property 1: should build a path starting by the requested departure whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the first track starting at departure

Written with fast-check:

``````it("should build a path starting by the requested departure whenever a path from start to end exists", () => {
fc.assert(
fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
// Arrange
const departure = knownPath[0];
const destination = knownPath[knownPath.length - 1];

// Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
if (departure === destination) expect(shortestPath).toEqual([]);
else expect(shortestPath![0].from).toBe(departure);
})
);
});
``````

## Property 2: should build a path ending by the requested destination whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the end track ending at destination

Written with fast-check:

``````it("should build a path ending by the requested destination whenever a path from start to end exists", () => {
fc.assert(
fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
// Arrange
const departure = knownPath[0];
const destination = knownPath[knownPath.length - 1];

// Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
if (departure === destination) expect(shortestPath).toEqual([]);
else expect(shortestPath![shortestPath!.length - 1].to).toBe(destination);
})
);
});
``````

## Property 3: should build an ordered path of tracks whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the start of each track connected to the end of the previous one

Written with fast-check:

``````it("should build an ordered path of tracks whenever a path from start to end exists", () => {
fc.assert(
fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
// Arrange
const departure = knownPath[0];
const destination = knownPath[knownPath.length - 1];

// Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
for (let index = 1; index < shortestPath!.length; ++index) {
expect(shortestPath![index].from).toBe(shortestPath![index - 1].to);
}
})
);
});
``````

## Property 4: should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with only tracks declared in the set of tracks

Written with fast-check:

``````it("should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists", () => {
fc.assert(
fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
// Arrange
const departure = knownPath[0];
const destination = knownPath[knownPath.length - 1];

// Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
for (const edge of shortestPath!) {
expect(shortestPath).toContainEqual(edge);
}
})
);
});
``````

## Property 5: should be able to find a path shorther or equal to the one we come up with

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with length shorter or equal to the known route

Written with fast-check:

``````it("should be able to find a path shorther or equal to the one we come up with", () => {
fc.assert(
fc.property(
orientedGraphArbitrary(),
({ knownPath, knownPathTracks, tracks }) => {
// Arrange
const departure = knownPath[0];
const destination = knownPath[knownPath.length - 1];

// Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
const distanceKnownPath = knownPathTracks.reduce((acc, e) => acc + e.length, 0);
const distanceShortestPath = shortestPath!.reduce((acc, e) => acc + e.length, 0);
expect(distanceShortestPath).toBeLessThanOrEqual(distanceKnownPath);
}
)
);
});
``````

## Property 6: should not return any path whenever there is no way going from start to end

for map of the metro and two stations "departure" and "destination" known not to be connected
it should not find any track going from "departure" to "destination"

Written with fast-check:

``````it("should not return any path whenever there is no way going from start to end", () => {
fc.assert(
fc.property(
orientedGraphNoWayArbitrary(),
({ departure, destination, tracks }) => {
// Arrange / Act
const shortestPath = metroRoute(departure, destination, tracks);

// Assert
expect(shortestPath).toBe(undefined);
}
)
);
});
``````

Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.