Kata: Rotate an array in place in JavaScript

Álvaro García and I were pairing yesterday after work.

We practised coding the Rotate an array in place kata in Python.

It was great fun and we discussed about naming, scaffolding tests, closures, free variables and deleting tests.

Once back at home, I redid the kata in JavaScript. You can see the resulting code in GitHub. I commited every time I got to green and after every refactoring so you can follow the process.

In this post I just want to highlight what Álvaro and I did to optimize the code a bit.

These are the tests we kept after having a first working version of the code:

	'use strict';
	var ArrayRotation = require("../src/ArrayRotation.js").ArrayRotation;
	describe("Array rotation in place", function() {
	it("An empty array does not change", function() {
	var originalArray = [];
	ArrayRotation.rotateInPlace(
	originalArray, 3
	);
	expect(originalArray).toEqual([]);
	});
	it("A rotation by 0 steps does not change the array", function() {
	var originalArray = [1, 2];
	ArrayRotation.rotateInPlace(
	originalArray, 0
	);
	expect(originalArray).toEqual([1, 2]);
	});
	it("A rotation by a number of steps that is less than the array size", function() {
	var originalArray = [1, 2, 3, 4];
	ArrayRotation.rotateInPlace(
	originalArray, 2
	);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	});
	});

view raw rotateArrayInPlaceTests1.js hosted with ❤ by GitHub

and this is the corresponding code:

	'use strict';
	var ArrayRotation = {
	rotateInPlace: function(array, steps) {
	var i, step,
	size = array.length;
	if (size === 0) {
	return;
	}
	for (step = 0; step < steps; step++) {
	for (i = 1; i < size; i++) {
	swap(0, i);
	}
	}
	function swap(position1, position2) {
	var temp = array[position1];
	array[position1] = array[position2];
	array[position2] = temp;
	}
	}
	};
	module.exports.ArrayRotation = ArrayRotation

view raw rotateArrayInPlace1.js hosted with ❤ by GitHub

This code worked also for steps greater or equal that the array size, only that in that particular case it would do more work than necessary. To avoid that extra work you just need to realize that a rotation by k steps yields the same result as a rotation by n * k steps, where n is a positive integer.

Since we were practising our TDD skills, we wanted to write first a failing test that forced us to write that optimization. Not that TDD should be used for that. It was only a way to set ourselves a tiny challenge for us to practise.

We realized that we could use an assertion on the number of calls to the swap helper to force the desired change, but first we had to make the function swap accessible from the outside:

	'use strict';
	var ArrayRotation = {
	rotateInPlace: function(array, steps) {
	var i, step,
	size = array.length;
	if (size === 0) {
	return;
	}
	for (step = 0; step < steps; step++) {
	for (i = 1; i < size; i++) {
	this.swap(array, 0, i);
	}
	}
	},
	swap: function(array, position1, position2) {
	var temp = array[position1];
	array[position1] = array[position2];
	array[position2] = temp;
	}
	};
	module.exports.ArrayRotation = ArrayRotation

view raw rotateArrayInPlace2.js hosted with ❤ by GitHub

in order to spy on it:

	'use strict';
	var ArrayRotation = require("../src/ArrayRotation.js").ArrayRotation;
	describe("Array rotation in place", function() {
	it("An empty array does not change", function() {
	var originalArray = [];
	ArrayRotation.rotateInPlace(
	originalArray, 3
	);
	expect(originalArray).toEqual([]);
	});
	it("A rotation by 0 steps does not change the array", function() {
	var originalArray = [1, 2];
	ArrayRotation.rotateInPlace(
	originalArray, 0
	);
	expect(originalArray).toEqual([1, 2]);
	});
	it("A rotation by a number of steps that is less than the array size", function() {
	var originalArray = [1, 2, 3, 4];
	ArrayRotation.rotateInPlace(
	originalArray, 2
	);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	});
	it("A rotation by a number of steps that is greater or equal than the array size", function() {
	var originalArray = [1, 2, 3, 4];
	spyOn(ArrayRotation, 'swap').andCallThrough();
	ArrayRotation.rotateInPlace(
	originalArray, 6
	);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	expect(ArrayRotation.swap.callCount).toBe(6);
	});
	});

view raw rotateArrayInPlaceTests2.js hosted with ❤ by GitHub

The last test was now failing, as we intended, for making to many calls to swap.

It took just a small change to the code to make the test pass:

	'use strict';
	var ArrayRotation = {
	rotateInPlace: function(array, steps) {
	var i, step,
	size = array.length;
	if (size === 0) {
	return;
	}
	for (step = 0; step < steps % size; step++) {
	for (i = 1; i < size; i++) {
	this.swap(array, 0, i);
	}
	}
	},
	swap: function(array, position1, position2) {
	var temp = array[position1];
	array[position1] = array[position2];
	array[position2] = temp;
	}
	};
	module.exports.ArrayRotation = ArrayRotation

view raw rotateArrayInPlace3.js hosted with ❤ by GitHub

This way we could assert that a rotation by k steps yielded the same result as a rotation by n * k steps, where n is a positive integer.

Once we had that optimization in place, we made swap private again:

	'use strict';
	var ArrayRotation = {
	rotateInPlace: function(array, steps) {
	var i, step,
	size = array.length;
	if (size === 0) {
	return;
	}
	for (step = 0; step < steps % size; step++) {
	for (i = 1; i < size; i++) {
	swap(0, i);
	}
	}
	function swap(position1, position2) {
	var temp = array[position1];
	array[position1] = array[position2];
	array[position2] = temp;
	}
	}
	};
	module.exports.ArrayRotation = ArrayRotation

view raw rotateArrayInPlace4.js hosted with ❤ by GitHub

for which we had to stop spying on it from the tests:

	'use strict';
	var ArrayRotation = require("../src/ArrayRotation.js").ArrayRotation;
	describe("Array rotation in place", function() {
	it("An empty array does not change", function() {
	var originalArray = [];
	ArrayRotation.rotateInPlace(
	originalArray, 3
	);
	expect(originalArray).toEqual([]);
	});
	it("A rotation by 0 steps does not change the array", function() {
	var originalArray = [1, 2];
	ArrayRotation.rotateInPlace(
	originalArray, 0
	);
	expect(originalArray).toEqual([1, 2]);
	});
	it("A rotation by a number of steps that is less than the array size", function() {
	var originalArray = [1, 2, 3, 4];
	ArrayRotation.rotateInPlace(
	originalArray, 2
	);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	});
	it("A rotation by a number of steps that is greater or equal than the array size", function() {
	var originalArray = [1, 2, 3, 4];
	//spyOn(ArrayRotation, 'swap').andCallThrough();
	ArrayRotation.rotateInPlace(
	originalArray, 6
	);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	// expect(ArrayRotation.swap.callCount).toBe(6);
	});
	});

view raw rotateArrayInPlaceTests3.js hosted with ❤ by GitHub

Next we examined the tests to see which ones were overlapped and could be removed. They had been useful as scaffolding to build the functionality, but once there they weren't adding much value. In our opinion keeping these scaffolding tests or not, is something that needs to be ponder in a case by case basis.

After removing those tests, I renamed the remaining tests and played a bit with augmenting the Array object prototype to finally get to the following tests:

	'use strict';
	var ArrayRotation = require('../src/ArrayRotation.js').ArrayRotation;
	Array.prototype.rotate = function(steps) {
	ArrayRotation.rotateInPlace(this, steps);
	};
	describe("Array rotation in place", function() {
	it("A rotation by any number of steps on an empty array has no effect", function() {
	var originalArray = [];
	originalArray.rotate(3);
	expect(originalArray).toEqual([]);
	});
	it("A rotation by 0 steps on a non-empty array has no effect", function() {
	var originalArray = [1, 2];
	originalArray.rotate(0);
	expect(originalArray).toEqual([1, 2]);
	});
	it("A rotation by non-zero steps on a non-empty array works as expected", function() {
	var originalArray = [1, 2, 3, 4];
	originalArray.rotate(6);
	expect(originalArray).toEqual([3, 4, 1, 2]);
	});
	});

view raw rotateArrayInPlaceTests4.js hosted with ❤ by GitHub

I think that although this kata is very simple, you can make a lot from it and have fun.

Thanks Álvaro for the great pairing experience, I hope we'll go on having fun with other katas.