Advent of PBT 2021 - Day 23 - Solution

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

---

Property 1: should be able to rebuild previous year given only the diff

for any wish lists:

• one for previous year
• one for current year

it should be able to rebuild the previous year's wish list just based on the diff

Indeed given a diff like:

=== Cars
+++ Buses
=== Trains
+++ Boats
--- Planes

It is pretty easy to find back the wish list used for the previous year as it corresponds to any line starting by --- or ===.

In terms of code, it can be done with:

function previousYearFromDiff(diff: string): string {
  return diff
    .split("\n")
    .filter((line) => line.startsWith("--- ") || line.startsWith("=== "))
    .map((line) => line.substring(4))
    .join("\n");
}

We also need a way to generate wish lists with fast-check. Here is a way to write such arbitrary:

function stringSingleLine() {
  return fc.stringOf(fc.fullUnicode().filter((c) => c !== "\n"));
}
function wishListArbitrary() {
  return fc.array(stringSingleLine()).map((lines) => lines.join("\n"));
}

Now everything is ready, we can go back to our property:

for any wish lists:

• one for previous year
• one for current year

it should be able to rebuild the previous year's wish list just based on the diff

Written with fast-check:

it("should be able to rebuild previous year given only the diff", () => {
  fc.assert(
    fc.property(
      wishListArbitrary(),
      wishListArbitrary(),
      (previousYear, currentYear) => {
        // Arrange / Act
        const computedDiff = wishListsDiffer(previousYear, currentYear);

        // Assert
        expect(previousYearFromDiff(computedDiff)).toEqual(previousYear);
      }
    )
  );
});

---

Property 2: should be able to rebuild current year given only the diff

for any wish lists:

• one for previous year
• one for current year

it should be able to rebuild the current year's wish list just based on the diff

Written with fast-check:

it("should be able to rebuild current year given only the diff", () => {
  fc.assert(
    fc.property(
      wishListArbitrary(),
      wishListArbitrary(),
      (previousYear, currentYear) => {
        // Arrange / Act
        const computedDiff = wishListsDiffer(previousYear, currentYear);

        // Assert
        expect(currentYearFromDiff(computedDiff)).toEqual(currentYear);
      }
    )
  );
});

---

Property 3: should compute the diff having the maximal number of unchanged lines

for any wish lists:

• one for previous year
• one for current year

extracted from a known diff
it should compute a diff at least as good as the original one

In order to write down this property with fast-check we first of all need an arbitrary to generate some diffs:

function diffArbitrary() {
  return fc
    .array(
      fc
        .record({
          type: fc.constantFrom("+++", "---", "==="),
          content: stringSingleLine()
        })
        .map(({ type, content }) => `${type} ${content}`),
      { minLength: 1 }
    )
    .map((lines) => lines.join("\n"));
}

Now that we have such arbitrary we have to define "at least as good as the original one" in the code. In the case of our differ the target is to maximize the number of lines marked with "===". In other words, make the number of unchanged lines as large as possible. So we will need an helper to count them.

function countUnchangedLines(diff: string): number {
  return diff.split("\n").filter((line) => line.startsWith("=== ")).length;
}

Now let's move back to our property:

for any wish lists:

• one for previous year
• one for current year

extracted from a known diff
it should compute a diff at least as good as the original one

Written with fast-check:

it("should compute the diff having the maximal number of unchanged lines", () => {
  fc.assert(
    fc.property(diffArbitrary(), (diff) => {
      // Arrange
      const previousYear = previousYearFromDiff(diff);
      const currentYear = currentYearFromDiff(diff);

      // Act
      const computedDiff = wishListsDiffer(previousYear, currentYear);

      // Assert
      expect(countUnchangedLines(computedDiff)).toBeGreaterThanOrEqual(
        countUnchangedLines(diff)
      );
    })
  );
});

---

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.