Advent of PBT 2021 - Day 21 - Solution
Tags: challenge, testing, webdev, javascript
Published: 2021-12-21 08:34:54

---
title: Advent of PBT 2021 - Day 21 - Solution
published: true
description: Advent of Property Based Testing 2021 - Day 21 - Solution
tags: challenge,testing,webdev,javascript
//cover_image: https://direct_url_to_image.jpg
---

Our algorithm was: **findPlaceForSanta**.
[Go to the subject itself for more details](https://dev.to/dubzzz/advent-of-pbt-2021-day-21-4186)

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:

```ts
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:

```ts
// 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:

```ts
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"](https://dev.to/dubzzz/advent-of-pbt-2021-13ee) to see topics covered during the other days and their solutions.

More about this serie on [@ndubien](https://twitter.com/ndubien) or with the hashtag [#AdventOfPBT](https://twitter.com/search?q=%23AdventOfPBT).