How to unit testing non-deterministic code

A few weeks back in our weekly coding kata we attempted the minesweeper challenge. (Coding Katas are quick training coding sessions). We created a few methods to create a board, add the right number of mines etc. We reached a point which we had to shuffle the board, so how do we test that the shuffling actually happened. Someone suggested that we can generate 2 shuffled boards and simply compare them, the problem with that approach is that there is always the probability that the test will fail intermittently. We could make the boards massive like 1000×1000 so even with a single mine, the test will fail once every 1 000 000 runs, increasing the mines will make the test even more reliable but to compare the boards we will need to do 2 000 000 comparisons, I think we can do better.

The truth is that is really hard or even impossible to test non-deterministic code, so how should we proceed? What are our options?

Approach 1 a probabilistic execution like the suggestion I described above. The issues with this approach are that it is slow and there is always even a small probability the unit test to fail intermittently.

Approach 2 attempt to prove the algorithm using a mathematical approach. Although this approach will guarantee correctness it is not a mainstream technique.

Approach 3 isolate the non-deterministic parts of the application and try to remove the randomness. Removing the randomness it is not something that can always be done but in our example above it was fairly straightforward.

Let’s attempt to implement approach 3, here is the class MineSweeper , note that mines are marked with an “X” and empty squares are marked with a “.”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;

public class Minesweeper {
    public String[][] makeBoard(int width, int height, int mines) {
        String[][] board = new String[width][height];
        for (String[] row : board) {
            Arrays.fill(row, ".");
        }
        return placeMines(board, mines);
   }
   private String[][] placeMines(String[][] board, int mines) {
       for (int i = 0; i < board.length; i++) {
           for (int j = 0; j< board[0].length;j++) {
	           if (mines > 0) {
                       board[i][j] = "X";
                       mines--;
               }
          }
      }
      return board;
   }
}

The first step in our example was to create a new class that would be responsible to shuffle the board lets call it BoardShuffler. BoardShuffler simply swaps every square with a random square. Random number generators usually accept a seed. The seed allows us to control the randomness and create a unit test that it is predictable. I have created an interface called IShuffler to allow me to mock this inline as an example but using a framework like Mockito will be my recommendation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Random;

public class BoardShuffler implements IShuffler {

	private Random generator;

	public BoardShuffler(int seed) {
	    generator = new Random(seed);
	}
	@Override
	public String[][] mix(String[][] placeMines) {
	    int width = placeMines.length;
		int height = placeMines[0].length;
		for (int i = 0; i < width; i++) {
			for (int j = 0;j<height; j++) {
				int randomWidth = getRandomSquare(width);
				int randomHeight = getRandomSquare(height);
				String temp = placeMines[i][j];
				placeMines[i][j] = placeMines[randomWidth][randomHeight];
				placeMines[randomWidth][randomHeight]= temp;
			}
		}
		return placeMines;
	}

	private int getRandomSquare(int maximum) {
		return generator.nextInt(maximum);
	}
}

Here is simple test that demonstrates the approach. Obviously you will need more than a single unit test for this class but the additional tests should be straight forward.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import org.junit.Test;
import static org.junit.Assert.*;
public class BoardShufflerTest {

	@Test
	public void testShufflingSimpleBoard() {
		IShuffler boardShuffler = new BoardShuffler(1);
		String[][] toBeMixed  = {{".","X"}};
		String[][] mixed = boardShuffler.mix(toBeMixed);
		String[][] expected  = {{"X","."}};
		assertArrayEquals(expected, mixed);
	}
}

The second step is to use dependency injection and use the BoardShuffler in the minesweeper class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Arrays;

public class Minesweeper {
	private IShuffler shuffler;

	public Minesweeper(IShuffler shuffler) {
		this.shuffler = shuffler;
	}

	public String[][] makeBoard(int width, int height, int mines) {
		String[][] board  = new String[width][height];
		for (String[] row: board){
			Arrays.fill(row, ".");
		}
		String[][] placeMines = placeMines(board,mines);
		return shuffler.mix(placeMines);
	}

	private String[][] placeMines(String[][] board, int mines) {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) { 
				if(mines>0){
					board[i][j] = "X";
					mines--;
				}
			}
		}
		return board;
	}
}

 

Writing a unit test is straightforward using a mock to check that the BoardShuffler has been called would do the trick.The testing of non-deterministic code can be tricky but DI can be really helpful and allows us to unit test parts of our application that we would have left without any unit test coverage. Again the topic is much more complex but I hope this blog gives you some assistance how to approach the problem.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s