{"id":11314,"date":"2021-05-17T04:08:34","date_gmt":"2021-05-17T04:08:34","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11314"},"modified":"2021-05-17T04:08:34","modified_gmt":"2021-05-17T04:08:34","slug":"programming-problem-design-tic-tac-toe","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11314","title":{"rendered":"[Programming Problem] Design Tic-Tac-Toe"},"content":{"rendered":"<p>Assume the following rules are for the tic-tac-toe game on an n x n board between two players:<\/p>\n<p>&#8211; A move is guaranteed to be valid and is placed on an empty block.<br \/>\n&#8211; Once a winning condition is reached, no more moves are allowed.<br \/>\n&#8211; A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.<\/p>\n<p>Implement the TicTacToe class:<\/p>\n<p>&#8211; TicTacToe(int n) Initializes the object the size of the board n.<br \/>\n&#8211; 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.<\/p>\n<p>Follow up:<br \/>\nCould you do better than O(n2) per move() operation?<\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/design-tic-tac-toe\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<p>Key here is that every move is going to be valid, so we don&#8217;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 &#8216;N&#8217; we have a winner!<\/p>\n<p>Few things to keep in mind:-<\/p>\n<ul>\n<li>Keep player status (i.e. hits for rows, cols, and both diagonals) for both players. A single object wont do.<\/li>\n<li>Remember we have 2 diagonals. When calculating hits for diagonals, treat those diagonals as separate variables! (not single diagonal)<\/li>\n<\/ul>\n<pre lang=\"javascript\">\r\n\/**\r\n * Initialize your data structure here.\r\n * @param {number} n\r\n *\/\r\nvar TicTacToe = function(n) {\r\n    \r\n    \/\/ - Gotcha 1: Please add player status for both players, single object wont do\r\n    \/\/ We need to keep track if specifically one players rows, cols, or diagonals have hit 'N'\r\n    \/\/ - Gotcha 2: Please remember we have 2 diagonals!\r\n    \/\/ - Gotcha 3: \r\n\r\n    \/\/ Player status objects!\r\n    this.playerOne = {\r\n        rows: new Array(n).fill(0),\r\n        cols: new Array(n).fill(0),\r\n        diagonal: [0, 0],\r\n    }\r\n    \r\n    this.playerTwo = {\r\n        rows: new Array(n).fill(0),\r\n        cols: new Array(n).fill(0),\r\n        diagonal: [0, 0],\r\n    }\r\n    \r\n    \/\/ N\r\n    this.n = n;\r\n    \r\n    \/\/ rows, cols in diagonal one (and diagonal two)\r\n    this.diagonal_one_set = new Set();\r\n    this.diagonal_two_set = new Set();\r\n\r\n    \/\/ diagonal 1 and diagonal 2\r\n    let i = this.n-1;\r\n    let j = 0;\r\n    while (i >=0 && j < this.n ) {        \r\n      this.diagonal_two_set.add(i + '' + j);\r\n      i--;\r\n      j++;\r\n    }\r\n    \r\n    i = 0;\r\n    j = 0;\r\n    while (i < this.n &#038;&#038; j < this.n ) {        \r\n      this.diagonal_one_set.add(i + '' + j);\r\n      i++;\r\n      j++;\r\n    }\r\n};\r\n\r\n\/**\r\n * Player {player} makes a move at ({row}, {col}).\r\n        @param row The row of the board.\r\n        @param col The column of the board.\r\n        @param player The player, can be either 1 or 2.\r\n        @return The current winning condition, can be either:\r\n                0: No one wins.\r\n                1: Player 1 wins.\r\n                2: Player 2 wins. \r\n * @param {number} row \r\n * @param {number} col \r\n * @param {number} player\r\n * @return {number}\r\n *\/\r\nTicTacToe.prototype.move = function(row, col, player) {\r\n    const playerStatus = player === 1 ? this.playerOne : this.playerTwo;\r\n        \r\n    playerStatus.rows[row]++;\r\n    playerStatus.cols[col]++;\r\n    if (this.diagonal_one_set.has(row + '' + col)) playerStatus.diagonal[0]++;\r\n    if (this.diagonal_two_set.has(row + '' + col)) playerStatus.diagonal[1]++;\r\n\r\n    if ( \r\n        playerStatus.rows[row] === this.n ||\r\n        playerStatus.cols[col] === this.n ||\r\n        playerStatus.diagonal[0] === this.n ||\r\n        playerStatus.diagonal[1] === this.n) {        \r\n        return player;\r\n    } else {\r\n        return 0;\r\n    }\r\n};\r\n\r\n\/** \r\n * Your TicTacToe object will be instantiated and called as such:\r\n * var obj = new TicTacToe(n)\r\n * var param_1 = obj.move(row,col,player)\r\n *\/\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Assume the following rules are for the tic-tac-toe game on an n x n board between two players: &#8211; A move is guaranteed to be valid and is placed on an empty block. &#8211; Once a winning condition is reached, no more moves are allowed. &#8211; A player who succeeds in placing n of their [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11314","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11314","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11314"}],"version-history":[{"count":2,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11314\/revisions"}],"predecessor-version":[{"id":11316,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11314\/revisions\/11316"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}