Advent of PBT 2021 - Day 8 - Solution

Our algorithm was: hasDuplicates.
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-8-solution-qey5j?file=/src/index.spec.ts&previewwindow=tests

Property 1: should not detect any duplicates when array has only distinct values

We first want to make sure that the algorithm will not produce false positives. In other words, that it will not detect duplicates on arrays not having any.

In order to check that, we will check that the following property is always true:

for any array of unique values regarding Object.is
hasDuplicates should not detect any duplicates

Written with fast-check:

it("should not detect any duplicates when array has only distinct values", () => {
  fc.assert(
    fc.property(fc.set(fc.integer(), { compare: Object.is }), (data) => {
      expect(hasDuplicates(data)).toBe(false);
    })
  );
});

In the property above, we restricted the set of inputs to fc.integer() but in reality the best option would have been to replace it by fc.anything() so that we clearly state that it should work whatever the data defined in the array.

If you double-check the implementation on the codesandbox, you might see that the proposed implementation had to explicitly deal with -0 vs 0 handling. A naive implementation backed by a native Set would have failed as it would not have used the right comparator. So it's important to let as much flexibility as possible to the framework if you want it to detect such cases. On the other hand, too much flexibility means less chances to fall on common cases. A middle ground solution might be to define two properties: one for the common case based on basic fc.integer() and one for exotic cases based on fc.anything().

Property 2: should always detect duplicates when there is at least one

Now that we checked that the algorithm should not detect duplicates when the array is made of unique values regarding Object.is. Let's check that it detects duplicates whenever there is one.

In order to do so, we will build an array with duplicates. Please note that we do not take a random array and somehow check for duplicates into it, we instead build one with known duplicates.

for arrays of values - start, middle and end - and one value dup
hasDuplicates should detect a duplicate in the array: [...start, dup, ...middle, dup, ...end]

Written with fast-check:

it("should always detect duplicates when there is at least one", () => {
  fc.assert(
    fc.property(
      fc.array(fc.anything()),
      fc.array(fc.anything()),
      fc.array(fc.anything()),
      fc.anything(),
      (start, middle, end, dup) => {
        expect(hasDuplicates([...start, dup, ...middle, dup, ...end]))
          .toBe(true);
      }
    )
  );
});

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.