5 lessons learned when I TDD an algorithm in JavaScript

How to develop an algorithm using TDD? In this article we will implement the Diamond-Square algorithm using TDD. This article was inspired by Uncle Bob’s blog post TDD Lesson – Terrain Generation.

Well, one of the things I did during the summer was to write an article about “How to Create Terrain and Heightmaps using the Diamond-Square Algorithm in JavaScript?“.

I just found out that Uncle Bob wrote an article about TDDing the Diamond Square algorithm (yea, I’m slow on catching up sometimes).

In the article, Uncle Bob leads us through a way to TDD an algorithm. It’s pretty nice and gave me a few insights as to how to mock and test in intervals until the algorithm emerges.

Problem is – Uncle Bob’s code is not JavaScript!!!

So I set down and reimplemented the algorithm. This time, I used the lessons learned from Uncle Bob’s article.

What did I learn while developing an algorithm using TDD in JavaScript?

Lesson #1: Start with the simplest test possible

In his article, Uncle Bob starts by testing input validation. That seems too simple, but I find this simplicity charming. We use to neglect input validation until we finish writing the code (if ever). Testing input validation? Most people don’t do that.

Starting with input validation is a kind of “warmup” to the real thing. I really suggest doing it. It takes a minute (or less) and is worth it. Here’s my input validation test:

Input validation tests. This begins the TDD of the algorithm.

Lesson #2: Mock for stability

Many algorithms have a random factor. The Diamond-Square algorithm has a random factor in the tile value calculation. On every such calculation, we calculate the mean of surrounding tiles and add some random number to make things interesting.

A random factor is not so good for tests. Unit tests need to be stable and that means that every function return should be predictable.

In some cases, using Math.random is enough. In these cases, we can stub Math.random to return a constant value for our tests.

There are other cases (like our algorithm) in which the randomness is a bit more complex. In this case, writing a function or a method to generate this randomness is a good practice.

We first create this function:

it(`should generate a random number that is multiplied by 2 in the power 0 to -0.1`, function () {
        diamondSquare.generateRandom.mockRestore();

        jest.spyOn(Math, 'random').mockReturnValue(1);
        const randomFactorWithOne = diamondSquare.generateRandom(1);

        jest.spyOn(Math, 'random').mockReturnValue(.1);
        const randomFactorWithTenth = diamondSquare.generateRandom(1);

        expect(randomFactorWithOne).toEqual(Math.pow(2, -.1));
        expect(randomFactorWithTenth).toEqual(Math.pow(2, .1*-0.1));
    });

Then we can mock it to get a constant “random” value in our test:

jest.spyOn(diamondSquare, 'generateRandom').mockReturnValue(1);

This magic line above mocked the generateRandom method and always returned the value 1.

Lesson #3: Track your state with a string

Algorithms can become very complex. They usually iterate a lot on the data, and tracking the steps can become difficult. What Uncle Bob suggests is to stub some functions to track the steps using a string and create sequences that are easy to follow:

const sequence = `diamondStep ${[1,2,3,4].reduce((v) => v += 'squareStep ', '')}`
const expectedSequence = `${[1,2,3,4,5].reduce(v => v += sequence, '')}`;
let output = '';
jest.spyOn(diamondSquare, 'diamondStep').mockImplementation(() => {
output += 'diamondStep ';
});
jest.spyOn(diamondSquare, 'squareStep').mockImplementation(() => {
output += 'squareStep ';
});
diamondSquare.createHeightMap(5);
expect(output).toEqual(expectedSequence);
Tracking the algorithm’s steps by stubbing the steps methods and concatenating the steps in a string. Then, we just expect the steps to be a human readable string.

In the Diamond-Square algorithm we know we need to have a certain sequence of steps. We’d expect on every iteration to calculate 4 squares for every diamond. So in a 3×3 matrix we will have something like this:

diamondStep squareStep squareStep squareStep squareStep 

In a 5×5 matrix, we have 5 diamonds, so we will expect to have the following sequence:

diamondStep squareStep squareStep squareStep squareStep diamondStep squareStep squareStep squareStep squareStep diamondStep squareStep squareStep squareStep squareStep diamondStep squareStep squareStep squareStep squareStep diamondStep squareStep squareStep squareStep squareStep

So if something goes wrong, the testing framework (Jest, in my case) will be very useful in guiding me what’s missing:

Missing steps in the diamond-square sequence for 5×5 matrix

I smacked my head when I read it. It reminded me “time travel” in redux and I wondered how I didn’t use this trick before.

Note that this is not always possible, because your step functions might not be be exposed from the module. The next lesson will show you a way to do it if you are OOPing.

Lesson #4: Inheritance can be very useful for testing

If you are using OOP, you just got lucky. You can create a test class that extends your original class. This allows you to mock even without a testing framework:

// in diamond.square.js
class DiamondSquare {
diamondStep() {
//logic
}
squareStep() {
//logic
}
}
// in diamond.square.spec.js
class DiamondSquareUnderTest extends DiamondSquare {
diamondStep() {
super.diamondStep();
return 'diamondStep';
}
squareStep() {
super.squareStep();
return 'squareStep';
}
}
Using inheritance to mock our step methods by overriding them.

While I didn’t use the full power of OOP in the actual reproduction of the algorithm, this is a nice trick that might come in handy in the future.

Lesson #5: Avoid the “Holy Grail” test until the end

The “Holy Grail” is a term that is used to describe the end result of our algorithm or module or function.

By starting with the Holy Grail, we can really fast hit a wall. The algorithm is quite complex and the results are somewhat hard to calculate. Especially in JavaScript, where the floating numbers returned from a calculation can be quirky.

Here’s my “Holy Grail” test:

The “Holy Grail” test reduced to just running the complete function and taking a snapshot. Then I just look at the snapshot and see that the calculation is correct.

Summary

I love TDD. I believe it improves my developing experience by simplifying big tasks.

The idea is to build incrementally. Start from the simplest (the first lesson learned here) and move on to the “Holy Grail” that will emerge from the simpler tests.

As Uncle Bob himself suggests in the article – do try this at home.

For those of you who are interested, here’s the full solution:

function powerOfTwo(x) {
return Math.log2(x) % 1 === 0;
}
module.exports = class DiamondSquare {
createHeightMap(matrixSize) {
if (matrixSize <= 2) {
throw `Matrix Cannot be smaller than 3. Received ${matrixSize}`;
}
if (!powerOfTwo(matrixSize – 1)) {
throw `Matrix size must be 2^n+1. Received ${matrixSize}`;
}
const matrix = this.createStartingMatrix(matrixSize);
const randomFactor = Math.round(Math.random() * 5);
let size = matrixSize – 1;
while (size > 1) {
const middle = size/2;
for (let i = middle; i < matrixSize – 1; i += size) {
for (let j = middle; j < matrixSize – 1; j += size) {
matrix[i][j] = this.diamondStep(matrix, i, j, middle) + this.generateRandom(randomFactor);
//left
matrix[i][j – middle] = this.squareStep(matrix, i, j – middle, middle) + this.generateRandom(randomFactor);
// top
matrix[i – middle][j] = this.squareStep(matrix, i – middle, j, middle) + this.generateRandom(randomFactor);
// bottom
matrix[i + middle][j] = this.squareStep(matrix, i + middle, j, middle) + this.generateRandom(randomFactor);
// right
matrix[i][j + middle] = this.squareStep(matrix, i, j + middle, middle) + this.generateRandom(randomFactor);
}
}
size /= 2;
}
return matrix;
}
createStartingMatrix(matrixSize) {
const newArray = new Array(matrixSize)
.fill(0)
.map((val, ui) => new Array(matrixSize))
newArray[0][0] = Math.floor(Math.random() * 10);
newArray[0][matrixSize – 1] = Math.floor(Math.random() * 10);
newArray[matrixSize – 1][0] = Math.floor(Math.random() * 10);
newArray[matrixSize – 1][matrixSize – 1] = Math.floor(Math.random() * 10);
return newArray;
}
generateRandom(random) {
const h = Math.random() * -.1;
return random * Math.pow(2, h);
}
diamondStep(matrix, x, y, middle) {
function safeMatrixMember(x1, y1) {
if (matrix[x1] === undefined || matrix[x1][y1] === undefined) {
meanMembers -= 1;
return 0;
}
return matrix[x1][y1];
}
let meanMembers = 4;
meanMembers = 4;
return (safeMatrixMember(x + middle, y – middle) +
safeMatrixMember(x + middle, y + middle) +
safeMatrixMember(x – middle, y – middle) +
safeMatrixMember(x – middle, y + middle)) / meanMembers;
}
squareStep(matrix, x, y, middle) {
function safeMatrixMember(x, y) {
if (matrix[x] === undefined || matrix[x][y] === undefined) {
meanMembers -= 1;
return 0;
}
return matrix[x][y];
}
let meanMembers = 4;
return (safeMatrixMember(x – middle, y) +
safeMatrixMember(x + middle, y) +
safeMatrixMember(x, y – middle) +
safeMatrixMember(x, y + middle)) / meanMembers;
}
}
const DiamondSquare = require('./diamond.square');
describe(`diamond square`, function () {
let diamondSquare, dummyMatrix3, dummyMatrix5, dummyMatrix;
beforeEach(function () {
diamondSquare = new DiamondSquare();
dummyMatrix3 = [
[1, undefined, 2],
[undefined, undefined, undefined],
[4, undefined, 3],
];
dummyMatrix5 = [
[1, undefined, undefined, undefined, 2],
[undefined, undefined, undefined, undefined, undefined],
[undefined, undefined, undefined, undefined, undefined],
[undefined, undefined, undefined, undefined, undefined],
[4, undefined, undefined, undefined, 5],
];
jest.spyOn(diamondSquare, 'createStartingMatrix').mockImplementation(() => dummyMatrix);
jest.spyOn(diamondSquare, 'generateRandom').mockReturnValue(1);
});
it(`should throw if matrix of size less than 3`, function () {
expect(() => diamondSquare.createHeightMap(0)).toThrow(`Matrix Cannot be smaller than 3. Received 0`);
expect(() => diamondSquare.createHeightMap(1)).toThrow(`Matrix Cannot be smaller than 3. Received 1`);
expect(() => diamondSquare.createHeightMap(2)).toThrow(`Matrix Cannot be smaller than 3. Received 2`);
});
it(`should accept only matrix of size 2^n+1`, function () {
expect(() => diamondSquare.createHeightMap(3)).not.toThrow(`Matrix size must be 2^n+1. Received 3`);
expect(() => diamondSquare.createHeightMap(5)).not.toThrow(`Matrix size must be 2^n+1. Received 5`);
expect(() => diamondSquare.createHeightMap(17)).not.toThrow(`Matrix size must be 2^n+1. Received 17`);
expect(() => diamondSquare.createHeightMap(4)).toThrow(`Matrix size must be 2^n+1. Received 4`);
expect(() => diamondSquare.createHeightMap(8)).toThrow(`Matrix size must be 2^n+1. Received 8`);
expect(() => diamondSquare.createHeightMap(19)).toThrow(`Matrix size must be 2^n+1. Received 19`);
});
it(`should return a matrix of given size`, function () {
diamondSquare.createStartingMatrix.mockRestore();
const heightMap3 = diamondSquare.createHeightMap(3);
const heightMap5 = diamondSquare.createHeightMap(5);
const heightMap17 = diamondSquare.createHeightMap(17);
const heightMap3HasThreeColumns = heightMap3.every((row) => row.length === 3);
const heightMap5HasFiveColumns = heightMap5.every((row) => row.length === 5);
const heightMap17HasSeventeenColumns = heightMap17.every((row) => row.length === 17);
expect(heightMap3.length).toEqual(3);
expect(heightMap3HasThreeColumns).toEqual(true);
expect(heightMap5.length).toEqual(5);
expect(heightMap5HasFiveColumns).toEqual(true);
expect(heightMap17.length).toEqual(17);
expect(heightMap17HasSeventeenColumns).toEqual(true);
});
it(`should generate a random number that is multiplied by 2 in the power 0 to -0.1`, function () {
diamondSquare.generateRandom.mockRestore();
jest.spyOn(Math, 'random').mockReturnValue(1);
const randomFactorWithOne = diamondSquare.generateRandom(1);
jest.spyOn(Math, 'random').mockReturnValue(.1);
const randomFactorWithTenth = diamondSquare.generateRandom(1);
expect(randomFactorWithOne).toEqual(Math.pow(2, -.1));
expect(randomFactorWithTenth).toEqual(Math.pow(2, .1*-0.1));
});
it(`should calculate the center of a matrix correctly`, function () {
dummyMatrix = dummyMatrix3;
const heightMap3 = diamondSquare.createHeightMap(3);
dummyMatrix = dummyMatrix5;
const heightMap5 = diamondSquare.createHeightMap(5);
expect(heightMap3[1][1]).toEqual(2.5 + 1);
expect(heightMap5[2][2]).toEqual(3 + 1);
});
it(`should calculate the square correctly`, function () {
jest.spyOn(diamondSquare, 'createStartingMatrix').mockImplementation(() => dummyMatrix);
jest.spyOn(diamondSquare, 'generateRandom').mockReturnValue(1);
dummyMatrix = dummyMatrix3;
const heightMap3 = diamondSquare.createHeightMap(3);
dummyMatrix = dummyMatrix5;
const heightMap5 = diamondSquare.createHeightMap(5);
expect(heightMap3[0][1]).toEqual(6.5 / 3 + 1);
expect(heightMap3[1][0]).toEqual(8.5 / 3 + 1);
expect(heightMap3[2][1]).toEqual(10.5 / 3 + 1);
expect(heightMap3[1][2]).toEqual(8.5 / 3 + 1);
expect(heightMap5[0][2]).toEqual(7/3 + 1);
expect(heightMap5[2][0]).toEqual(4);
expect(heightMap5[4][2]).toEqual(13/3 + 1);
expect(heightMap5[2][4]).toEqual(11/3 + 1);
});
it(`should run diamond-square sequences`, function () {
dummyMatrix = dummyMatrix5;
const sequence = `diamondStep ${[1,2,3,4].reduce((v) => v += 'squareStep ', '')}`
const expectedSequence = `${[1,2,3,4,5].reduce(v => v += sequence, '')}`;
let output = '';
jest.spyOn(diamondSquare, 'diamondStep').mockImplementation(() => {
output += 'diamondStep ';
});
jest.spyOn(diamondSquare, 'squareStep').mockImplementation(() => {
output += 'squareStep ';
});
diamondSquare.createHeightMap(5);
expect(output).toEqual(expectedSequence);
});
it(`should do a diamond-square sequence`, function () {
dummyMatrix = dummyMatrix5;
const heightMap5 = diamondSquare.createHeightMap(5);
expect(heightMap5).toMatchSnapshot();
});
});
The diamond square algorithm and its test. The tests came first šŸ˜‰

Thanks a lot to Hod Bauer and Yair Cohen for the kind and thorough review.

Featured Photo by Paul Gilmore on Unsplash

0 0 votes
Article Rating
Subscribe
Notify of
guest

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments