1
\$\begingroup\$

I decided to finally write up a Tic-Tac-Toe implementation. Since I'm currently learning web development, I decided to write it in JavaScript.

My main problem, and what I want reviewed here is my checks to see if there are any winning plays on the board.

I figured the easiest way to start out with would be to "brute-force" it. I'm having it (automatically) check every possible winnable streak (each row, column, and the two diagonals) to see if there are any consecutive symbols.

The problem is, it's super anti-DRY. The row and column checking are nearly identical, just with certain aspects switched. The same is the case for the 2 diagonal checking. The check for the top-left to bottom-right diagonal is almost identical to the top-right to bottom-left diagonal, with a couple key differences. They share the same basic structure though.

In each, the algorithm is basically:

  • Store the contents of the first cell of the row/column/diagonal (starting from the top and/or right).
  • Go down each row/column/diagonal and see if the contents of all the successive cells match the first cell.
  • If they do, return the symbol for the winning piece, otherwise, return false;

I can't figure out how to reduce the copy-and-pasting though, even though they're very similar conceptually.

While the problem above is where I'd like most of the focus, I'll welcome any other feedback, expect for the suggestion to add JSDocs. I usually go back over my code after I write it, and have yet to do that.

The code in question (specifically checkCols, checkRows and checkDiags):

TicTacToeGame.js:

function TicTacToeGame(sideLength) {
    sideLength = sideLength || 3;

    var X_PIECE = "X";
    var O_PIECE = "O";

    var board = new Board(sideLength, sideLength);

    this.addX = function(pieceX, pieceY) {
        board.setSquare(pieceX, pieceY, X_PIECE);
    };

    this.addO = function(pieceX, pieceY) {
        board.setSquare(pieceX, pieceY, O_PIECE);
    };

    this.getBoard = function() {
        return board;
    }

    this.checkForWin = function() {
        return checkRows() || checkCols() || checkDiags();
    }

    this.toString = function() {
        return board.toString();
    }

    function checkRows() {
        for (var row = 0; row < sideLength; row++) {
            var initialPiece = board.getSquare(0, row);

            if (initialPiece === board.getEmptyPlaceholder()) {
                continue;
            }

            for (var col = 1; col < sideLength; col++) {
                var currentPiece = board.getSquare(col, row);

                if (currentPiece !== initialPiece) {
                    break;

                } else if (col === sideLength - 1) {
                    return initialPiece;
                }
            }

            if (row === sideLength - 1) {
                return false;
            }
        }

        return false;
    }

    function checkCols() {
        for (var col = 0; col < sideLength; col++) {
            var initialPiece = board.getSquare(col, 0);

            if (initialPiece === board.getEmptyPlaceholder()) {
                continue;
            }

            for (var row = 1; row < sideLength; row++) {
                var currentPiece = board.getSquare(col, row);

                if (currentPiece !== initialPiece) {
                    break;

                } else if (row === sideLength - 1) {
                    return initialPiece;
                }
            }

            if (col === sideLength - 1) {
                return false;
            }
        }

        return false;
    }

    //(2,0), (1,1), (0,2)

    function checkDiags() {
        //Check main diagonal
        //TODO Move topLeftPiece out of loop, and collapse if
        var topLeftPiece = board.getSquare(0, 0);
        for (var d = 0; d < sideLength; d++) {
            if (topLeftPiece === board.getEmptyPlaceholder()) {
                break;
            } 

            var currentPiece = board.getSquare(d, d);

            if (currentPiece !== topLeftPiece) {
                break;

            } else if (d === sideLength - 1) {
                return currentPiece;
            }

        }

        var topRightPiece = board.getSquare(sideLength - 1, 0);
        //Check inverse diagonal
        for (var d = 0; d < sideLength; d++) {
            if (topRightPiece === board.getEmptyPlaceholder()) {
                break;
            }             

            var currentPiece = board.getSquare(sideLength - d - 1, d);

            if (currentPiece !== topRightPiece) {
                break;

            } else if (d === sideLength - 1) {
                return currentPiece;
            }

        }

        return false;
    }
}

And a "support" class to help with managing the board (Board.js):

function Board(squaresWide, squaresHigh) {
    var self = this;

    var EMPTY_PLACEHOLDER = null;

    var dimensions = {
        width:  squaresWide,
        height: squaresHigh
    };

    var squares = createBoardArray(dimensions.width, dimensions.height);

    this.setSquare = function(x, y, object) {
        assertIsInBounds(x, y);

        squares[ getIndexOfSquare(x, y) ] = object;
    };

    this.getSquare = function(x, y) {
        assertIsInBounds(x, y);

        return squares[ getIndexOfSquare(x, y) ];
    };

    this.squareIsOccupied = function(x, y) {
        return this.isInBounds(x, y)
                && getSquare(x,y) !== EMPTY_PLACEHOLDER;
    }

    this.swapSquares = function(x1, y1, x2, y2) {
        assertIsInBounds(x1, y1);
        assertIsInBounds(x2, y2);

        var old1 = this.getSquare(x1, y1);
        var old2 = this.getSquare(x2, y2);

        this.setSquare(x1, y1, old2);
        this.setSquare(x2, y2, old1);
    }

    this.clearBoard = function() {
        squares = createBoardArray(dimensions.width, dimensions.height);
    };

    this.getEmptyPlaceholder = function() {
        return EMPTY_PLACEHOLDER;
    }

    /**
     * 
     * @param {Function} f function(x, y, cellContents)
     * @returns {undefined}
     */
    this.forEach = function(f) {
        for (var y = 0; y < dimensions.height; y++) {
            for (var x = 0; x < dimensions.width; x++) {
                f(x, y, this.getSquare(x, y));
            }
        }
    }


    this.toString = function() {
        var stringArr = [];

        for (var i = 0; i < squares.length; i++) {
            stringArr.push(
                squares[i] === EMPTY_PLACEHOLDER ?
                    '-' : squares[i]
            );

            if ((i + 1) % dimensions.width === 0) {
                stringArr.push('\n');

            } else {
                stringArr.push(' | ');
            }
        }

        return stringArr.join('');
    };

    this.isInBounds = function(x, y) {
        return  x >= 0 && x < dimensions.width &&
                y >= 0 && y < dimensions.height;
    }

    function assertIsInBounds(x, y) {
        if (!self.isInBounds(x, y)) {
            throw new Error("Coord out of bounds: (" + x + ", " + y + ")");
        }
    }

    function getIndexOfSquare(x, y) {
        return y * dimensions.width + x;
    }

    function createBoardArray(width, height) {
        var arr = [];

        var total = width * height;
        for (var i = 0; i < total; i++) {
            arr.push(EMPTY_PLACEHOLDER);
        }

        return arr;
    }

}

And the test page I've been using (BoardTest.html):

<!DOCTYPE HTML>
<html>
    <head>
        <title>TODO supply a title</title>
        <meta charset="UTF-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0">
    </head>
    <body>
        <script src="Board.js"></script>
        <script src="TicTacToeGame.js"></script>
        <script>
            console.info("Successes:");

            var game = new TicTacToeGame();
            game.addO(0,0);
            game.addO(1,1);
            game.addO(2,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addX(0,2);
            game.addX(1,1);
            game.addX(2,0);
            game.addO(0,0);
            game.addO(2,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addX(0,2);
            game.addX(1,2);
            game.addX(2,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addX(1,0);
            game.addX(1,1);
            game.addX(1,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addO(2,0);
            game.addO(2,1);
            game.addO(2,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            console.info("Failures:");

            // Next

            game = new TicTacToeGame();

            game.addX(1,1);
            game.addX(2,2);
            game.addX(1,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addX(0,0);
            game.addO(1,1);
            game.addX(2,2);

            console.log(game.toString());
            console.log(game.checkForWin());

            // Next

            game = new TicTacToeGame();

            game.addX(1,0);
            game.addO(1,1);
            game.addX(1,2);

            console.log(game.toString());
            console.log(game.checkForWin());


        </script>
    </body>
</html>
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Nice code! I'm going to start off my review with your code, and I'm going to end it with an alternate solution.


Now to check rows. Wait, no: columns. Wait - er, doesn't it really matter?

You guessed it; your code is pretty wet. Just stick your checkRows and checkCols functions through a diff tool. Really, the only major difference is this line:

var initialPiece = board.getSquare(0, row);

Other than that, it's a matter of life or death row or col in a variable name.

A simple fix would be to create a universal function between these two that takes another parameter that decides whether to check rows or columns:

function checkRows(isRow) {
    for (var i = 0; i < sideLength; i++) {
        var initialPiece = board.getSquare(isRow ? 0 : i, isRow ? i : 0);

        if (initialPiece === board.getEmptyPlaceholder()) {
            continue;
        }

        for (var j = 1; j < sideLength; j++) {
            var currentPiece = board.getSquare(j, i);

            if (currentPiece !== initialPiece) {
                break;

            } else if (j === sideLength - 1) {
                return initialPiece;
            }
        }

        if (i === sideLength - 1) {
            return false;
        }
    }

    return false;
}

Now, to check both rows and columns, simply call it twice providing a different boolean each time.


Diagonals are diagonals no matter how you cross them

You are right again: your diagonals-checking function is also pretty darn wet. This time, the only major difference is what parameter you are passing into a function. This can be solved just like it was done above:

function checkDiags(topLeft) {

    var piece = board.getSquare(topLeft ? 0 : sideLength - 1, 0);
    for (var d = 0; d < sideLength; d++) {
        if (piece === board.getEmptyPlaceholder()) {
            break;
        } 

        var currentPiece = board.getSquare(topLeft ? d : sideLength - d - 1, d);

        if (currentPiece !== topLeftPiece) {
            break;

        } else if (d === sideLength - 1) {
            return currentPiece;
        }

    }
}

Like above, you'll have to call this function twice for each boolean. As shown above, the only changes really made were to the first argument of the two calls to board.getSquare


Hotdog vendor: one hotdog for you, and for you: a tuna salad

It is best to have return values that are consistent in type for each function. This keeps your code understandable and easy to follow.

For example, your check--- functions all either return "X", "O", or false. This is inconsistent; what's that boolean doing there?

It'd probably be best here to return "" (or maybe null) instead.


Misc.

Here are some small things I noticed

  1. addX and addO can become one function addPiece where the specific piece is provided through a parameter.
  2. It might be cleaner to create a players object with fields X and O. I dunno; it might seem a bit cleaner.
  3. If you don't absolutely need null to be the empty square placeholder, you can simplify your createBoardArray function to just return Array(width * height)

Now, here's my alternate solution


Here's a list of everything you need to do to figure who won

When I've made TTT programs in the past, I always thought that the best way to determine a winner was with a list/array of all the possible win conditions with a 0-based, linear board. Here's what I mean:

var winConditions = [
    [0, 1, 2], // first row and so on..
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6], // first column and so on...
    ...
];

Then, to check if someone won, you simply loop through this array, then check the three squares as shown by the array at that index. If they're all the same, then that letter won and you can stop looping.

This solution runs in \$O(n)\$ time, where n is 8 because there are 8 different solutions to check. Your solutions have multiple, nested loops which have a higher time complexity.

\$\endgroup\$
3
  • \$\begingroup\$ Awesome, thank you. Just a question about your suggestion to change my existing functions. I was under the impression that providing a flag parameter to change the behavior of the function is poor form. Obviously though, it's likely better than my current way since it greatly reduces duplication. Is this just a limitation of my original design? And I have to admit I don't understand your matrix solution. I also wanted to allow the board to be of variable length, so a static matrix wouldn't work. Is it possible to generate the matrix? \$\endgroup\$ Mar 21, 2016 at 22:52
  • \$\begingroup\$ @Carcigenicate (1) I've never been told that using a flag parameter is bad, but I could very well be wrong. But honestly, a flag parameter really helps dry up your code. (2) Each number in the inner lists represent an index on the TTT board; you check all three indices for the same character. The current provided list would not work for variable length boards; you also didn't mention you were planning on having a variable-length board in you question. And yes: you could generate this list. Do you want me to update my question with a way to automatically generate the matrix? \$\endgroup\$
    – SirPython
    Mar 21, 2016 at 23:01
  • \$\begingroup\$ Thanks, I'm sure I could figure out a generator once I understand it. I just got off work, so my brains a little tired. I'll give it a look over tomorrow. Thanks again, it definitely helped. \$\endgroup\$ Mar 21, 2016 at 23:25

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.