Advent of PBT 2021 - Day 9 - Solution

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

Property 1: should have the same length as source

for any array of values
the sorted array should have the same length as the inputted one

Written with fast-check:

it("should have the same length as source", () => {
  fc.assert(
    fc.property(fc.array(fc.integer()), (data) => {
      expect(sorted(data)).toHaveLength(data.length);
    })
  );
});

Property 2: should have exactly the same number of occurrences as source for each item

In addition to length, we can also check that the values have not changed. In other words, we want to make sure that if there was 5 times the number 8 in the array, then we will also see it 5 times in the sorted array.

for any array of values
the number of occurrences for each value in sorted version should be the same as the number of occurrences in the inputted array

Written with fast-check:

it("should have exactly the same number of occurrences as source for each item", () => {
  fc.assert(
    fc.property(fc.array(fc.integer()), (data) => {
      const sortedData = sorted(data);
      expect(countEach(sortedData)).toEqual(countEach(data));
    })
  );
});

Property 3: should produce an ordered array

Up to now, we have not checked the key characteristics and requirement of a sort: being able to sort things. So let's do that with the following property:

for any array of values
the sorted version of the array should verify sorted[index] <= sorted[index+1] for any valid index

Written with fast-check:

it("should produce an ordered array", () => {
  fc.assert(
    fc.property(fc.array(fc.integer()), (data) => {
      const sortedData = sorted(data);
      for (let idx = 1; idx < sortedData.length; ++idx) {
        expect(sortedData[idx - 1]).toBeLessThanOrEqual(sortedData[idx]);
      }
    })
  );
});

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.