Advent of PBT 2021 - Day 24 - Solution
Tags: challenge, testing, webdev, javascript
Published: 2021-12-24 07:54:02

---
title: Advent of PBT 2021 - Day 24 - Solution
published: true
description: Advent of Property Based Testing 2021 - Day 24 - Solution
tags: challenge,testing,webdev,javascript
//cover_image: https://direct_url_to_image.jpg
---

Our algorithm was: **christmasFactorySchedule**.
[Go to the subject itself for more details](https://dev.to/dubzzz/advent-of-pbt-2021-day-24-2377)

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`:

```ts
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:

```ts
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:

```ts
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:

```ts
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:

```ts
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"](https://dev.to/dubzzz/advent-of-pbt-2021-13ee) to see topics covered during the other days and their solutions.

More about this serie on [@ndubien](https://twitter.com/ndubien) or with the hashtag [#AdventOfPBT](https://twitter.com/search?q=%23AdventOfPBT).