Advent of PBT 2021 - Day 24 - Solution

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.