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.
Top comments (0)