DEV Community

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

Advent of PBT 2021 - Day 24

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[];
Enter fullscreen mode Exit fullscreen mode

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 }
  ]);
});
Enter fullscreen mode Exit fullscreen mode

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)