[Programming Problem] Design Tic-Tac-Toe

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

– A move is guaranteed to be valid and is placed on an empty block.
– Once a winning condition is reached, no more moves are allowed.
– A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

– TicTacToe(int n) Initializes the object the size of the board n.
– 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?

[Problem Link]

Key here is that every move is going to be valid, so we don’t need to check for invalid or repeat moves! Instead of keeping track of the whole board and checking for winners we can simply keep track of number of times a player has hit a row, col, or either of the diagonals. If count for any of them for a player hits ‘N’ we have a winner!

Few things to keep in mind:-

  • Keep player status (i.e. hits for rows, cols, and both diagonals) for both players. A single object wont do.
  • Remember we have 2 diagonals. When calculating hits for diagonals, treat those diagonals as separate variables! (not single diagonal)
/**
 * Initialize your data structure here.
 * @param {number} n
 */
var TicTacToe = function(n) {
 
    // - Gotcha 1: Please add player status for both players, single object wont do
    // We need to keep track if specifically one players rows, cols, or diagonals have hit 'N'
    // - Gotcha 2: Please remember we have 2 diagonals!
    // - Gotcha 3: 
 
    // Player status objects!
    this.playerOne = {
        rows: new Array(n).fill(0),
        cols: new Array(n).fill(0),
        diagonal: [0, 0],
    }
 
    this.playerTwo = {
        rows: new Array(n).fill(0),
        cols: new Array(n).fill(0),
        diagonal: [0, 0],
    }
 
    // N
    this.n = n;
 
    // rows, cols in diagonal one (and diagonal two)
    this.diagonal_one_set = new Set();
    this.diagonal_two_set = new Set();
 
    // diagonal 1 and diagonal 2
    let i = this.n-1;
    let j = 0;
    while (i >=0 && j < this.n ) {        
      this.diagonal_two_set.add(i + '' + j);
      i--;
      j++;
    }
 
    i = 0;
    j = 0;
    while (i < this.n && j < this.n ) {        
      this.diagonal_one_set.add(i + '' + j);
      i++;
      j++;
    }
};
 
/**
 * 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. 
 * @param {number} row 
 * @param {number} col 
 * @param {number} player
 * @return {number}
 */
TicTacToe.prototype.move = function(row, col, player) {
    const playerStatus = player === 1 ? this.playerOne : this.playerTwo;
 
    playerStatus.rows[row]++;
    playerStatus.cols[col]++;
    if (this.diagonal_one_set.has(row + '' + col)) playerStatus.diagonal[0]++;
    if (this.diagonal_two_set.has(row + '' + col)) playerStatus.diagonal[1]++;
 
    if ( 
        playerStatus.rows[row] === this.n ||
        playerStatus.cols[col] === this.n ||
        playerStatus.diagonal[0] === this.n ||
        playerStatus.diagonal[1] === this.n) {        
        return player;
    } else {
        return 0;
    }
};
 
/** 
 * Your TicTacToe object will be instantiated and called as such:
 * var obj = new TicTacToe(n)
 * var param_1 = obj.move(row,col,player)
 */

softwareeveryday

33 thoughts on “[Programming Problem] Design Tic-Tac-Toe”

  18. I wanted to create you one very small observation to help say thanks yet again on the superb basics you’ve provided in this article. This has been seriously open-handed with people like you to offer unreservedly all that a number of people would have sold for an e book to make some profit for themselves, even more so seeing that you could possibly have tried it in the event you considered necessary. Those inspiring ideas likewise served as a fantastic way to be aware that other individuals have similar dream really like my very own to see lots more when considering this matter. I’m sure there are lots of more pleasurable times ahead for individuals who take a look at your site.

    Reply

  19. Needed to post you one bit of observation just to say thanks once again considering the beautiful techniques you’ve discussed at this time. It is so extremely generous with people like you to make easily all that a few individuals would have distributed as an electronic book in making some dough on their own, notably considering that you might well have tried it if you decided. These good tips in addition worked like the great way to realize that many people have similar passion much like my own to learn much more when considering this matter. I am sure there are many more pleasurable occasions up front for individuals who examine your website.

    Reply

  22. I intended to draft you this bit of word in order to give thanks yet again considering the pleasing guidelines you’ve discussed above. It was really incredibly generous of you to deliver unhampered what a lot of folks would have offered for sale as an electronic book to end up making some dough on their own, most notably considering that you could possibly have done it if you ever desired. Those solutions also worked to become easy way to fully grasp that the rest have a similar passion just as my personal own to realize much more when considering this condition. I am sure there are several more fun situations up front for folks who go through your website.

    Reply

  24. My husband and i felt absolutely peaceful that Louis managed to finish up his homework out of the ideas he acquired through the web site. It’s not at all simplistic just to possibly be handing out methods that a number of people might have been trying to sell. Therefore we keep in mind we need the blog owner to appreciate because of that. Most of the explanations you have made, the easy website menu, the relationships you will help to engender – it’s many terrific, and it is leading our son in addition to us consider that that subject matter is entertaining, which is certainly rather vital. Thanks for the whole lot!

    Reply

  26. I have to show my gratitude for your kind-heartedness giving support to folks that should have help with this particular concept. Your very own dedication to passing the solution all-around became exceedingly valuable and have specifically helped most people much like me to achieve their aims. Your amazing warm and helpful instruction indicates a lot to me and far more to my office colleagues. With thanks; from everyone of us.

    Reply

  27. I actually wanted to compose a small message to express gratitude to you for some of the precious information you are giving at this site. My particularly long internet search has at the end of the day been compensated with reasonable tips to exchange with my relatives. I would say that most of us visitors actually are extremely blessed to dwell in a fabulous site with many awesome individuals with valuable suggestions. I feel very lucky to have encountered the web site and look forward to so many more excellent times reading here. Thanks a lot again for a lot of things.

    Reply

  28. I wish to express my affection for your kind-heartedness in support of folks that must have guidance on this particular question. Your very own dedication to getting the message all-around turned out to be astonishingly informative and have specifically permitted people like me to arrive at their ambitions. Your valuable help can mean much a person like me and especially to my office workers. With thanks; from all of us.

    Reply

  29. I precisely desired to thank you very much once again. I am not sure the things I might have carried out without the actual advice documented by you directly on that area of interest. It actually was a very challenging issue for me, nevertheless looking at the very expert manner you dealt with the issue forced me to weep over delight. I am thankful for your advice and as well , have high hopes you realize what a powerful job you were accomplishing teaching the others using a blog. I’m certain you haven’t come across any of us.

    Reply

  30. I wish to point out my affection for your generosity supporting those people who must have guidance on in this idea. Your very own commitment to getting the message all-around became especially helpful and have surely permitted others just like me to reach their targets. Your new invaluable tutorial can mean much a person like me and further more to my office colleagues. Best wishes; from everyone of us.

    Reply

  31. I truly wanted to develop a brief message so as to appreciate you for some of the great secrets you are writing on this site. My prolonged internet look up has finally been recognized with high-quality ideas to write about with my friends and family. I would express that most of us readers are very much fortunate to dwell in a perfect site with very many marvellous professionals with valuable tips. I feel very much grateful to have discovered the web pages and look forward to tons of more entertaining minutes reading here. Thanks a lot again for all the details.

    Reply

  32. I just wanted to construct a brief remark in order to express gratitude to you for these fantastic suggestions you are placing at this site. My prolonged internet search has at the end been compensated with useful facts and strategies to write about with my pals. I would admit that most of us visitors actually are unequivocally blessed to be in a remarkable place with many perfect people with helpful solutions. I feel pretty blessed to have seen your entire website and look forward to so many more fun moments reading here. Thank you once more for all the details.

    Reply

  33. I want to voice my love for your kindness supporting those who actually need help with this one subject matter. Your personal dedication to passing the message along ended up being astonishingly insightful and have all the time helped somebody like me to attain their endeavors. Your own invaluable hints and tips indicates much a person like me and further more to my office workers. Thank you; from everyone of us.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More