Advent of PBT 2021 - Day 22

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.