Advent of PBT 2021 - Day 5 - Solution

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

Before we start we will consider one helper that will help us to build our arbitraries and properties: wordArb.

const alphaCharArb = fc.integer({
  min: 'a'.charCodeAt(0),
  max: 'z'.charCodeAt(0)
}).map((v) => String.fromCharCode(v));

const wordArb = fc.stringOf(alphaCharArb, { minLength: 1 });

Such helper can help you to change the set of inputs you want to consider as being a valid word for your algorithm. A possible option would have been to define:

const alphaCharArb = fc.fullUnicode().filter(c => c !== " ");
const wordArb = fc.stringOf(alphaCharArb, { minLength: 1 });

Property 1: should be able to find back the original message

First of all we want to make sure the algorithm will be able to decode any valid message. In other words:

for any valid message
let consider space-less message as being valid message with all the spaces removed
respace should find back valid message given space-less message along the words inside it

Written with fast-check:

it("should be able to find back the original message", () => {
  fc.assert(
    fc.property(
      fc.set(wordArb, { minLength: 1 }).chain((words) =>
        fc.record({
          words: fc.constant(words),
          originalMessage: fc
            .array(fc.constantFrom(...words))
            .map((items) => items.join(" "))
        })
      ),
      ({ words, originalMessage }) => {
        const spacelessMessage = originalMessage.replace(/ /g, "");
        const combinations = respace(spacelessMessage, words);
        expect(combinations).toContain(originalMessage);
      }
    )
  );
});

How does it work?

We create an array of unique words containing at least one word thanks to fc.set(wordArb, { minLength: 1 }).

Then we build a record having two fields:

• words: the array containing all the words of our dictionary
• originalMessage: a message made out of those words

In the test itself, we build spacelessMessage by removing all the spaces of originalMessage.

At the end, we expect the returned value of respace to contain at least our originalMessage.

Property 2: should only return messages with spaceless version being the passed message

The second thing we want to confirm is that all the returned values are compatible with the message without any spaces.

for any dictionary and space-less message
it should only produce values compatible with space-less message

Specified as defined above the property will rarely fall in cases with respace able to find a valid combination of words. As a consequence we can rewrite it as follow:

for any dictionary
let's build a message called originalMessage based on this dictionary
let's consider words a sub-dictionary of the original one
respace should only produce values compatible with the space-less version of the message

Compared to the previous way to write the property, this one will have more chance to fall into cases with words being compatible with originalMessage and thus with at least one match. It also preserves the non-match case thanks to the fact that words is just a subset of the dictionary used to build originalMessage.

Written with fast-check:

it("should only return messages with spaceless version being the passed message", () => {
  fc.assert(
    fc.property(
      fc.set(wordArb, { minLength: 1 }).chain((words) =>
        fc.record({
          words: fc.shuffledSubarray(words), // we potentially remove words from the dictionary to cover no match case
          originalMessage: fc
            .array(fc.constantFrom(...words))
            .map((items) => items.join(" "))
        })
      ),
      ({ words, originalMessage }) => {
        const spacelessMessage = originalMessage.replace(/ /g, "");
        const combinations = respace(spacelessMessage, words);
        for (const combination of combinations) {
          expect(combination.replace(/ /g, "")).toBe(spacelessMessage);
        }
      }
    )
  );
});

Property 3: should only return messages built from words coming from the set of words

Same idea as second property but this time we want to check that the output is really made of words coming from the dictionary.

for any dictionary and space-less message
it should only produce values compatible with the dictionary

Written with fast-check:

it("should only return messages built from words coming from the set of words", () => {
  fc.assert(
    fc.property(
      fc.set(wordArb, { minLength: 1 }).chain((words) =>
        fc.record({
          words: fc.shuffledSubarray(words), // we potentially remove words from the dictionary to cover no match case
          originalMessage: fc
            .array(fc.constantFrom(...words))
            .map((items) => items.join(" "))
        })
      ),
      ({ words, originalMessage }) => {
        const spacelessMessage = originalMessage.replace(/ /g, "");
        const combinations = respace(spacelessMessage, words);
        for (const combination of combinations) {
          if (combination.length !== 0) {
            expect(words).toIncludeAnyMembers(combination.split(" "));
          }
        }
      }
    )
  );
});

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.