[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

52 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

  34. Needed to put you the very small note to finally say thanks a lot the moment again considering the exceptional knowledge you have contributed on this page. It’s particularly generous with people like you to convey openly what exactly a lot of people might have made available for an electronic book to generate some profit on their own, certainly considering the fact that you might well have done it in the event you wanted. Those basics additionally worked to be a great way to be aware that the rest have similar keenness similar to mine to understand more concerning this issue. I believe there are many more pleasurable periods up front for individuals that look into your site.

    Reply

  35. I as well as my friends appeared to be checking out the best secrets and techniques found on your website and then instantly I had an awful suspicion I had not thanked you for those tips. Those people became certainly thrilled to read through them and now have definitely been taking pleasure in them. Appreciate your turning out to be considerably helpful as well as for picking such helpful useful guides most people are really desirous to understand about. Our own honest apologies for not expressing appreciation to you earlier.

    Reply

  36. I intended to send you that tiny note to help thank you so much yet again considering the amazing secrets you’ve contributed at this time. This has been quite open-handed of you to grant without restraint precisely what many individuals would’ve distributed as an ebook in order to make some dough for their own end, primarily now that you might well have tried it if you ever decided. These tips likewise served to be the easy way to understand that the rest have similar desire similar to my own to know the truth a good deal more with reference to this matter. I know there are some more fun opportunities up front for those who scan through your website.

    Reply

  38. I needed to send you this very little note to be able to give many thanks again regarding the wonderful advice you’ve discussed on this site. It was really wonderfully open-handed with people like you to grant openly precisely what a number of us could have distributed as an ebook in making some bucks on their own, notably seeing that you might have done it if you desired. These secrets in addition worked to be the easy way to understand that other people have the identical dreams much like my very own to realize lots more in terms of this issue. I know there are many more pleasurable opportunities up front for individuals who read your website.

    Reply

  39. Needed to write you the bit of note so as to give many thanks once again for the pretty principles you’ve shared above. It is quite seriously generous of you to allow easily all that many individuals would’ve supplied as an ebook to help with making some cash for their own end, principally since you might well have done it if you ever desired. Those solutions as well acted as the fantastic way to be aware that other people have the identical keenness like my own to figure out a great deal more regarding this problem. I’m certain there are numerous more pleasant occasions up front for folks who go through your website.

    Reply

  41. I have to point out my passion for your kindness for those people that need guidance on this important situation. Your real dedication to getting the solution all-around had become particularly important and have regularly empowered guys and women much like me to get to their goals. Your amazing insightful tutorial denotes a whole lot to me and substantially more to my colleagues. Thanks a lot; from each one of us.

    Reply

  42. I want to voice my gratitude for your kind-heartedness for men who should have help on the area of interest. Your very own commitment to getting the message all around became certainly functional and have without exception allowed those just like me to get to their goals. Your entire invaluable help indicates a great deal to me and even more to my peers. With thanks; from everyone of us.

    Reply

  43. I wish to voice my passion for your generosity for people who actually need assistance with in this concern. Your personal commitment to passing the message all through has been amazingly effective and have in most cases permitted individuals just like me to reach their endeavors. The informative advice implies so much a person like me and further more to my colleagues. Regards; from each one of us.

    Reply

  44. My spouse and i were quite fulfilled John managed to do his research from your precious recommendations he had from your own site. It is now and again perplexing to just continually be giving away techniques that others might have been selling. And now we know we’ve got the blog owner to appreciate for this. These illustrations you made, the simple site menu, the relationships you can make it possible to promote – it’s got all spectacular, and it is aiding our son in addition to our family imagine that this topic is pleasurable, and that’s especially fundamental. Many thanks for the whole thing!

    Reply

  45. My spouse and i ended up being now excited when Chris managed to complete his research through the precious recommendations he grabbed using your site. It is now and again perplexing just to be making a gift of concepts that many some others have been trying to sell. So we take into account we’ve got you to appreciate for that. The main explanations you have made, the easy site menu, the friendships your site give support to promote – it’s mostly impressive, and it’s facilitating our son in addition to us imagine that the concept is interesting, which is certainly rather mandatory. Thanks for all the pieces!

    Reply

  46. Can I simply say what a aid to search out somebody who really knows what theyre talking about on the internet. You positively know tips on how to convey a difficulty to mild and make it important. Extra individuals have to read this and understand this aspect of the story. I cant consider youre not more popular since you positively have the gift.

    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