The Minesweeper Kata in 15 lines of C++


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.

4 Responses to “The Minesweeper Kata in 15 lines of C++”

  1. faizi Says:

    plzzzzz send me the code of minesweeper in c++ language using if else,loops,arrays and function………..please

    • Anders Schau Knatten Says:

      Hi faizi, this _is_ the code of minesweeper in the c++ language, using if else, loops, arrays and a function. Although you don’t see the “if” keyword anywhere, I am using the ternary operator, which is just a shorthand for an if-statement. Instead of writing

      if (c) return ‘*’ else return ‘0’

      You can write

      return (c ? ‘*’ : ‘0’)

      Read more at http://en.wikipedia.org/wiki/%3F:

  2. awhan Says:

    thanks for this … but i have lots of questions to bother u with … the first of which is
    would u mind providing your original code and then the improved code? i m wondering why u chose calloc over vector?

    i love this style of teaching … small targetted examples .. many times when i see lots and lots of words my almost dyslexic brain goes numb. i hope to learn a lot from this blog!

    • Anders Schau Knatten Says:

      Hi awhan, I am happy you enjoy my blog!

      I never used a vector for the big_board variable. I just changed from allocating the memory with new and then filling with zeroes, to allocating with calloc which automatically initializes with zeroes. I hope that answers your question?

      Sorry for the late reply by the way, I was away on vacation.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: