Count the Divisible Numbers

Let’s try our hand at using a property test driven approach to solving a Codewars code kata. The kata we’ll be solving today is “Count the Divisible Numbers”. We’ll be solving this kata using Javascript, and using fast-check alongside Jest as our property-based testing framework.

The kata’s prompt is as follows:

Complete the [divisibleCount] function that takes 3 numbers x, y and k (where x ≤ y), and returns the number of integers within the range [x..y] (both ends included) that are divisible by k.

Writing Our Property Test

We could try to translate this prompt directly into a property test by generating three integers, x, y, and k, and verifying that the result of divisibleCount(x, y, k) matches our expected result, but we’d have to duplicate our implementation of divisibleCount to come up with that “expected result.” Who’s to say our test’s implementation wouldn’t be flawed?

We need a more obviously correct way of generating test cases.

Instead of generating three integers, x, y, and k, we’ll generate our starting point, x, the number we’re testing for divisibility, k, and the number of divisible numbers we expect in our range, n:

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      // TODO ...
    })
  );
});

Armed with x, k, and n, we can compute the end of our range, y:

let y = x + n * k;

Next, we’ll pass x, our newly commuted y, and k into divisibleCount and assert that the result matches our expected value of n:

return n === divisibleCount(x, y, k);

Our final property test looks like this:

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

Beautiful.

Our First Solution

Coming up with a solution to this problem is fairly straight-forward:

const divisibleCount = (x, y, k) => {
  return _.chain(y - x)
    .range()
    .map(n => x + n)
    .reject(n => n % k)
    .size()
    .value();
};

We generate an array of integers from x to y, reject those that aren’t divisible by k, and return the size of the resulting array.

Unfortunately, this simple solution doesn’t work as expected. Our property test reports a failing counterexample of [0, 0, 1] values for x, k, and n:

$ jest
 FAIL ./index.test.js
  ✕ it works (10ms)

  ● it works

    Property failed after 1 tests
    { seed: 1427202042, path: "0:0:0:1:0:0:0", endOnFailure: true }
    Counterexample: [0,0,1]
    Shrunk 6 time(s)
    Got error: Property failed by returning false

Looking at our solution, this makes sense. The result of n % 0 is undefined. Unfortunately, the kata doesn’t specify what the behavior of our solution should be when k equals 0, so we’re left to figure that out ourselves.

Let’s just set up a precondition in our test that k should never equal 0:

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      fc.pre(k !== 0);
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

Great!

Unfortunately, there’s another problem. Without putting an upper bound on the size of n * k, our solution will generate potentially massive arrays. This will quickly eat through the memory allocated to our process and result in a crash.

Let’s add some upper and lower bounds to our generated k and n values:

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(-100, 100), fc.nat(100), (x, k, n) => {
      fc.pre(k !== 0);
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

Perfect. Our starting integer, x, can be any positive or negative integer, but our generated values of k are clamped between -100 and 100, and n ranges from 0 to 100. These values should be large enough to thoroughly test our solution, and small enough to prevent memory issues from arising.

Our Second Solution

In hindsight, our solution seems to be making inefficient use of both time and memory. If we consider the fact that our property test is computing y in terms of x, n, and k, it stands to reason that we should be able to compute n, our desired result, in terms of x, y, and k. If we can manage this, our solution will run in both constant time and constant space.

Let’s use some algebra and work our way backwards from calculating y to calculating n. If y = x + n * k, that means that y - x = n * k. Dividing by k gives us our equation for computing n: n = (y - x) / k.

Let’s replace our original divisibleCount solution with this equation:

const divisibleCount = (x, y, k) => (y - x) / k;

And rerun our test suite:

$ jest
 PASS ./index.test.js
  ✓ it works (8ms)

  Test Suites: 1 passed, 1 total
  Tests: 1 passed, 1 total

Wonderful!