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
trueandfalse, we will call this maprawMap - given those dimensions, generate a place for Santa, we will call it
request - now that we have
rawMapandrequest, we can generate the finalmap: the same asrawMapexcept that any cell withinrequestwill be set totrue(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.
Top comments (0)