Advent of PBT 2021 - Day 18 - Solution

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

Property 1: should detect any valid palindrome having even number of characters

for any palindrome made of an even number of characters
it should consider it as a palindrome

In other words:

for any string s
the string s + reverse(s) should be considered as a palindrome

Written with fast-check:

it("should detect any valid palindrome having even number of characters", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (start) => {
      // Arrange
      const reversedStart = [...start].reverse().join("");
      const palindrome = `${start}${reversedStart}`;

      // Act / Assert
      expect(isPalindrome(palindrome)).toBe(true);
    })
  );
});

Property 2: should detect any valid palindrome having odd number of characters

for any palindrome made of an odd number of characters
it should consider it as a palindrome

In other words:

for any string s and char c
the string s + c + reverse(s) should be considered as a palindrome

Written with fast-check:

it("should detect any valid palindrome having odd number of characters", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), fc.fullUnicode(), (start, c) => {
      // Arrange
      const reversedStart = [...start].reverse().join("");
      const palindrome = `${start}${c}${reversedStart}`;

      // Act / Assert
      expect(isPalindrome(palindrome)).toBe(true);
    })
  );
});

Property 3: should detect any invalid palindrome

for any non-palindrome
it should not consider it as a palindrome

In other words we should build find a way to generate a string which will never be a palindrome. A way to do that is to do the following:

for any strings s, m and chars a, b
with a different from b
the string s + a + m + b + reverse(s) not should be considered as a palindrome

Why that? Actually s and reverse(s) have the same length so in order to be a palindrome a and b must be equal. It is never the case by construct.

Written with fast-check:

it("should detect any invalid palindrome", () => {
  fc.assert(
    fc.property(
      fc.fullUnicodeString(),
      fc.fullUnicode(),
      fc.fullUnicode(),
      fc.fullUnicodeString(),
      (start, a, b, middle) => {
        // Arrange
        fc.pre(a !== b);
        const reversedStart = [...start].reverse().join("");
        const notPalindrome = `${start}${a}${middle}${b}${reversedStart}`;
        // not a palindrome as the mirror of a is b and a !== b

        // Act / Assert
        expect(isPalindrome(notPalindrome)).toBe(false);
      }
    )
  );
});

Property 4: should have the same answer for s and reverse(s)

Knowing we already covered all the cases given the three properties defined above. The following ones are pure bonus and mostly show other possible properties you may have come with.

for any string s
it should have the same result for both s and reverse(s)

Written with fast-check:

it("should have the same answer for s and reverse(s)", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (s) => {
      // Arrange
      const reversedS = [...s].reverse().join("");

      // Act / Assert
      expect(isPalindrome(reversedS)).toBe(isPalindrome(s));
    })
  );
});

Property 5: should be equivalent to non-optimal implementation based on fully reversing the string

While comparing to an equivalent implementation looks appealing, it is often a risk for rewriting twice the implementation: one time for the real implementation and one time for the tests. In my opinion it tends to increase the risk of invalid tests as tests and implementation may share too many things in terms of how they work.

Ideally approaches trying to build inputs like properties 1, 2 or 3 should be preferred given they never try to re-implement the algorithm but just rely on examples known to always be palindromes (or the opposite). Properties like number 4 are also better as they assess some characteristics we expect and once again without having to re-implement the logic of the implementation.

But here is an example comparing one implementation against a simple one in-lined in the test:

for any string s
it should produce the same answer as a given simple implementation

Written with fast-check:

it("should be equivalent to non-optimal implementation based on fully reversing the string", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (s) => {
      // Arrange
      const reversedS = [...s].reverse().join("");
      const expectedResult = reversedS === s;

      // Act / Assert
      expect(isPalindrome(s)).toBe(expectedResult);
    })
  );
});

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.