DEV Community: Nicolas DUBIEN

Integrate Jest and fast-check together

Nicolas DUBIEN — Thu, 20 Oct 2022 18:57:47 +0000

A few days ago, Jest released a new feature making users able to seed their runs. While not fully leveraged within Jest itself, @fast-check/jest is already using it.

It makes @fast-check/jest, the best option to integrate Jest and fast-check, as it provides an abstraction over both to ease their mutual integration.

Starting at version 1.3.0, here is how you would use it to start your new project:

npm install --save-dev jest @fast-check/jest

Then you just have not to forget to put the --show-seed option every time you call Jest to make sure Jest will always print the seed for you.

--  "test": "jest --verbose --coverage",
++  "test": "jest --show-seed --verbose --coverage",

Options --verbose and --coverage are just examples of possible parameters you may already pass to Jest

At that point everything is ready, have fun with fast-check and Jest and happy testing! 🎉

import { testProp, fc } from '@fast-check/jest';

// for all a, b, c strings
// b is a substring of a + b + c
testProp('should detect the substring', [fc.string(), fc.string(), fc.string()], (a, b, c) => {
  return (a + b + c).includes(b);
});

Advent of PBT 2021 - Day 24 - Solution

Nicolas DUBIEN — Fri, 24 Dec 2021 07:54:02 +0000

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.

Advent of PBT 2021 - Day 24

Nicolas DUBIEN — Fri, 24 Dec 2021 07:53:33 +0000

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.

Advent of PBT 2021 - Day 23 - Solution

Nicolas DUBIEN — Thu, 23 Dec 2021 08:11:07 +0000

Our algorithm was: wishListsDiffer.
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-23-solution-5evnm?file=/src/index.spec.ts&previewwindow=tests

Property 1: should be able to rebuild previous year given only the diff

for any wish lists:

one for previous year

one for current year

it should be able to rebuild the previous year's wish list just based on the diff

Indeed given a diff like:

=== Cars
+++ Buses
=== Trains
+++ Boats
--- Planes

It is pretty easy to find back the wish list used for the previous year as it corresponds to any line starting by --- or ===.

In terms of code, it can be done with:

function previousYearFromDiff(diff: string): string {
  return diff
    .split("\n")
    .filter((line) => line.startsWith("--- ") || line.startsWith("=== "))
    .map((line) => line.substring(4))
    .join("\n");
}

We also need a way to generate wish lists with fast-check. Here is a way to write such arbitrary:

function stringSingleLine() {
  return fc.stringOf(fc.fullUnicode().filter((c) => c !== "\n"));
}
function wishListArbitrary() {
  return fc.array(stringSingleLine()).map((lines) => lines.join("\n"));
}

Now everything is ready, we can go back to our property:

for any wish lists:

one for previous year

one for current year

it should be able to rebuild the previous year's wish list just based on the diff

Written with fast-check:

it("should be able to rebuild previous year given only the diff", () => {
  fc.assert(
    fc.property(
      wishListArbitrary(),
      wishListArbitrary(),
      (previousYear, currentYear) => {
        // Arrange / Act
        const computedDiff = wishListsDiffer(previousYear, currentYear);

        // Assert
        expect(previousYearFromDiff(computedDiff)).toEqual(previousYear);
      }
    )
  );
});

Property 2: should be able to rebuild current year given only the diff

for any wish lists:

one for previous year

one for current year

it should be able to rebuild the current year's wish list just based on the diff

Written with fast-check:

it("should be able to rebuild current year given only the diff", () => {
  fc.assert(
    fc.property(
      wishListArbitrary(),
      wishListArbitrary(),
      (previousYear, currentYear) => {
        // Arrange / Act
        const computedDiff = wishListsDiffer(previousYear, currentYear);

        // Assert
        expect(currentYearFromDiff(computedDiff)).toEqual(currentYear);
      }
    )
  );
});

Property 3: should compute the diff having the maximal number of unchanged lines

for any wish lists:

one for previous year

one for current year

extracted from a known diff
it should compute a diff at least as good as the original one

In order to write down this property with fast-check we first of all need an arbitrary to generate some diffs:

function diffArbitrary() {
  return fc
    .array(
      fc
        .record({
          type: fc.constantFrom("+++", "---", "==="),
          content: stringSingleLine()
        })
        .map(({ type, content }) => `${type} ${content}`),
      { minLength: 1 }
    )
    .map((lines) => lines.join("\n"));
}

Now that we have such arbitrary we have to define "at least as good as the original one" in the code. In the case of our differ the target is to maximize the number of lines marked with "===". In other words, make the number of unchanged lines as large as possible. So we will need an helper to count them.

function countUnchangedLines(diff: string): number {
  return diff.split("\n").filter((line) => line.startsWith("=== ")).length;
}

Now let's move back to our property:

for any wish lists:

one for previous year

one for current year

extracted from a known diff
it should compute a diff at least as good as the original one

Written with fast-check:

it("should compute the diff having the maximal number of unchanged lines", () => {
  fc.assert(
    fc.property(diffArbitrary(), (diff) => {
      // Arrange
      const previousYear = previousYearFromDiff(diff);
      const currentYear = currentYearFromDiff(diff);

      // Act
      const computedDiff = wishListsDiffer(previousYear, currentYear);

      // Assert
      expect(countUnchangedLines(computedDiff)).toBeGreaterThanOrEqual(
        countUnchangedLines(diff)
      );
    })
  );
});

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.

Advent of PBT 2021 - Day 23

Nicolas DUBIEN — Thu, 23 Dec 2021 08:10:51 +0000

Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples

Our algorithm today is: wishListsDiffer.
It comes with the following documentation and prototype:

/**
 * Each year, Santa receives wish lists coming from everywhere.
 *
 * Lists are ordered starting by the most important present to the last
 * important one. Santa does not always offer the most important one.
 * From time to time he wants to wait one more year to check if the
 * present stays in the top.
 *
 * Each year, Santa manually performs a diff of the list with
 * the one of the year before. Based on this diff he makes his choice.
 *
 * You can see the diff manually computed by Santa as an usual git diff
 * between two strings including many lines.
 *
 * Let's take the example:
 *
 *   Year N:
 *     Cars
 *     Trains
 *     Planes
 *
 *   Year N+1:
 *     Cars
 *     Buses
 *     Trains
 *     Boats
 *
 *   Diff of Santa:
 *     === Cars
 *     +++ Buses
 *     === Trains
 *     +++ Boats
 *     --- Planes
 *
 * @param before - String representing the list of presents (before)
 * @param after - String representing the list of presents (after)
 */
declare function wishListsDiffer(before: string, after: string): string;

We already wrote some examples based tests for it:

it("should compute the appropriate diff", () => {
  // Arrange
  const previousYear = "Cars\nTrains\nPlanes";
  const currentYear = "Cars\nBuses\nTrains\nBoats";

  // Act
  const diff = wishListsDiffer(previousYear, currentYear);

  // Assert
  // prettier-ignore
  expect(diff).toEqual(
    "=== Cars\n" +
    "+++ Buses\n" +
    "=== Trains\n" +
    "+++ Boats\n" +
    "--- Planes"
  );
});

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-23-q1468?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-23-solution-4lg4

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.

Advent of PBT 2021 - Day 22 - Solution

Nicolas DUBIEN — Wed, 22 Dec 2021 07:20:02 +0000

Our algorithm was: spyOnSanta.
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-22-solution-j3lb9?file=/src/index.spec.ts&previewwindow=tests

For this algorithm we will more or less always assert the 4 same things:

Selection must have between 1 and 3 elves
Selection must be made of indexes corresponding to known elves
Selection must not repeat elves
Selection must reach the wall height, not more not less

Written with code:

function assertElves(
  elves: number[],
  selectedElves: number[],
  wallHeight: number
): void {
  // Selection must have between 1 and 3 elves
  expect(selectedElves.length).toBeGreaterThanOrEqual(1);
  expect(selectedElves.length).toBeLessThanOrEqual(3);
  // Selection must be made of indexes corresponding to known elves
  for (const selected of selectedElves) {
    expect(elves).toHaveProperty(String(selected));
  }
  // Selection must not repeat elves
  expect(selectedElves).toHaveLength(new Set(selectedElves).size);
  // Selection must reach the wall height, not more not less
  const selectionHeight = selectedElves
    .map((i) => elves[i])
    .reduce((a, b) => a + b);
  expect(selectionHeight).toBe(wallHeight);
}

Each of our properties will re-use this shared assertion. The properties today will mostly focus on "how to generate the different situations we might face with this algorithm?". Then anytime we expect an answer with some elves being selected we will assert that the selection fulfilled the requirements. We could have spread each assertion into a dedicated property and multiply by 4 the number of properties but we preferred a more synthetic approach for today.

Property 1: should select some elves whenever there is a solution with one elf

for any wallHeight and elves
such as there is a combination of one elf i such as height(elf(i)) = wallHeight
it should find a combination of elves

Written with fast-check:

it("should select some elves whenever there is a solution with one elf", () => {
  fc.assert(
    fc.property(
      fc.array(fc.integer({ min: 1 }), { minLength: 1 }),
      fc.nat(),
      (elves, modElf1) => {
        // Arrange
        const indexElf1 = modElf1 % elves.length;
        const wallHeight = elves[indexElf1];

        // Act
        const selectedElves = spyOnSanta(elves, wallHeight);

        // Assert
        expect(selectedElves).not.toBe(undefined);
        assertElves(elves, selectedElves!, wallHeight);
      }
    )
  );
});

Property 2: should select some elves whenever there is a solution with two elves

for any wallHeight and elves
such as there is a combination of two elves i and j such as height(elf(i)) + height(elf(j)) = wallHeight
it should find a combination of elves

Written with fast-check:

it("should select some elves whenever there is a solution with two elves", () => {
  fc.assert(
    fc.property(
      fc.array(fc.integer({ min: 1 }), { minLength: 2 }),
      fc.nat(),
      fc.nat(),
      (elves, modElf1, modElf2) => {
        // Arrange
        const indexElf1 = modElf1 % elves.length;
        const indexElf2 = modElf2 % elves.length;
        fc.pre(indexElf1 !== indexElf2);
        const wallHeight = elves[indexElf1] + elves[indexElf2];

        // Act
        const selectedElves = spyOnSanta(elves, wallHeight);

        // Assert
        expect(selectedElves).not.toBe(undefined);
        assertElves(elves, selectedElves!, wallHeight);
      }
    )
  );
});

Property 3: should select some elves whenever there is a solution with three elves

for any wallHeight and elves
such as there is a combination of two elves i, j and k such as height(elf(i)) + height(elf(j)) + height(elf(k)) = wallHeight
it should find a combination of elves

Written with fast-check:

it("should select some elves whenever there is a solution with three elves", () => {
  fc.assert(
    fc.property(
      fc.array(fc.integer({ min: 1 }), { minLength: 3 }),
      fc.nat(),
      fc.nat(),
      fc.nat(),
      (elves, modElf1, modElf2, modElf3) => {
        // Arrange
        const indexElf1 = modElf1 % elves.length;
        const indexElf2 = modElf2 % elves.length;
        const indexElf3 = modElf3 % elves.length;
        fc.pre(indexElf1 !== indexElf2);
        fc.pre(indexElf1 !== indexElf3);
        fc.pre(indexElf2 !== indexElf3);
        const wallHeight =
          elves[indexElf1] + elves[indexElf2] + elves[indexElf3];

        // Act
        const selectedElves = spyOnSanta(elves, wallHeight);

        // Assert
        expect(selectedElves).not.toBe(undefined);
        assertElves(elves, selectedElves!, wallHeight);
      }
    )
  );
});

Property 4: should either propose a valid solution or nothing

for any wallHeight and elves
it should either find a valid combination of elves or nothing

Written with fast-check:

it("should either propose a valid solution or nothing", () => {
  fc.assert(
    fc.property(
      fc.array(fc.integer({ min: 1 })),
      fc.nat(),
      (elves, wallHeight) => {
        // Arrange / Act
        const selectedElves = spyOnSanta(elves, wallHeight);

        // Assert
        if (selectedElves !== undefined) {
          assertElves(elves, selectedElves!, wallHeight);
        }
      }
    )
  );
});

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.

Advent of PBT 2021 - Day 22

Nicolas DUBIEN — Wed, 22 Dec 2021 07:19:11 +0000

Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples

Our algorithm today is: spyOnSanta.
It comes with the following documentation and prototype:

/**
 * Santa' elves often want to know in advance what will be the plan
 * of Santa for the upcoming Christmas. As a consequence, they try
 * to spy on Santa by looking on top of a wall separating them from
 * him when Santa starts receiving letters.
 *
 * They usually try to mount on each others shoulders to have the exact
 * same height as the whole. But even if they tried many years in a raw
 * they have only succeeding with 1, 2 or 3 eleves.
 *
 * Could you help them in their mission?
 * In other words: could you return one, two or three elves (by index)
 * such as:
 *   height(elves[i]) = height(wall)
 * OR
 *   height(elves[i]) + height(elves[j]) = height(wall)
 * OR
 *   height(elves[i]) + height(elves[j]) + height(elves[k]) = height(wall)
 *
 * @param elvesHeight - Strictly positive integers representing
 *                      the heights of our elves
 * @param wallHeight - The height of the wall
 *
 * @returns
 * The one, two or three selected elves if there is a solution,
 * undefined otherwise.
 */
declare function spyOnSanta(
  elvesHeight: number[],
  wallHeight: number
): number[] | undefined;

We already wrote some examples based tests for it:

it("should find combinations including one elf", () => {
  // Arrange
  const elves = [1, 3, 6, 11, 13];

  // Act
  const selectedElves = spyOnSanta(elves, 11);
  // 11 = 11

  // Assert
  expect(selectedElves).toEqual([3]);
});

it("should find combinations including two elves", () => {
  // Arrange
  const elves = [1, 3, 6, 11, 13];

  // Act
  const selectedElves = spyOnSanta(elves, 4);
  // 4 = 1 + 3

  // Assert
  expect(selectedElves).toEqual([0, 1]);
});

it("should find combinations including three elves", () => {
  // Arrange
  const elves = [1, 3, 6, 11, 13];

  // Act
  const selectedElves = spyOnSanta(elves, 10);
  // 10 = 1 + 3 + 6

  // Assert
  expect(selectedElves).toEqual([0, 1, 2]);
});

it("should not find combinations including four elves", () => {
  // Arrange
  const elves = [1, 1, 3, 6, 11, 13];

  // Act
  const selectedElves = spyOnSanta(elves, 33);
  // 33 = 3 + 6 + 11 + 13

  // Assert
  expect(selectedElves).toBe(undefined);
});

it("should be able to deal with elves having the same height", () => {
  // Arrange
  const elves = [1, 1, 5, 10, 15];

  // Act
  const selectedElves = spyOnSanta(elves, 12);
  // 12 = 1 + 1 + 10

  // Assert
  expect(selectedElves).toEqual([0, 1, 3]);
});

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-22-7zgcs?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:

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.

Advent of PBT 2021 - Day 21 - Solution

Nicolas DUBIEN — Tue, 21 Dec 2021 08:34:54 +0000

Our algorithm was: findPlaceForSanta.
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-21-solution-3usm8?file=/src/index.spec.ts&previewwindow=tests

Property 1: should find a place whenever the map has at least one with the right size

for any market having enough room for santa
it should find a place

In order to be able to write this property down, we first need to find a way to define such market. How would we generate a market with enough room?

Basically the approach I used for this property is the following:

generate the dimensions of the market
given those dimensions, generate a map for the market made of true and false, we will call this map rawMap
given those dimensions, generate a place for Santa, we will call it request
now that we have rawMap and request, we can generate the final map: the same as rawMap except that any cell within request will be set to true (aka available)

We have generated a map for the market with an already known to be eligible place for Santa. We only need to check that the algorithm will always find a place given there is at least one.

Written with fast-check:

it("should find a place whenever the map has at least one with the right size", () => {
  fc.assert(
    fc.property(
      fc
        .record({
          // Size of the map
          mapWidth: fc.nat({ max: 100 }),
          mapHeight: fc.nat({ max: 100 })
        })
        .chain((mapSize) =>
          fc.record({
            // Default map with some holes for available places
            rawMap: mapArbitrary(mapSize),
            // Stand that will be allocated for Santa
            // We will free this room so that it will be available
            request: rectAreaArbitrary(mapSize)
          })
        ),
      ({ rawMap, request }) => {
        // Arrange
        // Allocate some room to Santa so that he will be able
        // to have his stand on the market
        const map: boolean[][] = [];
        for (let y = 0; y !== rawMap.length; ++y) {
          map[y] = [];
          for (let x = 0; x !== rawMap[0].length; ++x) {
            map[y][x] =
              rawMap[y][x] ||
              (request.x.start <= x &&
                x < request.x.end &&
                request.y.start <= y &&
                y < request.y.end);
          }
        }
        const requestedArea = {
          width: request.x.end - request.x.start,
          height: request.y.end - request.y.start
        };

        // Act
        const foundPlace = findPlaceForSanta(map, requestedArea);

        // Assert
        expect(foundPlace).not.toBe(undefined);
      }
    )
  );
});

In order to help us, we also needed those extra arbitraries:

// Build a range with values between 0 (included) and max (included)
// and such as range.start <= range.end
function rangeArbitrary(max: number) {
  return fc
    .tuple(fc.nat({ max }), fc.nat({ max }))
    .map(([v1, v2]) => ({ start: Math.min(v1, v2), end: Math.max(v1, v2) }));
}

// Build a rectangular area within the map
function rectAreaArbitrary(mapSize: { mapWidth: number; mapHeight: number }) {
  return fc.record({
    x: rangeArbitrary(mapSize.mapWidth),
    y: rangeArbitrary(mapSize.mapHeight)
  });
}

// Build a map with randomly defined available/non-available places
function mapArbitrary(mapSize: { mapWidth: number; mapHeight: number }) {
  return fc.array(
    fc.array(fc.boolean(), {
      minLength: mapSize.mapWidth,
      maxLength: mapSize.mapWidth
    }),
    { minLength: mapSize.mapHeight, maxLength: mapSize.mapHeight }
  );
}

Property 2: should either return no place or the start of valid place with enough room

for any market
it should either return no place or the upper-left corner of the place

Written with fast-check:

it("should either return no place or the start of valid place with enough room", () => {
  fc.assert(
    fc.property(
      fc
        .record({
          // Size of the map
          mapWidth: fc.nat({ max: 100 }),
          mapHeight: fc.nat({ max: 100 })
        })
        .chain((mapSize) =>
          fc.record({
            // Default map with some holes for available places
            map: mapArbitrary(mapSize),
            // Size of the stand requested by Santa
            requestedArea: fc.record({
              width: fc.integer({ min: 0, max: mapSize.mapWidth }),
              height: fc.integer({ min: 0, max: mapSize.mapHeight })
            })
          })
        ),
      ({ map, requestedArea }) => {
        // Arrange / Act
        const foundPlace = findPlaceForSanta(map, requestedArea);

        // Assert
        if (foundPlace !== undefined) {
          for (let dy = 0; dy !== requestedArea.height; ++dy) {
            for (let dx = 0; dx !== requestedArea.width; ++dx) {
              expect(map[foundPlace.y + dy][foundPlace.x + dx]).toBe(true);
            }
          }
        }
      }
    )
  );
});

With those two properties we can fully cover the whole algorithm:

property 1 makes sure that we always find a place when there is one
property 2 makes sure we do not lie when we say we found one place

There is also something good to know regarding this algorithm. While the first property only relies on a match/no-match the second one requires much more details than just "we have found a match". Indeed the second property would not have been feasible if the algorithm only returned a boolean value to tell if such place exists or not. It required the location of the upper-left corner to be writable. I initially opted for a boolean output but as I struggled to have a second property I moved to a more verbose output making me able to assess a bit more things. At the end this more verbose output did not required more computations so we did not alter the algorithm for the needs of the tests. But we have here a good example for which properties can be more complex to write if the output is too restricted. By the way, we can still rewrite easily a hasRoomForSanta based on findPlaceForSanta without too much work.

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.

Advent of PBT 2021 - Day 21

Nicolas DUBIEN — Tue, 21 Dec 2021 08:34:39 +0000

Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples

Our algorithm today is: findPlaceForSanta.
It comes with the following documentation and prototype:

/**
 * For the Christmas market, Santa is looking for a place.
 *
 * For each market of the world, he has to check if it can land with
 * his 8 reindeers and his sleigh. He is looking for help to compute
 * that quickly as Christmas is coming really really soon.
 *
 * Check whether there is an area of consecutive true that can
 * contain requestedArea and return its upper-left corner.
 *
 * @param map - A map of boolean value, true for available, false
 *              otherwise. Indexed by map[y][x]
 * @param requestedArea - The area to look for
 *
 * map.length corresponds to the height of the map
 * map[0].length corresponds to the width of the map
 *
 * @returns
 * - the upper-left corner of the area,
 *   whenever there is one place in the map having with
 *   rectangular width x height surface with only true
 * - undefined if no such area exists
 */
declare function findPlaceForSanta(
  map: boolean[][],
  requestedArea: { width: number; height: number }
): { x: number; y: number } | undefined;

We already wrote some examples based tests for it:

it("should find a place for santa given the map has one with exact size", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toEqual({ x: 3, y: 0 });
});

it("should find a place for santa given the map has one larger", () => {
  // Arrange
  const map = [
    [false, false, true, true, true, true],
    [false, true, false, true, true, true],
    [false, false, false, true, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toEqual({ x: 3, y: 0 });
});

it("should not find the requested place if height is too small", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 3 });

  // Assert
  expect(location).toBe(undefined);
});

it("should not find the requested place if width is too small", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 4, height: 2 });

  // Assert
  expect(location).toBe(undefined);
});

it("should not find the requested place if place is not rectangular", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, true, true, true, false],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toBe(undefined);
});

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-21-19pp8?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-21-solution-3j1m

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.

Advent of PBT 2021 - Day 20 - Solution

Nicolas DUBIEN — Mon, 20 Dec 2021 09:18:15 +0000

Our algorithm was: drawTree.
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-20-solution-21h7b?file=/src/index.spec.ts&previewwindow=tests

Property 1: should build a linear trunk

for any requested size of tree n
it should render a tree having a linear trunk

Written with fast-check:

it("should build a linear trunc", () => {
  fc.assert(
    fc.property(fc.integer({ min: 1, max: 1000 }), (n) => {
      // Arrange / Act
      const tree = drawTree(n);

      // Assert
      // Remove all the leaves from the tree to only keep the trunk
      const treeWithoutLeaves = tree
        .split("\n")
        .map((level) => level.replace(/[()]/g, " ").trimRight());
      for (const level of treeWithoutLeaves) {
        expect(level.trimLeft()).toEqual("^");
        expect(level).toEqual(treeWithoutLeaves[0]);
      }
    })
  );
});

Property 2: should create larger and larger levels

for any requested size of tree n
it should render a tree having levels being larger and larger as we move down in the tree

Written with fast-check:

it("should create larger and larger levels", () => {
  fc.assert(
    fc.property(fc.integer({ min: 1, max: 1000 }), (n) => {
      // Arrange / Act
      const tree = drawTree(n);

      // Assert
      const treeLevels = tree.split("\n").map((level) => level.trim());
      for (let index = 1; index < n; ++index) {
        expect(treeLevels[index]).toContain(treeLevels[index - 1]);
      }
    })
  );
});

Property 3: should offset leaves from one level to the next one

for any requested size of tree n
it should render a tree with leaves being offset from one level to the next one

Written with fast-check:

it("should offset leaves from one level to the next one", () => {
  fc.assert(
    fc.property(fc.integer({ min: 1, max: 1000 }), (n) => {
      // Arrange / Act
      const tree = drawTree(n);

      // Assert
      const treeLevels = tree.split("\n").map((level) => level.trim());
      for (let index = 1; index < n; ++index) {
        expect(treeLevels[index]).toEqual("(" + treeLevels[index - 1] + ")");
      }
    })
  );
});

Property 4: should create a base of size two with levels identical to the top

for any requested size of tree n
it should render a tree having a base of size 2

Written with fast-check:

it("should create a base of size two with levels identical to the top", () => {
  fc.assert(
    fc.property(fc.integer({ min: 1, max: 1000 }), (n) => {
      // Arrange / Act
      const tree = drawTree(n);

      // Assert
      const treeLevels = tree.split("\n");
      expect(treeLevels).toHaveLength(n + 2);
      expect(treeLevels[n]).toEqual(treeLevels[0]);
      expect(treeLevels[n + 1]).toEqual(treeLevels[0]);
    })
  );
});

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.

Advent of PBT 2021 - Day 20

Nicolas DUBIEN — Mon, 20 Dec 2021 09:17:50 +0000

Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples

Our algorithm today is: drawTree.
It comes with the following documentation and prototype:

/**
 * Draw a tree with:
 * - a trunc made of '^',
 * - leaves on the left made of '('
 * - and the ones on the right made of ')'
 *
 * @param size - Size of the tree >=1
 */
declare function drawTree(size: number): string;

We already wrote some examples based tests for it:

it("should be able to draw a tree of size 1", () => {
  // prettier-ignore
  expect(drawTree(1)).toEqual(
    "^\n" +
    "^\n" +
    "^"
  );
});

it("should be able to draw a tree of size 2", () => {
  // prettier-ignore
  expect(drawTree(2)).toEqual(
    " ^\n" +
    "(^)\n" +
    " ^\n" +
    " ^"
  );
});

it("should be able to draw a tree of size 5", () => {
  // prettier-ignore
  expect(drawTree(5)).toEqual(
    "    ^\n" +
    "   (^)\n" +
    "  ((^))\n" +
    " (((^)))\n" +
    "((((^))))\n" +
    "    ^\n" +
    "    ^"
  );
});

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-20-61ylb?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-20-solution-43nm

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.

Advent of PBT 2021 - Day 19 - Solution

Nicolas DUBIEN — Sun, 19 Dec 2021 11:13:56 +0000

Our algorithm was: metroRoute.
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-19-solution-t470u?file=/src/index.spec.ts&previewwindow=tests

As for many of the properties we have defined so far in this Advent calendar, the idea will be to build some inputs we know a lot about. In other words we will not build fully random ones that would possibly require us to re-implement part of the logic.

For this algorithm we will need two main builders:

one for maps of metro with known connections between two stations
one for maps of the metro with a clear absence of path between two stations

For the first of the two the idea is to generate two entities:

a route of stations: first station will be the departure, last one will be the destination and the route itself is one of the known set of tracks to go from departure to destination
a set of other tracks: possibly including some that will be used to go more quickly from departure to destination

Written with fast-check:

function orientedGraphArbitrary() {
  return fc
    .record({
      // tracks that will compose the known path (starting at node=0)
      knownPathExcludingStart: fc.set(
        fc.record({ node: fc.integer({ min: 1 }), length: fc.nat() }),
        { compare: (na, nb) => na.node === nb.node }
      ),
      // some more tracks that will compose our graph
      extraTracks: fc.array(
        fc.record({ from: fc.nat(), to: fc.nat(), length: fc.nat() })
      )
    })
    .chain(({ knownPathExcludingStart, extraTracks }) => {
      const departure = 0;
      const knownPath = [
        departure,
        ...knownPathExcludingStart.map((n) => n.node)
      ];
      const knownPathTracks = knownPathExcludingStart.map((n, index) => ({
        from: index !== 0 ? knownPathExcludingStart[index - 1].node : departure,
        to: n.node,
        length: n.length
      }));
      const allTracks = [...knownPathTracks, ...extraTracks];
      return fc.record({
        knownPath: fc.constant(knownPath),
        knownPathTracks: fc.constant(knownPathTracks),
        tracks: fc.shuffledSubarray(allTracks, { minLength: allTracks.length })
      });
    });
}

Our second builder will be responsible to build maps not having routes leading from departure to destination. In order to do so we will generate the following entries:

a set of tracks going from stations in [0, 9] to stations in [0, 9]
a set of tracks going from stations in [10, 19] to stations in [10, 19]
a set of tracks going from stations in [10, 19] to stations in [0, 9]
departure will be 0
destination will be 19

So we have no route going from departure to destination.

Written with fast-check:

function orientedGraphNoWayArbitrary() {
  return fc
    .record({
      // We consider start = 0 and end = 19.
      // We delimit two zones:
      // - start zone contains stations 0 to 9 (included)
      // - end zone contains stations 10 to 19 (included)
      tracksStartZone: fc.array(
        fc.record({
          from: fc.integer({ min: 0, max: 9 }),
          to: fc.integer({ min: 0, max: 9 }),
          length: fc.nat()
        })
      ),
      tracksEndZone: fc.array(
        fc.record({
          from: fc.integer({ min: 10, max: 19 }),
          to: fc.integer({ min: 10, max: 19 }),
          length: fc.nat()
        })
      ),
      tracksEndToStart: fc.array(
        fc.record({
          from: fc.integer({ min: 10, max: 19 }),
          to: fc.integer({ min: 0, max: 9 }),
          length: fc.nat()
        })
      )
    })
    .map((config) => ({
      departure: 0,
      destination: 19,
      tracks: [
        ...config.tracksStartZone,
        ...config.tracksEndZone,
        ...config.tracksEndToStart
      ]
    }));
}

Property 1: should build a path starting by the requested departure whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the first track starting at departure

Written with fast-check:

it("should build a path starting by the requested departure whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      if (departure === destination) expect(shortestPath).toEqual([]);
      else expect(shortestPath![0].from).toBe(departure);
    })
  );
});

Property 2: should build a path ending by the requested destination whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the end track ending at destination

Written with fast-check:

it("should build a path ending by the requested destination whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      if (departure === destination) expect(shortestPath).toEqual([]);
      else expect(shortestPath![shortestPath!.length - 1].to).toBe(destination);
    })
  );
});

Property 3: should build an ordered path of tracks whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the start of each track connected to the end of the previous one

Written with fast-check:

it("should build an ordered path of tracks whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      for (let index = 1; index < shortestPath!.length; ++index) {
        expect(shortestPath![index].from).toBe(shortestPath![index - 1].to);
      }
    })
  );
});

Property 4: should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with only tracks declared in the set of tracks

Written with fast-check:

it("should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      for (const edge of shortestPath!) {
        expect(shortestPath).toContainEqual(edge);
      }
    })
  );
});

Property 5: should be able to find a path shorther or equal to the one we come up with

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with length shorter or equal to the known route

Written with fast-check:

it("should be able to find a path shorther or equal to the one we come up with", () => {
  fc.assert(
    fc.property(
      orientedGraphArbitrary(),
      ({ knownPath, knownPathTracks, tracks }) => {
        // Arrange
        const departure = knownPath[0];
        const destination = knownPath[knownPath.length - 1];

        // Act
        const shortestPath = metroRoute(departure, destination, tracks);

        // Assert
        const distanceKnownPath = knownPathTracks.reduce((acc, e) => acc + e.length, 0);
        const distanceShortestPath = shortestPath!.reduce((acc, e) => acc + e.length, 0);
        expect(distanceShortestPath).toBeLessThanOrEqual(distanceKnownPath);
      }
    )
  );
});

Property 6: should not return any path whenever there is no way going from start to end

for map of the metro and two stations "departure" and "destination" known not to be connected
it should not find any track going from "departure" to "destination"

Written with fast-check:

it("should not return any path whenever there is no way going from start to end", () => {
  fc.assert(
    fc.property(
      orientedGraphNoWayArbitrary(),
      ({ departure, destination, tracks }) => {
        // Arrange / Act
        const shortestPath = metroRoute(departure, destination, tracks);

        // Assert
        expect(shortestPath).toBe(undefined);
      }
    )
  );
});

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.