Decode the Coding Interview in Elixir: Real-World Examples/

...

/

Design Tic-Tac-Toe

Design Tic-Tac-Toe

Understand and solve the interview question "Design Tic-Tac-Toe."

We'll cover the following...

Description

Suppose that two players are playing a game of tic-tac-toe on an n x n board. They are following specific rules to play and win the game.

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

Your task is to implement a TicTacToe module, which will be used by two players to play the game and win fairly.

Given the 2D array containing the inputs for the TicTacToe object and the move function, you have to implement the TicTacToe module.

Assume that you have the following input array:

[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]

Here, the first index of the 2D array is the input for the TicTacToe object and the rest of the indexes will be used as input for the move function.

Let’s look at the illustration of how the TicTacToe module will use the inputs given below.

Keep in mind the following functionalities that need to be implemented:

  • TicTacToe struct, which declares an object to create the board.
  • init(n), which initializes the object of TicTacToe to create the board of size n.
  • move(row, col, player), which indicates that the player with ID player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Constraints:

  • 2 <= n <= 100

  • The player should be either 1 or 2.

  • 0 <= row, col < n

  • Every call to move() will be with a unique row, col combination.

  • The move function will be called at most n2n^2 times.

Coding exercise

Press + to interact
defmodule TicTacToe do
  defstruct []
  def init(_n) do 
    # Initialise your data structures here
  end
  def move(obj, _row, _col, _player) do
    # Write your code here
    {-1, obj} # return 0 if no one wins otherwise return player id
  end
end

Solution

While playing tic-tac-toe, we must find if the player has won. A player can win by marking an entire row, column, diagonal, or anti-diagonal cells. We can solve this problem in a constant time.

Let’s break the problem into two parts.

  • First, if there are n rows and n columns on a board, at each move, we must check if the player has already marked all of the cells in a row or column, that is, the certain row or column is marked n times.

  • Second, we must check if the player marked all the cells on the diagonal or anti-diagonal on every move. There can only be one diagonal and one anti-diagonal, no matter what the size of the board is.

From the given conditions, ...

Access this course and 1400+ top-rated courses and projects.