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 calledoriginalMessage
based on this dictionary
let's considerwords
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.
Top comments (0)