Modelling a tic tac toe board state

My first foray into TDD coding katas led me to the Roman Numerals Kata. My second sees me designing a noughts and crosses engine (or tic tac toe if you prefer). This led down some interesting paths of designing the board and storing moves, combined with the best way to work out if someone had won. Maybe this shows me to be more of an algorithm designer than a TDD specialist but I think the time spent was worth it.

My initial test was that starting a game caused an empty board state to be produced. As I moved through the exercise I realised that this wasn't really a useful test. I certainly didn't care what the internal board state was, and as I'll get to, I didn't end up with a board being modelled at all! So that test got deleted. A similar test may return if I want the output of the game to be part of the API.

Equivalent initial designs

My initial board design was an array of playable positions, all initialised to the enum value Player.NEITHER. This is entirely equivalent to the other considered approach of a real-world-like model using a 3x3 array of the Player enum.

private List<Player> board = Arrays.asList(
   NEITHER,NEITHER,NEITHER,
   NEITHER,NEITHER,NEITHER,
   NEITHER,NEITHER,NEITHER);

or

private Player[][] board = {
   {NEITHER,NEITHER,NEITHER},
   {NEITHER,NEITHER,NEITHER},
   {NEITHER,NEITHER,NEITHER}};

The problem with these designs came when I needed to test the winning moves. What does an algorithm look like for checking a winning move in those data structures? Even when you factor in that that current move must be a part of the win, if there is one, you still have a lot of code checking various combinations of elements in your array. You could perhaps keep a set of 8 numbers, one for each win line (3 rows, 3 columns, 2 diagonals) and add one when player 1 plays there, and subtract 1 when player 2 does so. Then you know someone has won when a number reaches +/-3

But then I noticed a forum post which mentioned that a magic square might be a useful tool for a noughts and crosses game. And I immediately set about refactoring to use this new information. Luckily I had tests, and I could make pretty sweeping changes without breaking them as I had already deleted those pesky tests that were peering into the internals of my data structures.

The final design

I ended up with the "board" being a map of coordinates (Points) to magic square values. A turn involves taking one of those values from the map and adding it to the current players list of moves. If at any point a player has any 3 values that add up to 15, they have won. This also has the added bonus that if you were adding an AI player, it could easily scan the remaining moves to see if it, or you, has a winning move available.

import java.awt.Point;
import java.util.*;

public class Tictactoe {

 private Gamestate gameState = Gamestate.ONGOING;
 private Player currentPlayer = Player.PLAYER1;
 private Map<Point, Integer> availableSquares;
 private Map<Player, List<Integer>> playerBoards;

 public Tictactoe() {
  availableSquares = new HashMap<>();
  availableSquares.put(new Point(1,1), 4);
  availableSquares.put(new Point(1,2), 3);
  availableSquares.put(new Point(1,3), 8);
  availableSquares.put(new Point(2,1), 9);
  availableSquares.put(new Point(2,2), 5);
  availableSquares.put(new Point(2,3), 1);
  availableSquares.put(new Point(3,1), 2);
  availableSquares.put(new Point(3,2), 7);
  availableSquares.put(new Point(3,3), 6);

  List<Integer> player1sMoves = new ArrayList<>();
  List<Integer> player2sMoves = new ArrayList<>();
  playerBoards = new HashMap<Player, List<<Integer>>();
  playerBoards.put(Player.PLAYER1, player1sMoves);
  playerBoards.put(Player.PLAYER2, player2sMoves);
 }

 public Gamestate playAt(int column, int row) {
  Integer moveMade = availableSquares.remove(new Point(column, row));
  if (moveMade == null) {
   throw new IllegalStateException("already taken");
  }
  if (isWinningMove(moveMade, currentPlayer)) {
   gameState = currentPlayer.hasWon;
  }
  playerBoards.get(currentPlayer).add(moveMade);
  if (gameState == Gamestate.ONGOING && availableSquares.isEmpty()) {
   gameState = Gamestate.A_DRAW;
  }
  currentPlayer = currentPlayer.getNext();
  return gameState;
 }

 private boolean isWinningMove(int numberToTake, Player player) {
  LinkedList<Integer> second = new LinkedList<>(playerBoards.get(player));
  for (Integer integer : playerBoards.get(player)) {
   second.pollFirst();
   for (Integer integer2 : second) {
    if(numberToTake + integer + integer2 == 15) {
     return true;
    }
   }
  }
  return false;
 }

 public enum Gamestate {
  ONGOING, PLAYER1WON, PLAYER2WON, A_DRAW;
 }

 private enum Player {
  PLAYER1(Gamestate.PLAYER1WON), PLAYER2(Gamestate.PLAYER2WON);
  Gamestate hasWon;

  Player(Gamestate stateOnWinning) {
   this.hasWon = stateOnWinning;
  }

  public Player getNext() {
   Player next;
   switch (this) {
   case PLAYER1:
    next = PLAYER2;
    break;
   case PLAYER2:
   default:
    next = PLAYER1;
    break;
   }
   return next;
  }
 }

}

Roman Numerals Coding Kata

This is one of the classic TDD coding katas. I've only done this a dozen or so times but after the first 2 or 3 attempts I found that I always ended up with exactly the same code. Follow my steps and see if you would make the same leaps at the same point. Let me know where you would deviate, where you see me making mistakes, or where you see slight improvements.   Lets get started:

First, lets create a test class and our first test. At this point we are tentatively designing our API. It may change, but we're at least working out how we are likely to call the function from real code. We already see a little bit of duplication here in the test, but we'll deal with that later if necessary.

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class RomanNumeralTest {
 @Test
 public void test() {
  assertEquals("1","I", RomanNumerals.arabic2Roman(1));
 }

Obviously running this code with jUnit will fail as we haven't created the class under test yet, but run it anyway and verify that the failure is what you expect. This is an important step that sometimes gets missed by beginners or even veterans who are rushing ahead. We want our failures to be expected and for the error to make it obvious what has failed and where.

Now go ahead and make the smallest step possible in order to make the test pass: create the required class and method.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  return "I";
 }
}

The smallest step does introduce some duplication again. That "I" literal is used in both the test and the code. We will want to keep our eye on that and remove it as soon as possible, but for now we don't know how. We need more tests to triangulate. Check that you are now green and we'll move onto the next test.

public class RomanNumeralTest {
 @Test
 public void test() {
  assertEquals("1","I", RomanNumerals.arabic2Roman(1));
  assertEquals("2","II", RomanNumerals.arabic2Roman(2));
 }
}

Again, check that we are red and we'll move onto making the test pass, noticing as we do that there is even more duplication in those test cases. They're just too similar looking, with repeated literals.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  if (arabic == 2) {
   return "II";
  }
  return "I";
 }
}

Again, the simplest step to make the tests pass appears to be cheating, but there is still not enough to make a decision on how to design the algorithm to remove the duplications. Lets press on with another test. Its at this point that the duplication in the tests gets too much for me and I refactor that out a little.

public class RomanNumeralTest {

 @Test
 public void test() {
  testConverting(1, "I");
  testConverting(2, "II");
  testConverting(3, "III");
 }

 private void testConverting(int arabic, String roman) {
  assertEquals("test " + arabic, roman, RomanNumerals.arabic2Roman(arabic));
 }
}

Run again to prove that we are failing on the test that we expect. Having refactored the test it is possible that you introduced a problem with one of the earlier tests so we need to ensure it is the new test that is actually failing, and failing with a useful error message. Once we're happy we write the code to make this test pass.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  if (arabic == 3) {
   return "III";
  }
  if (arabic == 2) {
   return "II";
  }
  return "I";
 }
}

At this point the duplication becomes obvious and while we are green we take the chance to refactor it out.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  StringBuilder roman = new StringBuilder();
  while (arabic >= 1) {
   roman.append("I");
   arabic--;
  }
  return roman.toString();
 }
}

Now we are getting somewhere, but the next couple of tests feel like they are adding duplication without it being immediately obvious how it can be removed. I

 @Test
 public void test() {
  testConverting(1, "I");
  testConverting(2, "II");
  testConverting(3, "III");
  testConverting(4, "IV");
  testConverting(5, "V");
 }

And the simplest code to pass the tests. The code for IV and V looks like the first attempts at the code for I and II so maybe there is some hidden duplication here. I also don't like returning from the middle of a method.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  StringBuilder roman = new StringBuilder();
  if (arabic == 5) {
   return "V";
  }
  if (arabic == 4) {
   return "IV";
  }
  while (arabic >= 1) {
   roman.append("I");
   arabic--;
  }
  return roman.toString();
 }
}

Once we add the test for 6 it starts to become apparent what the duplication is, and we begin to see what our final algorithm may be.

public class RomanNumerals {
 public static String arabic2Roman(int arabic) {
  StringBuilder roman = new StringBuilder();
  if (arabic >= 5) {
   roman.append("V");
   arabic -= 5;
  }
  if (arabic == 4) {
   return "IV";
  }
  while (arabic >= 1) {
   roman.append("I");
   arabic--;
  }
  return roman.toString();
 }
}

Since we are green we can take the opportunity to make the duplication completely obvious by rewriting the code for when (arabic == 4) to match the other stanzas, and then make the steps necessary to remove it. At this point I have seen some other blogs on the Roman Numerals Kata create 2 parallel arrays with the mapping from one to the other in them. However, that word "mapping" should make it obvious that what we actually have here is a map, and we should use the Java Map interface to show the relationship. We need a Map that can be sorted in reverse order by the arabic number key. Here is my final solution with the rest of the tests and mappings included. Obviously there are smaller steps and tests to be created before you get here, but apart from adding more tests and the necessary numbers to the TreeMap, the code and algorithm stays the same.

public class RomanNumeralTest {

 @Test
 public void test() {
  testConverting(1,"I");
  testConverting(2,"II");
  testConverting(3,"III");
  testConverting(4,"IV");
  testConverting(5,"V");
  testConverting(6,"VI");
  testConverting(7,"VII");
  testConverting(8,"VIII");
  testConverting(9,"IX");
  testConverting(10,"X");
  testConverting(11,"XI");
  testConverting(20,"XX");
  testConverting(50,"L");
  testConverting(1954,"MCMLIV");
  testConverting(1990,"MCMXC");
  testConverting(2014,"MMXIV");
 }

 private void testConverting(int arabic, String roman) {
  assertEquals("converting " + arabic, roman, RomanNumerals.arabic2Roman(arabic));
 }
}

public class RomanNumerals {
 static Map<Integer,String> arabic2roman = new TreeMap<Integer,String>(Collections.reverseOrder());
 static {
  arabic2roman.put(1, "I");
  arabic2roman.put(4, "IV");
  arabic2roman.put(5, "V");
  arabic2roman.put(9, "IX");
  arabic2roman.put(10, "X");
  arabic2roman.put(40, "XL");
  arabic2roman.put(50, "L");
  arabic2roman.put(90, "XC");
  arabic2roman.put(100, "C");
  arabic2roman.put(400, "CD");
  arabic2roman.put(500, "D");
  arabic2roman.put(900, "CM");
  arabic2roman.put(1000, "M");
 }

 public static String arabic2Roman(int arabic) {
  StringBuilder roman = new StringBuilder();
  for (Map.Entry<Integer,String> entry : arabic2roman.entrySet()) {
   while (arabic >= entry.getKey()) {
    roman.append(entry.getValue());
    arabic-=entry.getKey();
   }
  }
  
  return roman.toString();
 }
}