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
andc
strings
b
should be seen as a sub-string ofa+b+c
In other words:
for any
a
,b
andc
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
andc
strings
the string starting at the index returned bylastIndexOf(b, a+b+c)
and having a size ofb.length
should be equal tob
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
andc
strings
the string starting at the indexlastIndexOf(b, a+b+c) + 1
should not haveb
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.
Top comments (0)