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.
Top comments (0)