Advent of PBT 2021 - Day 10 - Solution

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

Property 1: should never request any changes when moving a string to itself

One of the first option to consider when trying to cover a code with properties is to find subsets of the problem that have simple to compute solutions. In other words, find some inputs with easy answers but clearly not covering the whole scope of the algorithm.

While they offer a limited coverage of the feature, they are often a very good start and can already be pretty powerful to detect unexpected issues. This first property is a good example of such properties.

for any string - value
the minimal number of changes to move from value to value is exactly 0

Written with fast-check:

it("should never request any changes when moving a string to itself", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (value) => {
      // Arrange / Act
      const numChanges = minimalNumberOfChangesToBeOther(value, value);

      // Assert
      expect(numChanges).toBe(0);
    })
  );
});

Property 2: should request target.length changes to move from empty to target

Based on the same idea we can write the following property:

for any string - target
the minimal number of changes to move from the empty string to target is the number of characters of target

Indeed, if we start from the empty string, the fastest way to build target is to add all the characters of target one by one. In other words, we need at least "number of characters of target" operations.

Written with fast-check:

it("should request target.length changes to move from empty to target", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (target) => {
      // Arrange / Act
      const numChanges = minimalNumberOfChangesToBeOther("", target);

      // Assert
      expect(numChanges).toBe([...target].length);
    })
  );
});

Property 3: should request source.length changes to move from source to empty

With the same idea in mind, we can write the reversed version of the second property:

for any string - source
the minimal number of changes to move from source to the empty string is the number of characters of source

Written with fast-check:

it("should request source.length changes to move from source to empty", () => {
  fc.assert(
    fc.property(fc.fullUnicodeString(), (source) => {
      // Arrange / Act
      const numChanges = minimalNumberOfChangesToBeOther(source, "");

      // Assert
      expect(numChanges).toBe([...source].length);
    })
  );
});

Property 4: should request {start+end}.length changes to move from {start}{mid}{end} to {mid}

Just a small variation mixing a bit of the first property with the third one to make an even more generic property.

for any strings - start, mid, end
the minimal number of changes to move from start+mid+end to mid is the number of characters of start+end

Written with fast-check:

it("should request {start+end}.length changes to move from {start}{mid}{end} to {mid}", () => {
  fc.assert(
    fc.property(
      fc.fullUnicodeString(),
      fc.fullUnicodeString(),
      fc.fullUnicodeString(),
      (start, mid, end) => {
        // Arrange / Act
        const numChanges = minimalNumberOfChangesToBeOther(
          start + mid + end,
          mid
        );

        // Assert
        expect(numChanges).toBe([...(start + end)].length);
      }
    )
  );
});

While this property seems easy at first glance, it is easy to fall into traps. Properties like:

for any strings - start, mid, end
the minimal number of changes to move from start+mid to mid+end is the number of characters of start+end

Would be fully wrong. For instance it would not work for: start = mid = end = "a".

Property 5: should be independent of the ordering of the arguments

Before covering even more generic cases, we can already back us with basic mathematical properties like symmetry.

for any strings - source, target
the number of changes required to move from source to target is the same as the one required to move from target to source

Written with fast-check:

it("should be independent of the ordering of the arguments", () => {
  fc.assert(
    fc.property(
      fc.fullUnicodeString(),
      fc.fullUnicodeString(),
      (source, after) => {
        // Arrange / Act
        const numChanges = minimalNumberOfChangesToBeOther(source, target);
        const numChangesReversed = minimalNumberOfChangesToBeOther(target, source);

        // Assert
        expect(numChangesReversed).toBe(numChanges);
      }
    )
  );
});

Property 6: should compute the minimal number of changes to mutate source into target

Let's finally fully cover our algorithm with a property making us sure that the returned number of changes is the minimal one.

In order to do that check an easy trap would be to rewrite the implementation in the test but we will not do that for obvious reasons. Another solution is to have a simpler implementation of the same algorithm: most of the time this trick will be available for algorithms aiming for performances like binary searches as they could be double-checked against naive linear searches. But unfortunately we do not have that chance. The last resort is to find a way to generate our inputs differently to make us able to have some more expectations on the output.

Basically it looks similar to what we have done so far with the properties 1, 2, 3 and 4 but pushed even further. Instead of generating the string, we will generate the array of changes that can lead from the source string to the target one. While this array of changes is possibly not the smallest set of changes to move from source to target it is one of the various possibilities. In other words, our algorithm should find something with at most this number of changes.

for any set of changes (add/remove/update/no-change)
the number of changes required to move from source to target is less of equal to number of generated changes excluding no-change

Basically you can see a change as something like:

type Change =
  | { type: "no-op"; value: string }
  | { type: "new"; value: string }
  | { type: "delete"; value: string }
  | { type: "update"; from: string; to: string };

And given an array of changes we can easily build source:

function sourceFromChanges(changes: Change[]): string {
  let value = "";
  for (const c of changes) {
    if (c.type === "no-op") value += c.value;
    else if (c.type === "delete") value += c.value;
    else if (c.type === "update") value += c.from;
  }
  return value;
}

Or target:

function targetFromChanges(changes: Change[]): string {
  let value = "";
  for (const c of changes) {
    if (c.type === "no-op") value += c.value;
    else if (c.type === "new") value += c.value;
    else if (c.type === "update") value += c.to;
  }
  return value;
}

The last missing block is the arbitrary making us able to generate our changes, we can implement it as follow with fast-check:

function changeArb() {
  return fc.array(
    fc.oneof(
      fc.record<Change>({
        type: fc.constant("no-op"),
        value: fc.fullUnicode()
      }),
      fc.record<Change>({ type: fc.constant("new"), value: fc.fullUnicode() }),
      fc.record<Change>({
        type: fc.constant("delete"),
        value: fc.fullUnicode()
      }),
      fc.record<Change>({
        type: fc.constant("update"),
        from: fc.fullUnicode(),
        to: fc.fullUnicode()
      })
    ),
    { minLength: 1 }
  );
}

Now that we have all the elementary building blocks, we can write our property with fast-check:

it("should compute the minimal number of changes to mutate source into target", () => {
  fc.assert(
    fc.property(changeArb(), (changes) => {
      // Arrange
      const source = sourceFromChanges(changes);
      const target = targetFromChanges(changes);
      const requestedOperations = changes.filter((d) => d.type !== "no-op").length;

      // Act
      const numChanges = minimalNumberOfChangesToBeOther(source, target);

      // Assert
      expect(numChanges).toBeLessThanOrEqual(requestedOperations);
    })
  );
});

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.