Advent of PBT 2021 - Day 22 - Solution

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.