1
\$\begingroup\$

Working on the problem Find Winner on a Tic Tac Toe Game, I took several hours longer than an artificial time constraint the site had for mock interview purposes. This leads me to wonder if my solution is needlessly complex or unclear. Curious to hear from others. The only part that would have to stay the same upon review is the function signature func tictactoe(_ moves: [[Int]]) -> String for the web editor to accept it.

class Solution {
    func tictactoe(_ moves: [[Int]]) -> String {
        
        let populatedBoard = populatedBoard(with: moves)
        
        if let winner = checkWon(board: populatedBoard) {
            return winner
        }
        
        if moves.count < 9 {
            return "Pending"
        } else {
            return "Draw"
        }
    }
    
    func populatedBoard(with moves: [[Int]]) -> [[Character]] {
        var playerAMoves = [[Int]]()
        var playerBMoves = [[Int]]()
        
        var board: [[Character]] = [
            [" ", " ", " "],
            [" ", " ", " "],
            [" ", " ", " "]
        ]
        
        for (index, move) in moves.enumerated() where index % 2 == 0 {
            playerAMoves.append(move)
        }
        
        for (index, move) in moves.enumerated() where index % 2 == 1 {
            playerBMoves.append(move)
        }
        
        for move in playerAMoves {
            board[move[0]][move[1]] = "X"
        }
        
        for move in playerBMoves {
            board[move[0]][move[1]] = "O"
        }
        
        return board
    }
    
    func checkWon(board: [[Character]]) -> String? {
        for index in 0...2 {
            // Player won horizontally in a row.
            if board[index][0] == board[index][1] && board[index][0] == board[index][2] {
                if board[index][0] == "X" {
                    return "A"
                } else if board[index][0] == "O" {
                    return "B"
                }
            }
            
            // Player won vertically in a column.
            if board[0][index] == board[1][index] && board[0][index] == board[2][index] {
                if board[0][index] == "X" {
                    return "A"
                } else if board[0][index] == "O" {
                    return "B"
                }
            }
        }
        
        // Player won diagonally between the top left and bottom right.
        if board[0][0] == board[1][1] && board[0][0] == board[2][2] {
            if board[0][0] == "X" {
                return "A"
            } else if board[0][0] == "O" {
                return "B"
            }
        }
        
        // Player won diagonally between the top right and bottom left.
        if board[0][2] == board[1][1] && board[0][2] == board[2][0] {
            if board[0][2] == "X" {
                return "A"
            } else if board[0][2] == "O" {
                return "B"
            }
        }
        
        return nil
    }
}
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Your code is written clearly, and works correctly as far as I can see. Some things can be improved, in my opinion.

Avoid magic constants

The characters " ", "O", "X" are used as possible values for the values of a field on the board. That is error-prone because the compiler would not detect typographical errors. If you assign "0" instead of "O" to a field then the program will behave incorrectly, but it may take some time to find the error. It is better to use an enumeration instead:

 enum Piece: Character, Equatable {
    case empty = " "
    case X = "X"
    case O = "O"
}

The raw Character value is not needed for this challenge, but makes it easier to print the fields for debugging purposes. The conformance to Equatable makes it possible to compare fields easily.

The enumeration is more memory efficient (each value is stored as a single byte) and possibly more time efficient, because comparing bytes is easier than comparing Characters (which represent “extended grapheme clusters” in Swift and consist of one or more Unicode scalar values).

The other magic constants are "A", "B", "Draw" and "Pending", which are prescribed by the problem description. But we can still use an enumeration for the internal representation of the game state

enum State {
    case pending
    case draw
    case win(Piece)
}

and translate that to the requested strings at a single place.

Avoid repetition

There are four occurrences of code like

if board[index][0] == "X" {
    return "A"
} else if board[index][0] == "O" {
    return "B"
}

in your program. One could make the checkWon() function return a piece ("X" or "O") instead, so that the translation to "A" and "B" is done only once in the calling function.

Use a type to represent the game board

With a struct TicTacToeBoard one can encapsulate the game logic in a (reusable) type, and hide the internal representation of the board from the outside. With a public interface like

struct TicTacToeBoard {

    enum Piece { ... }

    enum State { ... }

    subscript(row: Int, col: Int) -> Piece

    func state() -> State
}

the main function becomes

func tictactoe(_ moves: [[Int]]) -> String {
    var board = TicTacToeBoard()
    for (index, move) in moves.enumerated() {
        let isPlayerA = index.isMultiple(of: 2)
        board[move[0], move[1]] = isPlayerA ? .X : .O
    }
    
    switch board.state() {
    case .draw:
        return "Draw"
    case .pending:
        return "Pending"
    case .win(let piece):
        return piece == .X ? "A" : "B"
    }
}

which is easy to read and to understand. Without changing the algorithm of your logic to detect the winner, an implementation could look like this:

struct TicTacToeBoard {
    
    enum Piece: Character, Equatable {
        case empty = " "
        case X = "X"
        case O = "O"
    }
    
    enum State {
        case pending
        case draw
        case win(Piece)
    }
    
    private var grid: [[Piece]] =
        [
            [.empty, .empty, .empty],
            [.empty, .empty, .empty],
            [.empty, .empty, .empty]
        ]
    
    private var numMoves = 0
    
    subscript(row: Int, col: Int) -> Piece {
        get {
            return grid[row][col]
        }
        set {
            precondition(grid[row][col] == .empty)
            grid[row][col] = newValue
            numMoves += 1
        }
    }
    
    func state() -> State {
        for index in 0...2 {
            // Player won horizontally in a row.
            if grid[index][0] != .empty && grid[index][0] == grid[index][1]
                && grid[index][0] == grid[index][2] {
                return .win(grid[index][0])
            }
            
            // Player won vertically in a column.
            if grid[0][index] != .empty && grid[0][index] == grid[1][index]
                && grid[0][index] == grid[2][index] {
                return .win(grid[index][0])
            }
        }

        // Player won diagonally between the top left and bottom right.
        if grid[0][0] != .empty && grid[0][0] == grid[1][1]
            && grid[0][0] == grid[2][2] {
            return .win(grid[0][0])
        }
        
        // Player won diagonally between the top right and bottom left.
        if grid[0][2] != .empty && grid[0][2] == grid[1][1]
            && grid[0][2] == grid[2][0] {
            return .win(grid[0][2])
        }
        
        return numMoves == 9 ? .draw : .pending
    }
}

The use of string and character literals has been greatly reduced to a single place in the main function. Piece and State are “nested types” to that naming collisions with other code can not happen.

For debugging purposes you may want to add

extension TicTacToeBoard : CustomStringConvertible {
    var description: String {
        // I'll leave the implementation as an exercise ... :)
    }
}

so that print(board) prints a nice representation of the game board, either in the code or in the debugger.

Performance improvements

Some suggestions which may make your code faster:

  • Define an array of all “winning combinations” which are then checked in a single loop, or:

  • Check for a winner after every move. That makes more checks, but you only have to check the row and the column changed by the last move, and possibly the diagonals.

\$\endgroup\$
3
  • \$\begingroup\$ Can you give an example for the "array of all winning combinations"? \$\endgroup\$
    – muescha
    Apr 19, 2022 at 13:17
  • \$\begingroup\$ @muescha: I simply meant an array like [((0, 0), (0, 1), (0, 2)), ((1, 0), (1, 1), (1, 2)), ...] \$\endgroup\$
    – Martin R
    Apr 19, 2022 at 19:35
  • \$\begingroup\$ Since a win can't occur until at least the 5th play, maybe a guard statement should be added for a quick exit(return "Pending"). \$\endgroup\$
    – Marcy
    May 4, 2022 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.