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!

Posted on by:

## Discussion