Nicolas DUBIEN

Posted on

# 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.