DEV Community 👩‍💻👨‍💻

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

Advent of PBT 2021 - Day 12 - Solution

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);
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

A well-parenthesized expression can be seen as something like:

type WellParenthesized = {
  type: "(" | "[" | "{";
  content: WellParenthesized[];
};
Enter fullscreen mode Exit fullscreen mode

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: ([]{})
Enter fullscreen mode Exit fullscreen mode

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}`;
}
Enter fullscreen mode Exit fullscreen mode

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(""));
Enter fullscreen mode Exit fullscreen mode

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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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: (())
Enter fullscreen mode Exit fullscreen mode

And:

const reversedParenthesizedDefinition = {
  type: '(',
  content: [
    {
      type: '(',
      content: [],
      reversed: true,
    },
  ],
  reversed: false,
};
// corresponds to: ()()
Enter fullscreen mode Exit fullscreen mode

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);
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

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(""));
Enter fullscreen mode Exit fullscreen mode

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);
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

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(""));
Enter fullscreen mode Exit fullscreen mode

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)

Take a look at this:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. 🛠