Arrays, Problem Solving, Software Development

Problem Solving: Xs and Os / Tic-Tac-Toe (Part 2)

Start a new project, I was using IntelliJ for this. The below is my folder structure.

In your GameTest file make 4 tests.

	@Test
	public void completeGameWithWinner_shouldReturnWinnerX() {

	}

	@Test
	public void completeGameWithNoWinner_shouldReturnNoWinner() {
		
	}

	@Test
	public void incompleteGameWithWinner_shouldReturnWinnerX() {
		
	}

	@Test
	public void incompleteGameWithNoWinnerYet_shouldReturnNoWinnerYet() {

	}

The tests will instantiate a new multidimensional array. Create the arrays as below. Remember from part 1 that Empty is 0, X is 1 and O is 2 when you’re creating the array.

	@Test
	public void completeGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] completeGameWithWinner = {{1, 1, 1},
				{1, 2, 2},
				{2, 2, 1}};
		//when

		//then

	}

	@Test
	public void completeGameWithNoWinner_shouldReturnNoWinner() {
		//given
		int[][] completeGameWithNoWinner = {{2, 1, 1},
				{1, 1, 2},
				{2, 2, 1}};
		//when
		
		//then

	}

	@Test
	public void incompleteGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] incompleteGameWithWinner = {{1, 2, 0},
				{0, 1, 2},
				{0, 0, 1}};
		//when
		
		//then

	}

	@Test
	public void incompleteGameWithNoWinnerYet_shouldReturnNoWinnerYet() {
		//given
		int[][] incompleteGameWithNoWinnerYet = {{1, 2, 0},
				{0, 1, 0},
				{0, 2, 0}};
		//when
		
		//then

	}

This array will be a 3 X 3 and will represent a game state. In our code we want to verify this game state. By verify we mean we want to be able to find out if X has won in this game state, if O has won, if there were no winners, if the game isn’t finished. We’re going to abstract the details of the game state to a new Game object. A new game will be instantiated for all the tests here:

public class GameTest {
	private Game game;

Assign game in each test using its multidimensional array.

	@Test
	public void completeGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] completeGameWithWinner = {{1, 1, 1},
				{1, 2, 2},
				{2, 2, 1}};
		//when
		game = new Game(completeGameWithWinner);
		//then
		
	}

	@Test
	public void completeGameWithNoWinner_shouldReturnNoWinner() {
		//given
		int[][] completeGameWithNoWinner = {{2, 1, 1},
				{1, 1, 2},
				{2, 2, 1}};
		//when
		game = new Game(completeGameWithNoWinner);
		//then
		
	}

	@Test
	public void incompleteGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] incompleteGameWithWinner = {{1, 2, 0},
				{0, 1, 2},
				{0, 0, 1}};
		//when
		game = new Game(incompleteGameWithWinner);
		//then
		
	}

	@Test
	public void incompleteGameWithNoWinnerYet_shouldReturnNoWinnerYet() {
		//given
		int[][] incompleteGameWithNoWinnerYet = {{1, 2, 0},
				{0, 1, 0},
				{0, 2, 0}};
		//when
		game = new Game(incompleteGameWithNoWinnerYet);
		//then		
	}

Lastly add in assertion statements comparing the message we will expect back when a game state is verified vs what is actually returned:

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class GameTest {
	private Game game;

	@Test
	public void completeGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] completeGameWithWinner = {{1, 1, 1},
				{1, 2, 2},
				{2, 2, 1}};
		//when
		game = new Game(completeGameWithWinner);
		//then
		Assertions.assertEquals("The Winner is X", game.verifyGameState());
	}

	@Test
	public void completeGameWithNoWinner_shouldReturnNoWinner() {
		//given
		int[][] completeGameWithNoWinner = {{2, 1, 1},
				{1, 1, 2},
				{2, 2, 1}};
		//when
		game = new Game(completeGameWithNoWinner);
		//then
		Assertions.assertEquals("No Winner - Game Complete", game.verifyGameState());
	}

	@Test
	public void incompleteGameWithWinner_shouldReturnWinnerX() {
		//given
		int[][] incompleteGameWithWinner = {{1, 2, 0},
				{0, 1, 2},
				{0, 0, 1}};
		//when
		game = new Game(incompleteGameWithWinner);
		//then
		Assertions.assertEquals("The Winner is X", game.verifyGameState());
	}

	@Test
	public void incompleteGameWithNoWinnerYet_shouldReturnNoWinnerYet() {
		//given
		int[][] incompleteGameWithNoWinnerYet = {{1, 2, 0},
				{0, 1, 0},
				{0, 2, 0}};
		//when
		game = new Game(incompleteGameWithNoWinnerYet);
		//then
		Assertions.assertEquals("No Winner Yet - Game Incomplete", game.verifyGameState());
	}
}

Leave GameTest, we’re going to populate Game now:

In Game, start by declaring fields (I have named them according to their multidimensional coordinates). As these don’t change once declared they are marked final.

public class Game {	
	private final int x0y0;
	private final int x0y1;
	private final int x0y2;
	private final int x1y0;
	private final int x1y1;
	private final int x1y2;
	private final int x2y0;
	private final int x2y1;
	private final int x2y2;
}

As mentioned in part 1 we use ints in place of chars. Declare and use these as static finals to avoid ‘magic numbers’ creeping into your code.

public class Game {
	private static final int EMPTY_VALUE = 0;
	private static final int X = 1;
	private static final int O = 2;	

	private final int x0y0;
	private final int x0y1;
	private final int x0y2;
	private final int x1y0;
	private final int x1y1;
	private final int x1y2;
	private final int x2y0;
	private final int x2y1;
	private final int x2y2;
}

Add in a constructor for Game. This constructor takes a multidimensional array (our game state) in order to instantiate a new Game. In the constructor we have assigned fields of the current object (indicated by this keyword) to equal corresponding coordinates of the multidimensional array used.

public class Game {
	private static final int EMPTY_VALUE = 0;
	private static final int X = 1;
	private static final int O = 2;

	private final int x0y0;
	private final int x0y1;
	private final int x0y2;
	private final int x1y0;
	private final int x1y1;
	private final int x1y2;
	private final int x2y0;
	private final int x2y1;
	private final int x2y2;

	public Game(int[][] newGameDetails) {
		this.x0y0 = newGameDetails[0][0];
		this.x0y1 = newGameDetails[0][1];
		this.x0y2 = newGameDetails[0][2];
		this.x1y0 = newGameDetails[1][0];
		this.x1y1 = newGameDetails[1][1];
		this.x1y2 = newGameDetails[1][2];
		this.x2y0 = newGameDetails[2][0];
		this.x2y1 = newGameDetails[2][1];
		this.x2y2 = newGameDetails[2][2];
	}
}

Below the constructor we’ve just added, we’re now going to add in our main method of this class – verifyGameState(). All of our other Game methods will be private as they do their work inside the Game class, but verifyGameState() will be public so we can call it from outside.

To start off I’m just going to add in a call to setup(), a new method we’ll use to do some work for us.

	public String verifyGameState() {
		setup();
	}

We’ll need to create a new ArrayList that will be accessible to the whole class (and you’ll need the below imports):

import java.util.ArrayList;
import java.util.List;

public class Game {
	private final List<Integer> gameState = new ArrayList<>();

In the new method setup() we are adding to an ArrayList all of the fields of the Game object. This new ArrayList now contains our game state and is therefore appropriately named gameState. I’ve done this because for some of the manipulations later on, an ArrayList is the most flexible way of working with this information.

	private void setup() {
		gameState.add(x0y0);
		gameState.add(x0y1);
		gameState.add(x0y2);
		gameState.add(x1y0);
		gameState.add(x1y1);
		gameState.add(x1y2);
		gameState.add(x2y0);
		gameState.add(x2y1);
		gameState.add(x2y2);
	}

So next in verifyGameState(), before we start looking for Xs or Os, we’re going to have a fail fast check, so if we are passed a board of the wrong size for example, we find this quickly and don’t waste time on it. Add in the If Else statement below:

	public String verifyGameState() {
		setup();
		if(validateGameState()) {
                
		}else return "Invalid Values";
	}	

Now to add our validation. In this example there is only one check by validateBoardSize() and the result is returned by validateGameState(). These are abstracted like this so as to allow you to add several validation checks and then validateGameState() can return an overall result of whether the game state is valid or not. Add the below code after the setup() method:

	private boolean validateGameState() {
		return validateBoardSize();
	}

	private boolean validateBoardSize() {
		return gameState.size() == REQUIRED_BOARD_SIZE;
	}

Add in REQUIRED_BOARD_SIZE as a new static final:

public class Game {
	private final List<Integer> gameState = new ArrayList<>();

	private static final int EMPTY_VALUE = 0;
	private static final int X = 1;
	private static final int O = 2;
	private static final int REQUIRED_BOARD_SIZE = 9;

Now we’re going to add more to verifyGameState() by creating a new method to do some work, called findWinner(). findWinner() is going to check through the gameState list and find if X or O won. If neither won we’ll get findWinner() to return the EMPTY_VALUE and then we can investigate further.

Add the below calls to findWinner() along with the If Else logic:

	public String verifyGameState() {
		setup();
		if(validateGameState()) {
			if(findWinner() != EMPTY_VALUE) {
				if(findWinner() == X) {
					return "The Winner is X";
				}else if(findWinner() == O) {
					return "The Winner is O";
				}
			}
		}else return "Invalid Values";
	}	

Below validateBoardSize() add in findWinner() below.

	private int findWinner() {

	}
}

Now because there are three different directions a player can win in we’re going to call new methods to do that searching for us. Add in the below new methods under findWinner():

	private boolean findWinnerHorizontal(int xOrO) {

	}

	private boolean findWinnerVertical(int xOrO) {

	}

	private boolean findWinnerDiagonal(int xOrO) {

	}

As above in the 3 new methods we are passing in an int xOrO (as in X or O).

First we’ll look at how it will work with just findWinnerHorizontal() and X. In findWinner() we are going to call findWinnerHorizontal() and pass in X (remember, because these correspond to our static final ints declared at the top the IDE recognizes them as ints). findWinnerHorizontal() will take in its xOrO value (X in this case). It will compare X to the Game fields (the idea is to fail fast again, start by comparing X/O to the fields and then following that see if the fields are equal, as per part 1 if a field is Empty then the horizontal/vertical/diagonal line being checked would never win) . findWinnerHorizontal() will return a boolean as to whether there was a horizontal line found containing all Xs.

	private int findWinner() {
		if(findWinnerHorizontal(X)) {
			return X;
		} else if //....
	}

	private boolean findWinnerHorizontal(int xOrO) {
		return ((xOrO == x0y0 && x0y0 == x0y1 && x0y1  == x0y2)||
				(xOrO == x1y0 && x1y0 == x1y1 && x1y1  == x1y2)||
				(xOrO == x2y0 && x2y0 == x2y1 && x2y1  == x2y2));
	}

Now I’ve filled in the rest of findWinner(), findWinnerHorizontal(), findWinnerVertical() and findWinnerDiagonal(). As mentioned above if findWinner() can’t find a winner it will return EMPTY_VALUE.

	private int findWinner() {
		if(findWinnerHorizontal(X)) {
			return X;
		} else if(findWinnerHorizontal(O)) {
			return O;
		} else if(findWinnerVertical(X)) {
			return X;
		} else if(findWinnerVertical(O)) {
			return O;
		} else if(findWinnerDiagonal(X)) {
			return X;
		} else if(findWinnerDiagonal(O)) {
			return O;
		} else return EMPTY_VALUE;
	}

	private boolean findWinnerHorizontal(int xOrO) {
		return ((xOrO == x0y0 && x0y0 == x0y1 && x0y1  == x0y2)||
				(xOrO == x1y0 && x1y0 == x1y1 && x1y1  == x1y2)||
				(xOrO == x2y0 && x2y0 == x2y1 && x2y1  == x2y2));
	}

	private boolean findWinnerVertical(int xOrO) {
		return ((xOrO == x0y0 && x0y0 == x1y0 && x1y0  == x2y0)||
				(xOrO == x0y1 && x0y1 == x1y1 && x1y1  == x2y1)||
				(xOrO == x0y2 && x0y2 == x1y2 && x1y2  == x2y2));
	}

	private boolean findWinnerDiagonal(int xOrO) {
		return ((xOrO == x0y0 && x0y0 == x1y1 && x1y1  == x2y2)||
				(xOrO == x2y0 && x2y0 == x1y1 && x1y1  == x0y2));
	}

Now, almost complete. Back to verifyGameState(). We need to handle the scenario where there is no winner. Add in a call to checkGameComplete() and the If Else logic:

	public String verifyGameState() {
		setup();
		if(validateGameState()) {
			if(findWinner() != EMPTY_VALUE) {
				if(findWinner() == X) {
					return "The Winner is X";
				}else if(findWinner() == O) {
					return "The Winner is O";
				}
			}
			if (checkGameComplete()) {
				return "No Winner - Game Complete";
			}else {
				return "No Winner Yet - Game Incomplete";
			}
		}else return "Invalid Values";
	}

Add new method checkGameComplete() below findWinnerDiagonal(). This will utilise Streams to go through our gameState list and return a boolean based on whether any EMPTY_VALUE was discovered in the list. If there are none (returns true) – then the game was completed with no winner. If it finds empty values (returns false) – then the game is incomplete.

	private boolean checkGameComplete() {
		return gameState.stream()
				.noneMatch(currentGameMark -> currentGameMark.equals(EMPTY_VALUE));
	}

That’s it! I hope this is helpful, my GitHub is linked below with the problem we’ve just discussed.

Standard
Arrays, Problem Solving, Software Development

Problem Solving: Xs and Os / Tic-Tac-Toe (Part 1)

X’s and Os can be represented as a multidimentional array:

0,00,10,2
1,01,11,2
2,02,12,2

Rather than pass in 9 parameters, make each coordinate a field in a Game object. Instead of using X and O in the program, use integers as this is easier to handle. Account for empty spaces with another integer. Use statics for these values to avoid ‘magic numbers’. A game needs to be passed in a required board of size 9. This required board can include X, O and Empty markers.

Assumptions

Assume we are passed a multidimensional int array (int[][]). Assume the conversion (from Empty to 0, X to 1, O to 2) has been completed in another part of the code. Assume we are passed an int[][] of size 3 x 3. Assume play will continue until there is a winner or until all spaces are used.

States

We are accounting for four states our game can be in – Winner with no Empty Spaces, Winner with Empty Spaces, No Winner with no Empty Spaces, No Winner Yet. As the game can have a Winner and contain Empty Spaces therefore for efficiency check for a Winner first. Thereafter if there’s No Winner check if the game has Empty Spaces. If this is the case the game is in state No Winner Yet.

Ways to win

8 ways to win (diagrams below – X placed in diagram but can be X or O). As the winning horizontal/vertical/diagonal line must have 3 X or O markers to win, to fail fast check the markers against X or O first (variable xOrO used for this). If the marker is Empty that line will not be a winning line.

Tests

I tested the ‘happy path’ –

completeGameWithWinner_shouldReturnWinner

completeGameWithNoWinner_shouldReturnNoWinner

incompleteGameWithWinner_shouldReturnWinner

incompleteGameWithNoWinnerYet_shouldReturnNoWinnerYet

More exception handling and tests could be added to check for non-happy path scenarios like if the gameState passed is larger or smaller than 3 X 3, and so forth.

Ways to win – diagrams

Horizontal:

XXX
   
   
   
XXX
   
   
   
XXX

Vertical:

X  
X  
X  
 X 
 X 
 X 
  X
  X
  X

Diagonal:

X  
 X 
  X
  X
 X 
X  

I hope this is helpful, my GitHub is linked below with the problem we’ve just discussed.

In Part 2 I’ll discuss more in detail how to implement the solution discussed above.

Standard
Arrays, Problem Solving, Software Development

Problem Solving: Hourglass

Below is a 6 X 6 2D array arr. In this question you are asked to identify hourglasses in the array.

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

There are 16 hourglasses in arr. An hourglass is a subset of values falling in this pattern:

a b c
  d
e f g

An hourglass sum is the sum of all an hourglass’s values.

Question:

Calculate all the hourglass sums in a 2D array. Return the maximum hourglass sum. The array will always be 6 X 6.

Solution:

Make int variables largestHourglassSum and currentHourglassSum. largestHourglassSum will be initialized as the first hourglass’s sum. currentHourglassSum will be the current hourglass’s sum as the loops iterate. The nested for loop will move through the array to capture and sum each new hourglass. As the loops iterate in the If statement if the currentHourglassSum is larger that will now become largestHourglassSum.

Hourglass 1: arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2]

Hourglass 2: Increment j and repeat the above.

Method:

    static int hourglassSum(int[][] arr) {
        int currentCount = 0;
    	int count = arr[0][0] + arr[0][1] + arr[0][2] 
                + arr[1][1] + arr[2][0] + arr[2][1] 
                + arr[2][2];
        
        for(int i = 0; i < arr.length-2; i++) {
            for (int j = 0; j < arr.length-2; j++) {
                currentCount = arr[i][j] + arr[i][j+1] + arr[i][j+2] 
                    + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] 
                    + arr[i+2][j+2];
                if(currentCount > count) {
                    count = currentCount;
                }
            } 
        } return count;
    }

Accompanying test:

	@Test
	void whenGivenArray_shouldReturnHourglassSum() {
		//given
		Array2D array = new Array2D();
		//when
		int[][] arr = {	{-1, -1, 0, -9, -2, -2},
						{-2, -1, -6, -8, -2, -5},
						{-1, -1, -1, -2, -3, -4},
						{-1, -9, -2, -4, -4, -5},
						{-7, -3, -3, -2, -9, -9},
						{-1, -3, -1, -2, -4, -5}};
		//then
		Assertions.assertEquals(-6, array.hourglassSum(arr));
	}

I hope this is helpful, my GitHub is linked below with the problem we’ve just discussed. Problems sourced on HackerRank.

Standard