It is about quitting time for today Friday January 15, 2021. Due to the snow storm the cleaning lady called to postpone for today. She will be here Monday morning. I guess different cities received different amounts of snow. I am not sure how much fresh snow fell during this storm. My guess is that we received between 2 to 3 inches. That said; the service that cleans our driveway and paths was here around 01:00 PM.
For lunch my wife prepared a Chinese meal with products from Trader Joe’s. It was quite good taking into consideration that it came from a super market. It took my wife about 30 minutes to prepare lunch from start to finish.
I was looking for a specific problem on LeetCode but could not find it. Perhaps the name has been changed. I did find Design Tic-Tac-Toe. I had to give it a try.
Assume the following rules are for the tic-tac-toe game on an n x n board between two players: o A move is guaranteed to be valid and is placed on an empty block. o Once a winning condition is reached, no more moves are allowed. o A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game. Implement the TicTacToe class: o TicTacToe(int n) Initializes the object the size of the board n. o int move(int row, int col, int player) Indicates that player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move. Follow up: Could you do better than O(n2) per move() operation? Constraints: o 2 <= n <= 100 o player is 1 or 2. o 1 <= row, col <= n o (row, col) are unique for each different call to move. o At most n2 calls will be made to move.
The rules are simple and match the ones for the tic-tac-toe we all used to play growing up. Our task is limited to declare variables for the class, generate the constructor to initialize the variables and accept the moves made by the two players. At some point we need to call a winner.
The test scaffolding will make sure that the players make one call at a time and they alternate. Also it seems that they will not attempt to fill a spot already used by the opponent.
The requirements look straight forward.
class TicTacToe {
/** Initialize your data structure here. */
public TicTacToe(int n) {
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
The signature for the TicTacToe class is provided. We need to fill in the constructor and the move methods.
LeetCode also provides how the TicTacToe class will be invoked and used.
I like to develop the solution in one of my machines. We will have to generate a test scaffolding to mimic what LeetCode provides. I will be using the Java programming language and the VSCode IDE running on a Windows 10 machine. After feeling confident with a solution, I will have to copy and paste the code into the LeetCode IDE and submit it for evaluation.
3 0, 0, 1 0, 2, 2 2, 2, 1 1, 1, 2 2, 0, 1 1, 0, 2 2, 1, 1 main <<< board: [1, 0, 2] [2, 2, 0] [1, 1, 1] main <<< player: 1 winner winner chicken dinner !!! 3 0, 0, 1 1, 1, 2 1, 0, 1 1, 2, 2 2, 0, 1 main <<< board: [1, 0, 0] [1, 2, 2] [1, 0, 0] main <<< player: 1 winner winner chicken dinner !!! 3 0, 0, 1 0, 2, 2 1, 1, 1 2, 0, 2 2, 2, 1 main <<< board: [1, 0, 2] [0, 1, 0] [2, 0, 1] main <<< player: 1 winner winner chicken dinner !!! 3 0, 2, 1 0, 0, 2 1, 1, 1 1, 0, 2 2, 0, 1 main <<< board: [2, 0, 1] [2, 1, 0] [1, 0, 0]
It seems that LeetCode provides one example. That is the first test we use.
The tests start with the side of the board we will use for the game. Our test code needs to read the dimension for the board. The boards are square. In this first case our board will be 3×9 with 9 cells.
Following are a set of lines. Each line contains information for a single move. The first integer represents the row for the move. The second value represents the column on the board for the move. The third and last argument is the player number. We have two players. The first is player 1 and the second player 2.
The idea is that our test program will process a move and will determine if the move generates a winner. This will become clear when we see the code for the test scaffolding.
At some point in the game, a winner may appear. We could check if there is a tie, but implementing such condition is not required.
If you follow the games with a piece of paper, you can determine that at some point one of the players wins the game. Note that the display of the board is an artifact of our test code. We are not required to display the board as part of the solution.
In addition, when a game ends due to a winner, the test program displays a message. That is not part of the solution.
As you can verify with a piece of paper, we have to determine is a game is won by filing a row, a column or one of the two diagonals. A test for each condition is executed to assure all is well.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
int winner = 0;
TicTacToe obj = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// ***** loop until there is a winner ****
while(winner == 0) {
// **** read next input line ****
String[] strArr = br.readLine().trim().split(", ");
// **** initialize or move ****
if (strArr.length == 1) {
obj = new TicTacToe(Integer.parseInt(strArr[0]));
} else {
// **** parse the arguments for the move ****
int r = Integer.parseInt(strArr[0]);
int c = Integer.parseInt(strArr[1]);
int p = Integer.parseInt(strArr[2]);
// **** player makes move ****
winner = obj.move(r, c, p);
// **** signal winner (if needed) ****
if (winner != 0) {
System.out.println("main <<< board:");
System.out.println(obj.toString());
System.out.println("main <<< player: " + p +
" winner winner chicken dinner !!!");
}
}
}
// **** close the buffered reader ****
br.close();
}
We start by performing initializations. We then open a buffered reader that will be used to read when to initialize the game and then read the arguments for the moves of the two players.
We then enter a loop in which we exit when a winner is found. A winner is determined by the number of the player winning the game.
We read the next line. It can be a game initialization or a move. LeetCode will start all games with an initialization. From there on we will be presented by moves from the opposing players.
When we receive data for a move, we parse the row, column and player. We then make a call to the move method which returns 0, 1 or 2 depending on the result of the move. A 0 means no winner yet, a 1 indicates that player 1 won and 2 that player 2 is the winner.
Our test software detects if a player won the game and displays a message. The loops exists and we close the buffered reader.
/**
* Design Tic-Tac-Toe
* https://leetcode.com/problems/design-tic-tac-toe/
*
* Runtime: 3 ms, faster than 99.96% of Java online submissions.
* Memory Usage: 42.1 MB, less than 48.10% of Java online submissions.
*/
public class TicTacToe {
// **** class members ****
public int n = 0;
public int[][] board = null;
/**
* Initialize your data structure here.
*/
public TicTacToe(int n) {
this.n = n;
this.board = new int[n][n];
}
::: ::: ::::
}
This is the TicTacToe class. The class shows the members and the constructor. The rest of the code is not displayed. The class members and the constructor are part of the solution.
Note that in the comments section we have information about our solution. I guess we did well on our first and only submission.
/**
* Player {player} makes a move at ({row}, {col}).
* @param row The row of the board.
* @param col The column of the board.
* @param player The player, can be either 1 or 2.
* @return The current winning condition, can be either:
* 0: No one wins.
* 1: Player 1 wins.
* 2: Player 2 wins.
*/
public int move(int row, int col, int player) {
// **** initialization ****
int winner = 0;
// **** flag move on board ****
board[row][col] = player;
// **** check if we have a winner ****
winner = haveWinner(row, col, player);
// **** return winner ****
return winner;
}
The move method sets the winner variable. We then flag the space on the board for the move. We check if we have a winner and return the updated variable. We could have eliminated the winner variable and have returned the result of the haveWinner auxiliary method returned directly. You could make that change and reduce a fraction of the time from the game.
/**
* Determine if we have a winner.
* Execution time: O(4n)
*/
private int haveWinner(int row, int col, int player) {
// **** initialization ****
int winner = player;
// **** check row O(n) ****
for (int c = 0; c < this.n; c++) {
if (board[row] != player) {
winner = 0;
break;
}
}
// **** check if we have a winner ****
if (winner == player)
return winner;
// **** check column O(n) ****
winner = player;
for (int r = 0; r < this.n; r++) {
if (this.board[r][col] != player) {
winner = 0;
break;
}
}
// **** check if we have a winner ****
if (winner == player)
return winner;
// **** check first diagonal O(n) ****
winner = player;
for (int d = 0; d < this.n; d++) {
if (this.board[d][d] != player) {
winner = 0;
break;
}
}
// **** check if we have a winner ****
if (winner == player)
return winner;
// **** check second diagonal O(n) ****
winner = player;
for (int d = n - 1; d >= 0; d--) {
if (this.board[d][n - d - 1] != player) {
winner = 0;
break;
}
}
// **** ****
return winner;
}
This auxiliary method checks if a row, column, or one of the two diagonals contains the player number in all the cells. If it does, we return the player number indicating this is the winner for the game. Like I stated earlier, this is the first and only pass of the code. Perhaps we could optimize further this method in order to eliminate some of the checks under some conditions. That could shave another fraction of time from the game.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,866 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com