Advent of PBT 2021 - Day 1 - Solution

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

Property 1: should detect a sub-string when there is one

For this first property, we will come up with tailored inputs having some already known characteristics. Instead of taking two fully random strings, we build two strings having some links together.

for any a, b and c strings
b should be seen as a sub-string of a+b+c

In other words:

for any a, b and c strings
lastIndexOf(b, a+b+c) should be different from -1
as -1 means no match

Written with fast-check:

it("should detect a substring when there is one", () => {
  fc.assert(
    fc.property(fc.string(), fc.string(), fc.string(), (a, b, c) => {
      const searchString = b;
      const text = `${a}${b}${c}`;
      expect(lastIndexOf(searchString, text)).not.toBe(-1);
    })
  );
});

In this property we only covered the fact that if there was a match we could say that there is one. But we have not checked that the returned index is correct or that the algorithm works when there is 'no match'.

Regarding returned index, we cannot cover it directly via this property. Expecting lastIndexOf to return a.length will not be a valid expectation. Indeed let's imagine that fast-check comes up with: a="", b="abc", c="abc", lastIndexOf("abc", "abcabc") = 3 (not a.length).

Property 2: should return the start index of the sub-string when there is one

As seen in previous property, we are not covering the value returned by lastIndexOf but just that it can tell us that there is a match when there is one. It is already an important feature for lastIndexOf. But we want to go further.

The value returned by lastIndexOf is full of details we have not used yet. Indeed when we have lastIndexOf("abc", "abcdabcd") = 4, it actually means that if we take the sub-string starting at index 4 and having the same size as the one of "abc", we will find "abc". Let's check if our function really works by checking that fact on it.

for any a, b and c strings
the string starting at the index returned by lastIndexOf(b, a+b+c)
and having a size of b.length should be equal to b

Written with fast-check:

it("should return the start index of the substring when there is one", () => {
  fc.assert(
    fc.property(fc.string(), fc.string(), fc.string(), (a, b, c) => {
      const searchString = b;
      const text = `${a}${b}${c}`;
      const index = lastIndexOf(searchString, text);
      expect(text.substr(index, searchString.length)).toBe(searchString);
    })
  );
});

But we still have not covered the "no match" case. But before we do we still have one characteristic to cover regarding matches: is it really the last one?

Property 3: should return the last possible index of the sub-string when there is one

If our match is the last one, then if I take the string starting at the returned index +1, I should have no match. In other words, I expect the following property to be true:

for any a, b and c strings
the string starting at the index lastIndexOf(b, a+b+c) + 1
should not have b as a sub-string

Written with fast-check:

it("should return the last possible index of the substring when there is one", () => {
  fc.assert(
    fc.property(
      fc.string(),
      fc.string({ minLength: 1 }),
      fc.string(),
      (a, b, c) => {
        const searchString = b;
        const text = `${a}${b}${c}`;
        const textBis = text.substring(lastIndexOf(searchString, text) + 1);
        expect(lastIndexOf(searchString, textBis)).toBe(-1);
      }
    )
  );
});

With this last property we also covered the "no match" case as we expect to fall in such case as soon as we removed all the matches and only kept the part without any.

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.