Our algorithm was: validParentheses.
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-12-solution-qxu3z?file=/src/index.spec.ts&previewwindow=tests
Property 1: should accept any well-parenthesized expression
As building a well-parenthesized expression is mostly a matter of recursion, we can consider that we could easily come up with an arbitrary to do so.
for any well-parenthesized expression
it should accept it
Written with fast-check:
it("should accept any well-parenthesized expression", () => {
fc.assert(
fc.property(wellParenthesizedStringArbitrary, (expression) => {
expect(validParentheses(expression)).toBe(true);
})
);
});
A well-parenthesized expression can be seen as something like:
type WellParenthesized = {
type: "(" | "[" | "{";
content: WellParenthesized[];
};
In other words a type of bracket and a content made of other well-parenthesized expressions.
For instance we can define:
const wellParenthesized = {
type: '(',
content: [
{ type: '[', content: [] },
{ type: '{', content: [] },
]
}
// corresponds to: ([]{})
Given a well-parenthesized definition, we can compute its string representation with:
function wellParenthesizedToString(definition: WellParenthesized): string {
const { type, content } = definition;
const openingBracket = type;
const closingBracket = type === "(" ? ")" : type === "[" ? "]" : "}";
return `${openingBracket}${content
.map((p) => wellParenthesizedToString(p))
.join("")}${closingBracket}`;
}
Now that we defined most the the building blocks of wellParenthesizedStringArbitrary we can write it by relying on fc.letrec:
// Arbitrary building instances of WellParenthesized
const wellParenthesizedArbitrary = fc.letrec((tie) => ({
parenthesized: fc.record<WellParenthesized>({
type: fc.constantFrom("(", "[", "{"),
// We use a oneof instead of a raw array to enforce the convergence towards a finite structure
content: fc.oneof(
{ depthFactor: 1 },
fc.constant([]),
fc.array(tie("parenthesized") as fc.Arbitrary<WellParenthesized>)
)
})
})).parenthesized;
// Arbitrary building valid parenthesized expressions
const wellParenthesizedStringArbitrary = fc
.array(wellParenthesizedArbitrary)
.map((def) => def.map((p) => wellParenthesizedToString(p)).join(""));
Property 2: should reject any expression not containing an even number of signs
There are multiple ways not to be valid and building an arbitrary building any of the possible invalid parenthesized expressions is not that simple.
Instead, we will consider case by case.
For instance, any expression containing an odd number of symbols is known to be an invalid expression.
for expression containing an odd number of brackets
it should reject it
Written with fast-check:
it("should reject any expression not containing an even number of signs", () => {
fc.assert(
fc.property(
fc
.tuple(
fc.array(
fc.tuple(
fc.constantFrom("(", "[", "{", ")", "]", "}"),
fc.constantFrom("(", "[", "{", ")", "]", "}")
)
),
fc.constantFrom("(", "[", "{", ")", "]", "}")
)
.chain(([evenNumParentheses, extraParenthesis]) => {
const parentheses = [...evenNumParentheses.flat(), extraParenthesis];
return fc
.shuffledSubarray(parentheses, { minLength: parentheses.length })
.map((parentheses) => parentheses.join(""));
}),
(invalidExpression) => {
expect(validParentheses(invalidExpression)).toBe(false);
}
)
);
});
We could also have written it with something simpler like:
it("should reject any expression not containing an even number of signs (2)", () => {
fc.assert(
fc.property(
fc
.array(fc.constantFrom("(", "[", "{", ")", "]", "}"), { minLength: 1 })
.filter((parentheses) => parentheses.length % 2 === 1)
.map((parentheses) => parentheses.join("")),
(invalidExpression) => {
expect(validParentheses(invalidExpression)).toBe(false);
}
)
);
});
But this one will reject half of the generated values.
Property 3: should reject any expression not having the same number of openings and closings
Another possible cause of rejections is an expression with mismatching number of openings and closings.
for expression not containing the same number of openings as closings
it should reject it
Written with fast-check:
it("should reject any expression not having the same number of openings and closings", () => {
fc.assert(
fc.property(
wellParenthesizedStringArbitrary,
fc.constantFrom("(", "[", "{", ")", "]", "}"),
fc.nat().noShrink(),
(expression, extra, seed) => {
const position = seed % (expression.length + 1);
const invalidExpression =
expression.substring(0, position) +
extra +
expression.substring(position);
expect(validParentheses(invalidExpression)).toBe(false);
}
)
);
});
This property is actually a sub-case of the property before. Indeed, the expression above is made of an odd number of signs so it will already be covered by the property 2. Property 3 only gives more details for one specific sub-case.
Property 4: should reject any expression with at least one reversed openings and closings
Other ways to build invalid parenthesized expressions need to be fine tune one by one as there are multiple ways to go wrong. A simple example of that problem is the following property:
for expression containing at least one reversed set of parentheses
it should reject it
Actually this property is partially wrong, as:
const wellParenthesizedDefinition = {
type: '(',
content: [
{
type: '(',
content: []
},
]
};
// corresponds to: (())
And:
const reversedParenthesizedDefinition = {
type: '(',
content: [
{
type: '(',
content: [],
reversed: true,
},
],
reversed: false,
};
// corresponds to: ()()
Result both into well-parenthesized expressions.
In other words, building an invalid parenthesized expression is not just a matter of reversing one set of parentheses. With some fine tuning we can reach a quite decent property based on the idea of reversed parenthesized expressions but with some safety nets added to prevent falling into cases like the one discussed above.
Written with fast-check:
it("should reject any expression with at least one reversed openings and closings", () => {
fc.assert(
fc.property(reversedParenthesizedStringArbitrary, (expression) => {
expect(validParentheses(expression)).toBe(false);
})
);
});
With reversedParenthesizedStringArbitrary:
type ReversedParenthesized = {
type: "(" | "[" | "{";
content: ReversedParenthesized[];
reversed: boolean;
};
function reversedParenthesizedToString(
subDefinition: ReversedParenthesized
): string {
const { type, content, reversed } = subDefinition;
const matching = type === "(" ? ")" : type === "[" ? "]" : "}";
const openingBracket = reversed ? matching : type;
const closingBracket = reversed ? type : matching;
return `${openingBracket}${content
.map((p) => reversedParenthesizedToString(p))
.join("")}${closingBracket}`;
}
function hasReversed(subDefinition: ReversedParenthesized): boolean {
if (subDefinition.reversed) return true;
return subDefinition.content.some(
(p) => subDefinition.type !== p.type && hasReversed(p)
);
}
const reversedParenthesizedArbitrary = fc.letrec((tie) => ({
parenthesized: fc.record<ReversedParenthesized>({
reversed: fc.boolean(),
type: fc.constantFrom("(", "[", "{"),
// We use a oneof instead of a raw array to enforce the convergence towards a finite structure
content: fc.oneof(
{ depthFactor: 1 },
fc.constant([]),
fc.array(tie("parenthesized") as fc.Arbitrary<ReversedParenthesized>)
)
})
})).parenthesized;
const reversedParenthesizedStringArbitrary = fc
.array(reversedParenthesizedArbitrary)
.filter((def) => def.some((p) => hasReversed(p)))
.map((def) => def.map((p) => reversedParenthesizedToString(p)).join(""));
Property 5: should reject any expression with non-matching openings and closings
With the same drawbacks as the ones explained in property 4, we can define a property like:
for expression containing at least one non-matching set of parentheses
it should reject it
Written with fast-check:
it("should reject any expression with non-matching openings and closings", () => {
fc.assert(
fc.property(nonMatchingEndParenthesizedStringArbitrary, (expression) => {
expect(validParentheses(expression)).toBe(false);
})
);
});
With nonMatchingEndParenthesizedStringArbitrary:
type NonMatchingEndParenthesized = {
start: "(" | "[" | "{";
end: ")" | "]" | "}";
content: NonMatchingEndParenthesized[];
};
const nonMatchingEndParenthesizedArbitrary = fc.letrec((tie) => ({
parenthesized: fc.record<NonMatchingEndParenthesized>({
start: fc.constantFrom("(", "[", "{"),
end: fc.constantFrom(")", "]", "}"),
// We use a oneof instead of a raw array to enforce the convergence towards a finite structure
content: fc.oneof(
{ depthFactor: 1 },
fc.constant([]),
fc.array(
tie("parenthesized") as fc.Arbitrary<NonMatchingEndParenthesized>
)
)
})
})).parenthesized;
function nonMatchingEndParenthesizedToString(
definition: NonMatchingEndParenthesized
): string {
return `${definition.start}${definition.content
.map((p) => nonMatchingEndParenthesizedToString(p))
.join("")}${definition.end}`;
}
function hasNonMatchingEnd(
subDefinition: NonMatchingEndParenthesized
): boolean {
const matchingEnd =
subDefinition.start === "(" ? ")" : subDefinition.start === "[" ? "]" : "}";
if (subDefinition.end !== matchingEnd) return true;
if (subDefinition.content.length !== 1)
return subDefinition.content.some((p) => hasNonMatchingEnd(p));
return false; // We still reject too many things
}
const nonMatchingEndParenthesizedStringArbitrary = fc
.array(nonMatchingEndParenthesizedArbitrary)
.filter((def) => def.some((p) => hasNonMatchingEnd(p)))
.map((def) => def.map((p) => nonMatchingEndParenthesizedToString(p)).join(""));
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)