Advent of PBT 2021 - Day 6 - Solution

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 to num/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 and simplifiedDenom 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
and factor a strictly positive integer
let's consider the simplification of the fraction: factor * num by factor * denom
we expect a simplification by at least factor

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.