Our algorithm was: simplifyFraction.
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-6-solution-fwuln?file=/src/index.spec.ts&previewwindow=tests
Property 1: should simplify any fraction to a fraction having the same result
The first requirement of any algorithm doing simplification is that the simplified version behaves as the original one. In other words:
for any numerator -
num
- and denominator -denom
- integers
with denominator different from 0
simplifiedNum/simplifiedDenom
should be equal tonum/denom
Written with fast-check:
it("should simplify any fraction to a fraction having the same result", () => {
fc.assert(
fc.property(
fc.integer(),
fc.integer().filter((n) => n !== 0),
(numerator, denominator) => {
const fSource = { numerator, denominator };
const fOut = simplifyFraction(fSource);
expect(fOut.numerator / fOut.denominator).toEqual(
fSource.numerator / fSource.denominator
);
}
)
);
});
While this property is central to an algorithm dealing with simplification it does not prove that the algorithm even tried to simplify anything. A simple implementation like:
function simplifyFraction(f: Fraction): Fraction {
return f;
}
Would pass the property.
Property 2: should always return a simplified fraction having a positive denominator
Before assessing that the algorithm really tried to simplify the fraction let's check some characteristics we expect to see on the output.
for any numerator -
num
- and denominator -denom
- integers
with denominator different from 0
simplifiedDenom
should be positive
Written with fast-check:
it("should always return a simplified fraction having a positive denominator", () => {
fc.assert(
fc.property(
fc.integer(),
fc.integer().filter((n) => n !== 0),
(numerator, denominator) => {
const fSource = { numerator, denominator };
const fOut = simplifyFraction(fSource);
expect(fOut.denominator).toBeGreaterThan(0);
}
)
);
});
Property 3: should only produce integer values for the numerator and denominator
for any numerator -
num
- and denominator -denom
- integers
with denominator different from 0
simplifiedNum
andsimplifiedDenom
should be integers
Written with fast-check:
it("should only produce integer values for the numerator and denominator", () => {
fc.assert(
fc.property(
fc.integer(),
fc.integer().filter((n) => n !== 0),
(numerator, denominator) => {
const fSource = { numerator, denominator };
const fOut = simplifyFraction(fSource);
expect(Number.isInteger(fOut.numerator)).toBe(true);
expect(Number.isInteger(fOut.denominator)).toBe(true);
}
)
);
});
Even with that three properties, it is trivial to by-pass the tests with a non-working implementation like:
function simplifyFraction(f: Fraction): Fraction {
if (f.denominator < 0) {
return {
numerator: -f.numerator,
denominator: -f.denominator
};
}
return f;
}
So we really have to assess this simplification part.
Property 4: should only produce integer values for the numerator and denominator
Checking that a simplification algorithm does what it should do is often a trap.
Indeed it is easy to rewrite the implementation in the property itself. In other words, it is easy to check "is my code ok with itself". While from time to time it could be the solution because we have a way to write a non optimized version with a really straightforward implementation, most of the time you should find another way round.
A common pattern for such problems is to build entries we fully know, so that we know we can expect some simplifications for them.
for any numerator -
num
- and denominator -denom
- integers
with denominator different from 0
andfactor
a strictly positive integer
let's consider the simplification of the fraction:factor * num
byfactor * denom
we expect a simplification by at leastfactor
With such property we don't check that the algorithm gives the simplest form for factor * num
by factor * denom
but that at least it gives something simplified by factor
.
Written with fast-check:
it("should simplify fractions to simpler form whenever possible", () => {
fc.assert(
fc.property(
fc.integer(),
fc.integer().filter((n) => n !== 0),
fc.integer({ min: 1 }),
(smallNumerator, smallDenominator, factor) => {
fc.pre(Math.abs(smallNumerator * factor) <= Number.MAX_SAFE_INTEGER);
fc.pre(Math.abs(smallDenominator * factor) <= Number.MAX_SAFE_INTEGER);
const fSource = {
numerator: smallNumerator * factor,
denominator: smallDenominator * factor
};
const fOut = simplifyFraction(fSource);
const simplifiedByFactor = Math.abs(
fSource.denominator / fOut.denominator
);
expect(simplifiedByFactor).toBeGreaterThanOrEqual(factor);
}
)
);
});
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)