Our algorithm was: christmasFactorySchedule.
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-24-solution-68w81?file=/src/index.spec.ts&previewwindow=tests
Today, we will just generate the inputs requested by the algorithm. Actually there is something cool regarding this algorithm: computing the result is complex, but checking it is simple.
So we will just generate tasks being dependent from each others without cycles and ask the scheduler what's the best option for us. Then we just have to confirm the schedule is following our constraints.
But in order to generate our tasks we need to be careful as generating cycles could be easy (and trying to detect them would add some unwanted complexity in the tests).
Here is the implementation I came with for tasksArbitrary:
function tasksArbitrary(): fc.Arbitrary<Task[]> {
return fc
.tuple(
tasksLayerArbitrary(0), // tasks with ids in 0 to 9, without any dependencies
tasksLayerArbitrary(1), // tasks with ids in 10 to 19, with possible dependencies onto 0 to 9
tasksLayerArbitrary(2), // tasks with ids in 20 to 29, with possible dependencies onto 0 to 19
tasksLayerArbitrary(3) // tasks with ids in 30 to 39, with possible dependencies onto 0 to 29
)
.map((layers: Task[][]): Task[] => {
// Merge all the layers together
const requestedTasks = layers.flat();
// List all the ids of tasks used as dependencies of others
const tasksIdDependencies = [
...new Set(requestedTasks.flatMap((t) => t.dependsOnTasks))
];
// Create missing tasks (for dependencies)
const missingTasks = tasksIdDependencies
.filter(
(taskId) =>
requestedTasks.find((t) => t.taskId === taskId) === undefined
)
.map((taskId) => ({ taskId, estimatedTime: 0, dependsOnTasks: [] }));
// Return the tasks
return [...requestedTasks, ...missingTasks];
});
}
function tasksLayerArbitrary(layer: number): fc.Arbitrary<Task[]> {
return fc.set(
fc.record<Task>({
taskId: fc.integer({ min: layer * 10, max: layer * 10 + 9 }),
estimatedTime: fc.nat(),
// Curret layer can have dependencies onto any other previous layer
dependsOnTasks:
layer !== 0
? fc.set(fc.integer({ min: 0, max: (layer - 1) * 10 + 9 }))
: fc.constant([])
}),
{ compare: (taskA, taskB) => taskA.taskId === taskB.taskId }
);
}
Property 1: should keep all the tasks for the scheduled plan
for any valid set of tasks
it should compute a schedule including all the tasks
Written with fast-check:
it("should keep all the tasks for the scheduled plan", () => {
fc.assert(
fc.property(tasksArbitrary(), (tasks) => {
// Arrange / Act
const schedule = christmasFactorySchedule(tasks);
// Assert
expect(schedule).toHaveLength(tasks.length);
const tasksFromSchedule = new Set(schedule.map((t) => t.taskId));
const tasksFromRequest = new Set(tasks.map((t) => t.taskId));
expect(tasksFromSchedule).toEqual(tasksFromRequest);
})
);
});
Property 2: should not extend or reduce the duration of tasks
for any valid set of tasks
it should compute a schedule and keep duration untouched
Written with fast-check:
it("should not extend or reduce the duration of tasks", () => {
fc.assert(
fc.property(tasksArbitrary(), (tasks) => {
// Arrange / Act
const schedule = christmasFactorySchedule(tasks);
// Assert
for (const scheduledTask of schedule) {
const task = tasks.find((t) => t.taskId === scheduledTask.taskId);
expect(scheduledTask.finish - scheduledTask.start).toBe(
task.estimatedTime
);
}
})
);
});
Property 3: should not start any task before all its dependencies ended
for any valid set of tasks
it should compute a schedule following the requested dependencies between tasks
Written with fast-check:
it("should not start any task before all its dependencies ended", () => {
fc.assert(
fc.property(tasksArbitrary(), (tasks) => {
// Arrange / Act
const schedule = christmasFactorySchedule(tasks);
// Assert
for (const scheduledTask of schedule) {
const dependencies = tasks.find(
(t) => t.taskId === scheduledTask.taskId
)!.dependsOnTasks;
for (const depTaskId of dependencies) {
const depScheduledTask = schedule.find((s) => s.taskId === depTaskId);
expect(scheduledTask.start).toBeGreaterThanOrEqual(
depScheduledTask.finish
);
}
}
})
);
});
Property 4: should start tasks as soon as possible
for any valid set of tasks
it should compute the most optimized schedule
Written with fast-check:
it("should start tasks as soon as possible", () => {
fc.assert(
fc.property(tasksArbitrary(), (tasks) => {
// Arrange / Act
const schedule = christmasFactorySchedule(tasks);
// Assert
for (const scheduledTask of schedule) {
const dependencies = tasks.find(
(t) => t.taskId === scheduledTask.taskId
)!.dependsOnTasks;
const finishTimeDependencies = dependencies.map((depTaskId) => {
const depScheduledTask = schedule.find((s) => s.taskId === depTaskId);
return depScheduledTask.finish;
});
const expectedStart =
finishTimeDependencies.length !== 0
? Math.max(...finishTimeDependencies)
: 0;
expect(scheduledTask.start).toBe(expectedStart);
}
})
);
});
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)