Advent of PBT 2021 - Day 23 - Solution
source link: https://dev.to/dubzzz/advent-of-pbt-2021-day-23-solution-4lg4
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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
Enter fullscreen mode
Exit fullscreen mode
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");
}
Enter fullscreen mode
Exit fullscreen mode
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"));
}
Enter fullscreen mode
Exit fullscreen mode
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);
}
)
);
});
Enter fullscreen mode
Exit fullscreen mode
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);
}
)
);
});
Enter fullscreen mode
Exit fullscreen mode
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"));
}
Enter fullscreen mode
Exit fullscreen mode
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;
}
Enter fullscreen mode
Exit fullscreen mode
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)
);
})
);
});
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK