DEV Community is a community of 783,060 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Nicolas DUBIEN

Posted on • Updated on

Advent of PBT 2021 - Day 2 - Solution

Our algorithm was: decomposeIntoPrimes.
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-2-solution-n4nxq?file=/src/index.spec.ts&previewwindow=tests

Property 1: should only produce integer values in [2, 2**31-1] for factors

This property is mostly a sanity check to avoid having a decomposition like: 9 = 4.5 * 2

for any n, integer in [2, 2**31-1]
the factors should be integer values in [2, 2**31-1]

Written with fast-check:

it("should only produce integer values in [2, 2**31-1] for factors", () => {
fc.assert(
fc.property(fc.integer({ min: 2, max: 2 ** 31 - 1 }), (n) => {
const factors = decomposeIntoPrimes(n);
for (const factor of factors) {
expect(Number.isInteger(factor)).toBe(true);
expect(factor).toBeGreaterThanOrEqual(2);
expect(factor).toBeLessThanOrEqual(2 ** 31 - 1);
}
})
);
});

Property 2: should produce an array such that the product equals the input

The second thing we want to check is that the decomposition is correct. In other words: the product of all the returned factors equals our inputted value.

for any n, integer in [2, 2**31-1]
the product of all the factors in the proposed decomposition
is equal to n

Written with fast-check:

it("should produce an array such that the product equals the input", () => {
fc.assert(
fc.property(fc.integer({ min: 2, max: 2 ** 31 - 1 }), (n) => {
const factors = decomposeIntoPrimes(n);
const productOfFactors = factors.reduce((a, b) => a * b, 1);
return productOfFactors === n;
})
);
});

Property 3: should be able to decompose a product of two numbers

The third thing we want to assess is the ability to detect a non-prime number and express it in terms of multiple factors.

for any a and b integers in [2, 2**31-1]
such as a * b is in [2, 2**31-1]
the number of factors in the decomposition of a * b
should be greater than or equal to 2

Written with fast-check:

it("should be able to decompose a product of two numbers", () => {
fc.assert(
fc.property(
fc.integer({ min: 2, max: 2 ** 31 - 1 }),
fc.integer({ min: 2, max: 2 ** 31 - 1 }),
(a, b) => {
const n = a * b;
fc.pre(n <= 2 ** 31 - 1);
const factors = decomposeIntoPrimes(n);
return factors.length >= 2;
}
)
);
});

Property 4: should compute the same factors as to the concatenation of the one of a and b for a times b

And our last property will just confirm that the decomposition of a * b is just the result of the concatenation of the one for a to the one for b.

for any a and b integers in [2, 2**31-1]
the decomposition of a * b into prime factors
should be equal to the concatenation of the one for a to the one for b

Written with fast-check:

it("should compute the same factors as to the concatenation of the one of a and b for a times b", () => {
fc.assert(
fc.property(
fc.integer({ min: 2, max: 2 ** 31 - 1 }),
fc.integer({ min: 2, max: 2 ** 31 - 1 }),
(a, b) => {
fc.pre(a * b <= 2 ** 31 - 1);
const factorsA = decomposeIntoPrimes(a);
const factorsB = decomposeIntoPrimes(b);
const factorsAB = decomposeIntoPrimes(a * b);
expect(sorted(factorsAB)).toEqual(sorted([...factorsA, ...factorsB]));
}
)
);
});

Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.