Kata: Find indexes of all upper-case letters in a word

Last Friday I went to a kata of Barcelona Software Craftsmanship facilitated by Carlos Blé at Runroom.

We had to write a function using TDD that when given a word will produce an array containing the positions of all the capital letters in the word.

The most interesting part of the exercise came during the second interaction in which we had the constraint of not mutating any value.

Although we didn't managed to finish the exercise, we had a very interesting debate about recursion, baby steps and TDD.

Once back at home I started to grow the code again in tiny steps, trying to make explicit the problem patterns before taking the leap of faith of recursion.

This is the code passing all the tests right before being refactored to be recursive:

	'use strict';
	function findCapitalLetterPositions(word) {
	var res = [];
	if(word.length === 0) {
	return res;
	}
	if(isUpperCase(word[0])) {
	res = res.concat([0]);
	}
	if (word.length == 1) {
	return res;
	}
	if(isUpperCase(word[1])) {
	res = res.concat([1]);
	}
	return res;
	}
	function isUpperCase(letter) {
	return letter.toUpperCase() == letter[0];
	}
	describe("Upper case letters finder", function() {
	it("an empty word contains no capital letters", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("finds the index of a word with one letter that is upper case", function() {
	expect(findCapitalLetterPositions("A")).toEqual([0]);
	});
	it("produces no index for a one letter word containing no capital letters", function() {
	expect(findCapitalLetterPositions("a")).toEqual([]);
	});
	it("produces the index of a capital letter not at the beginning of the word", function() {
	expect(findCapitalLetterPositions("aA")).toEqual([1]);
	});
	it("produces the indexes of a two capital letters word", function() {
	expect(findCapitalLetterPositions("BA")).toEqual([0,1]);
	});
	});

view raw findCapitalLetterPositionsBeforeRecursion.js hosted with ❤ by GitHub

In the repetition that existed in this code, it was possible to see two emerging patterns:

1. The base case of the recursion which happens when the word length is equal to the current index.
2. The use of concat to make the result grow when the character at the current index is a capital letter

Using that information I refactored the code to get to this recursive solution, (after a pair of failed attempts...):

	'use strict';
	function findCapitalLetterPositions(word) {
	return f(word, 0);
	function f(word, index) {
	if(word.length == index) {
	return [];
	}
	if(isUpperCase(word[index])) {
	return [index].concat(f(word, index + 1));
	}
	return f(word, index + 1);
	}
	}
	function isUpperCase(letter) {
	return letter.toUpperCase() == letter[0];
	}
	describe("Upper case letters finder", function() {
	it("an empty word contains no capital letters", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("finds the index of a word with one letter that is upper case", function() {
	expect(findCapitalLetterPositions("A")).toEqual([0]);
	});
	it("produces no index for a one letter word containing no capital letters", function() {
	expect(findCapitalLetterPositions("a")).toEqual([]);
	});
	it("produces the index of a capital letter not at the beginning of the word", function() {
	expect(findCapitalLetterPositions("aA")).toEqual([1]);
	});
	it("produces the indexes of a two capital letters word", function() {
	expect(findCapitalLetterPositions("BA")).toEqual([0,1]);
	});
	});

view raw findCapitalLetterPositionsRecursion.js hosted with ❤ by GitHub

In it you can still distinguish the similarities with the previous non-recursive version.

The base case now returns an empty array and concat is used again when a capital letter is found at the current index, only that the concatenation is now with a one-element list containing the current index.

In any other case, no element is concatenated to the result and the function is called again with the next index.

Later, I refactored the code and the tests a bit more to get to these final versions of the tests:

	'use strict';
	var findCapitalLetterPositions = require('./UpperCaseFinder.js').findCapitalLetterPositions;
	describe("Upper case letters finder", function() {
	it("produces no index for an empty word", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("produces the indexes of capital letters in a word", function() {
	expect(findCapitalLetterPositions("BAsrwQMPaZ")).toEqual([0, 1, 5, 6, 7, 9]);
	});
	it("ignores characters that are not letters", function() {
	expect(findCapitalLetterPositions("3As5wQ6PaZ")).toEqual([1, 5, 7, 9]);
	});
	});

view raw findCapitalLetterPositionsRecursiveTests.js hosted with ❤ by GitHub

and the code:

	'use strict';
	function findCapitalLetterPositions(word, index) {
	if (index === undefined) {
	return findCapitalLetterPositions(word, 0);
	}
	if (word.length == index) {
	return [];
	}
	if (isNotLetter(word[index]) || isNotUpperCase(word[index])) {
	return findCapitalLetterPositions(word, index + 1);
	}
	return [index].concat(
	findCapitalLetterPositions(word, index + 1)
	);
	function isNotUpperCase(letter) {
	return letter.toUpperCase() != letter[0];
	}
	function isNotLetter(char) {
	return !char.match(/[a-z]/i);;
	}
	}
	module.exports.findCapitalLetterPositions = findCapitalLetterPositions

view raw findCapitalLetterPositionsRecursive.js hosted with ❤ by GitHub

You can check the code in this GitHub repository.

All in all, I'm under the impression that I wrote the before-recursion code that way because I already had an insight of how the recursive solution was going to be.

Had I written it in a different way, might it have made more difficult to find a recursive solution?
What would have happened with a more difficult problem?

I'm not sure if TDD alone will help me to find recursive solutions.

I will keep working on it.