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.
More about this serie on @ndubien or with the hashtag #AdventOfPBT.
Top comments (0)