DEV Community

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Edited on

Advent of PBT 2021 - Day 21 - Solution

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 true and false, we will call this map rawMap
  • given those dimensions, generate a place for Santa, we will call it request
  • now that we have rawMap and request, we can generate the final map: the same as rawMap except that any cell within request will be set to true (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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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 }
  );
}
Enter fullscreen mode Exit fullscreen mode

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);
            }
          }
        }
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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)