Our algorithm was: racePodium.
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-15-solution-e328q?file=/src/index.spec.ts&previewwindow=tests
Property 1: should predict the right podium
for any candidates
it should predict the right podium
Written with fast-check:
it("should predict the right podium", () => {
fc.assert(
fc.property(
fc.array(fc.nat(), { minLength: 25, maxLength: 25 }),
(speeds) => {
// Arrange
const compareParticipants = (pa: number, pb: number) => {
if (speeds[pa] !== speeds[pb]) return speeds[pb] - speeds[pa];
else return pa - pb;
};
const runRace = (
...participants: RaceParticipants
): RaceParticipants => {
return participants.sort(compareParticipants);
};
// Act
const podium = racePodium(runRace);
// Assert
const rankedParticipants = [...Array(25)]
.map((_, i) => i)
.sort(compareParticipants);
const expectedPodium = rankedParticipants.slice(0, 3);
expect(podium).toEqual(expectedPodium);
}
)
);
});
While this property ensures that we always compute the right podium it does not make sure that we do it in an efficient way as it never checks if we make unneeded races.
Property 2: should insert all the selected tabs before the move position
for any candidates
it should at most do 7 races
Written with fast-check:
it("should never do more than 7 races", () => {
fc.assert(
fc.property(
fc.array(fc.nat(), { minLength: 25, maxLength: 25 }),
(speeds) => {
// Arrange
const compareParticipants = (pa: number, pb: number) => {
if (speeds[pa] !== speeds[pb]) return speeds[pb] - speeds[pa];
else return pa - pb;
};
const runRace = jest.fn(
(...participants: RaceParticipants): RaceParticipants => {
return participants.sort(compareParticipants);
}
);
// Act
racePodium(runRace);
// Assert
expect(runRace.mock.calls.length).toBeLessThanOrEqual(7);
}
)
);
});
One of the key characteristics of this problem is that we have a known upper bound for the number of races. Requesting for more than 7 races means that we planned our races in a sub-optimal way leading for extra races to be executed.
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)