In which I solve the Minesweeper Kata using c++0x lambdas and a little thinking outside the box (literally).

A few days ago I went to see Prepared Katas at Communities in Action, in which four guys solved minesweeper in Ruby, Perl, Java and Javascript. They had just 20 minutes to code and test, which is short even for a prepared kata. They all looked pretty stressed out, except for the Perl guy who looked smug. But that’s how they always look, isn’t it?

Anyway, I thought I’d try the kata in C++, and see if I could golf it a bit without sacrificing readability too much. I ended up solving it in 15 12 lines, expanded a bit here for readability.

I use two tricks that I should mention before I show you the code:

The first is to expand the board by one in each direction. That is, if the board is 3×3, I allocate a 5×5 scratch board. In this way, each cell can check all it’s neighbours without special handling of the edge cases.

The second trick is not really a trick, but I should mention it anyway, since most C++ developers won’t be familiar with it. I am using C++0x lambda functions, which work nicely with the normal stl algorithms.

But let’s get to the point, here’s the code:

vector<string> solve(vector<string> board) {
	int rows = board.size();
	int cols = board[0].size();
	char* big_board = static_cast<char*>(calloc((rows+2)*(cols+2), sizeof(char))); //Supersized board

	for (int r = 0; r < rows; ++r)  //Put 1 in each mine-cell
		transform(board[r].begin(), board[r].end(), &big_board[(r+1)*(cols+2)+1],
			[](char c) {return (c == '*');});

	vector<string> solution(rows);
	for (int r = 0; r < rows; ++r)  //Calculate solution
		transform(&big_board[(r+1)*(cols+2)+1], &big_board[(r+1)*(cols+2)+cols+1], back_inserter(solution[r]),
			[=](char&c){ return (c ? '*' : '0'
				+ *(&c-cols-3) + *(&c-cols-2) + *(&c-cols-1) //Previous row
				+ *(&c-1) + *(&c+1) //This row
				+ *(&c+cols+1) + *(&c+cols+2) + *(&c+cols+3));}); //Next row
	free(big_board);
	return solution;
}

Update 10 April: Thanks Mike Long for golfing off another line using calloc instead of new and fill, and having me fix the memory leak.

You need G++ 4.5 to compile this (sudo apt-get install g++-4.5). Compile with g++-4.5 -std=c++0x

I also uploaded a tarball with the full code, including unittests and a make-script, here.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.