Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples
Our algorithm today is: christmasFactorySchedule.
It comes with the following documentation and prototype:
export type Task = {
taskId: number;
estimatedTime: number;
dependsOnTasks: number[];
};
export type ScheduledTask = {
taskId: number;
start: number;
finish: number;
};
/**
* Christmas is coming! Santa Claus and his elves have to produce all the presents before the D-day.
* In order to be as efficient as possible they want to schedule and parallelize as many tasks as possible.
*
* So they come up with a precise list of all the tasks including their dependencies and the time they will take.
* Now we have to suggest the ideal timetable to achieve this goal.
*
* @param tasks - Define the tasks to achieve.
* Tasks should not define circular dependencies, one task cannot be dependant on itself (even indirectly).
*
* The following implementation is based on the one suggested at https://algs4.cs.princeton.edu/44sp/CPM.java.html.
* It solves the "parallel precedence-constrained job scheduling problem".
*/
declare function christmasFactorySchedule(tasks: Task[]): ScheduledTask[];
We already wrote some examples based tests for it:
it("should fully parallelize all the tasks whenever possible", () => {
// Arrange
const tasks: Task[] = [
{ taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
{ taskId: 1, estimatedTime: 5, dependsOnTasks: [] },
{ taskId: 2, estimatedTime: 3, dependsOnTasks: [] },
{ taskId: 3, estimatedTime: 12, dependsOnTasks: [] }
];
// Act
const scheduledTasks = christmasFactorySchedule(tasks);
// Assert
expect(scheduledTasks).toEqual([
{ taskId: 0, start: 0, finish: 10 },
{ taskId: 1, start: 0, finish: 5 },
{ taskId: 2, start: 0, finish: 3 },
{ taskId: 3, start: 0, finish: 12 }
]);
});
it("should queue all tasks whenever no parallel runs are allowed", () => {
// Arrange
const tasks: Task[] = [
{ taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
{ taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
{ taskId: 2, estimatedTime: 3, dependsOnTasks: [3] },
{ taskId: 3, estimatedTime: 12, dependsOnTasks: [0] }
];
// Act
const scheduledTasks = christmasFactorySchedule(tasks);
// Assert
expect(scheduledTasks).toEqual([
{ taskId: 0, start: 0, finish: 10 },
{ taskId: 1, start: 25, finish: 30 },
{ taskId: 2, start: 22, finish: 25 },
{ taskId: 3, start: 10, finish: 22 }
]);
});
it("should be able to handle tasks depending on the completion of many", () => {
// Arrange
const tasks: Task[] = [
{ taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
{ taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
{ taskId: 2, estimatedTime: 3, dependsOnTasks: [0, 3] },
{ taskId: 3, estimatedTime: 12, dependsOnTasks: [] }
];
// Act
const scheduledTasks = christmasFactorySchedule(tasks);
// Assert
expect(scheduledTasks).toEqual([
{ taskId: 0, start: 0, finish: 10 },
{ taskId: 1, start: 15, finish: 20 },
{ taskId: 2, start: 12, finish: 15 },
{ taskId: 3, start: 0, finish: 12 }
]);
});
it("should be able to handle complex tasks with many dependencies", () => {
// Arrange
const tasks: Task[] = [
{ taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
{ taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
{ taskId: 2, estimatedTime: 3, dependsOnTasks: [0, 3] },
{ taskId: 3, estimatedTime: 12, dependsOnTasks: [4] },
{ taskId: 4, estimatedTime: 1, dependsOnTasks: [] },
{ taskId: 5, estimatedTime: 6, dependsOnTasks: [0] },
{ taskId: 6, estimatedTime: 8, dependsOnTasks: [2, 5] },
{ taskId: 7, estimatedTime: 9, dependsOnTasks: [1, 6] }
];
// Act
const scheduledTasks = christmasFactorySchedule(tasks);
// Assert
expect(scheduledTasks).toEqual([
{ taskId: 0, start: 0, finish: 10 },
{ taskId: 1, start: 16, finish: 21 },
{ taskId: 2, start: 13, finish: 16 },
{ taskId: 3, start: 1, finish: 13 },
{ taskId: 4, start: 0, finish: 1 },
{ taskId: 5, start: 10, finish: 16 },
{ taskId: 6, start: 16, finish: 24 },
{ taskId: 7, start: 24, finish: 33 }
]);
});
How would you cover it with Property Based Tests?
In order to ease your task we provide you with an already setup CodeSandbox, with examples based tests already written and a possible implementation of the algorithm: https://codesandbox.io/s/advent-of-pbt-day-24-6y13g?file=/src/index.spec.ts&previewwindow=tests
You wanna see the solution? Here is the set of properties I came with to cover today's algorithm: https://dev.to/dubzzz/advent-of-pbt-2021-day-24-solution-53e
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)