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.

Uniform Initialization Simplifies Testing


In which I demonstrate the use of uniform initialization, and show how it is particularly well suited to unit tests.

In C++0x, there is Yet Another Way to initialize objects, using the {} syntax (uniform initialization). Except, it isn’t really new, it’s the way we’ve always been initializing arrays and structs:

int i[] = {1,4,9};

The difference is we can now use this syntax to initialize any object. Why does this matter, and what is wrong with the old constructor syntax? Nothing is wrong with it in fact, and it will still see a lot of use. But in some cases, {} leads to simpler and easier code.

One area in particular is initialization of containers. It was always a bit of a hassle to initialize for instance a vector, where you would need to do something like this:

    string a[] = {"foo", "bar"};
    vector<string> v(a, a+2);

In C++0x however, you can do

    vector<string> v = {"foo", "bar"};

One area where I find myself initializing containers manually a lot is in unit tests. Here is an example:

#include <gtest/gtest.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int count_sheep(const vector<string>& animals) {
    return count(animals.begin(), animals.end(), "sheep");
}

TEST(TestCountSheep, returns_zero_when_there_are_no_sheep) {
    ASSERT_EQ(0, count_sheep({"pig", "cow", "giraffe"})); //here
}

TEST(TestCountSheep, returns_all_sheep) {
    ASSERT_EQ(2, count_sheep({"sheep", "cow", "sheep"})); //and here
}

Note the calls to count_sheep(), where the container is declared and initialized in line, without any mention of string, vector or temporary arrays!

To compile this, you need g++ 4.5 (sudo apt-get install g++-4.5). It might also be possible in Visual Studio 2010 if you are so inclined. This example also uses the Google C++ Testing Framework (sudo apt-get install libgtest-dev). Here is the full command to compile and run the example:

g++-4.5 * -std=c++0x -lgtest_main -lgtest -lpthread && ./a.out

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

C++0x highlights #0: Range Based For Loop


Herb Sutter has some good news, C++0x looks like it could end up as C++11! This is going to be a great update to the C++ language. Lots of advanced features, like closures, a new memory model, portable threading support etc., are coming, but I think the one that I miss most often is the really simple Range Based For Loop (especially combined with Type Inference).

The following for loop:

map<SomeClass, vector> someclass_strings_map;
for (map<SomeClass, vector>::const_iterator it = someclass_strings_map.begin();
    it != someclass_strings_map.end(); ++it) {
    do_something_with(it->second);
}

is one of the reasons the Python, Ruby (and Java since 1.5) people laugh at us. But next year, we will be able to do:

for (auto x : foo_strings_map) {
        do_something_with(x.second);
}

PS: while I was compiling this example, I remembered another tiny improvement, you can now do map<Foo, vector<string>>. Notice the missing space? C++ no longer confuses nested templates with the shift/stream operator. Currently, you need an extra space: map<Foo, vector<string> >

PPS: If do_something_with() is a simple function this could be done with a for_each and a lambda/closure, but that is another story.

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