2
\$\begingroup\$

I'm working on Tic Tac Toe and I want do it for any ROW x COL board with any WIN_SIZE (e.g. 4x4 board requires 3 to win). I've done the hasWon method already but I'm not sure is it done right. Can you check what can I do better here?

public boolean hasWon(Seed theSeed) {
    int count = 0;

    for (int col = 0; col < COLS; ++col) {               //check columns
        if (cells[currentRow][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }
    count = 0;

    for (int row = 0; row < ROWS; ++row) {              //check rows
        if (cells[row][currentCol].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }
    count = 0;

    int row = currentRow;

    for (int col = currentCol; col >= 0; --col) {      //check forward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

    count = 0;
    row = currentRow;

    for (int col = currentCol; col >= 0; --col) {  //check backward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    return false;
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Hope you get some nice answers! \$\endgroup\$ – Graipher Sep 11 '16 at 21:12
  • \$\begingroup\$ @Graipher Thanks, I hope i will able to help other people soon too. :) \$\endgroup\$ – Aro400 Sep 11 '16 at 21:27
  • 1
    \$\begingroup\$ Welcome to Code Review! You might be interested in some similar questions/posts: codereview.stackexchange.com/q/45086/31562 and codereview.stackexchange.com/a/97381/31562 . What I am trying to say is that you can use one method to loop through tiles and reuse that for both horizontal, vertical and diagonal. \$\endgroup\$ – Simon Forsberg Sep 12 '16 at 6:39
  • 2
    \$\begingroup\$ Is this a win for X: XXOX? It doesn't seem like X should win if there is an O blocking like that, but currently your code considers that a win. \$\endgroup\$ – JS1 Sep 12 '16 at 17:25
3
\$\begingroup\$
public boolean hasWon(Seed theSeed) {

What is a Seed? The way that you are using it, I'd expect a Player object.

    for (int col = 0; col < COLS; ++col) {               //check columns
        if (cells[currentRow][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

A more common format would be

    //check squares in currentRow
    for (int col = 0; col < COLS; ++col) {
        if (cells[currentRow][col].content == theSeed) {
            count++;
        } else {
            count = 0;
        }

        if (count == WIN_SIZE) {
            return true;
        }
    }

I added the else because I would expect a match to need to be consecutive. As is, you would accept any row containing WIN_SIZE total matches. Maybe that's what you want, but it's not what I would expect.

You iterate over columns when you are checking a row. The original comment was a bit confusing on that aspect.

While there is a single statement form of control structures (if), it is often recommended not to use it. It's less clear about what goes with what and it's easier to edit in a way that causes problems but is syntactically correct.

    count = 0;

    int row = currentRow;

    for (int col = currentCol; col >= 0; --col) {      //check forward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

This looks more complicated than it needs to be. Consider

    // check forward diagonal
    for (int col = currentCol, row = currentRow; col >= 0 && row >= 0; --col, --row) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

    for (int col = currentCol + 1, row = currentRow + 1; col < COLS && row < ROWS; ++col, ++row) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

Yes, you can use two variables in one for loop.

Rather than decrementing the count, this skips the current square in the second loop.

Or do the whole thing in one loop.

    // check forward diagonal
    count = 0;
    int col = 0;
    int row = 0;
    if (currentCol >= currentRow) {
        col = currentCol - currentRow;
    } else {
        row = currentRow - currentCol;
    }

    for (; col < COLS && row < ROWS; ++col, ++row) {
        if (cells[row][col].content == theSeed) {
            count++;
        }

        if (count == WIN_SIZE) {
            return true;
        }
    }

More work up front to figure out the first square in the diagonal, but only a single loop.

I left off the else case, as I'm not sure whether the current behavior is intentional or not. The single loop version works with the else as before. The double loop versions don't.

\$\endgroup\$
  • \$\begingroup\$ Good catch with the else count = 0; case. I think the intended behavior is/should be to require consecutive tiles. I am personally not a fan of using two loop variables (see TTWinCondition and TicUtils.setupWins in codereview.stackexchange.com/q/45086/31562 ) \$\endgroup\$ – Simon Forsberg Sep 12 '16 at 11:32
  • \$\begingroup\$ @mdfst13 thanks, your tips are very helpfull. \$\endgroup\$ – Aro400 Sep 14 '16 at 20:26
3
\$\begingroup\$

In your code there are four loops with very similar functionality. Each loop checks the board in a different direction. This could be extracted to a method and reuse the method 4 times:

/**
 * 
 * @param theSeed   Value expected in each cell
 * @param row       Row index to check
 * @param col       Col index to check
 * @param count     Number of consecutive elements found in the line. 
 * @param rowIncrement   Increment to the row index for the next evaluation
 * @param colIncrement   Increment to the col index for the next evaluation
 * @return  true if there is a winner combination in the line, otherwise false. 
 */ 
private boolean checkLine(Seed theSeed, int row, int col, int count, int rowIncrement, int colIncrement) {
    if (!areValidIndexes(row, col)) {
        return false;
    }

    if (theSeed == cells[row][col].getContent()) {
        count++;
        if (count >= WIN_SIZE) {
            return true;
        } else {
            return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement);
        }
    } else {
        return false;
    }
}


private boolean areValidIndexes(int row, int col) {
    if (row >= 0 && row < ROWS &&
        col >= 0 && col < COLS) {
        return true;
    }
    return false;
}

To simplify the usage of this method, we could create some wrapper method for each direction:

private boolean checkRow(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 1, 0);
}

private boolean checkColumn(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 0, 1);
}

private boolean checkForwardDiagonal(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 1, 1);
}

private boolean checkBackwardDiagonal(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, -1, 1);
} 

At this point, implement the hasWon method is very straightforward, just iterate over each cell and check each direction:

public boolean hasWon(Seed theSeed) {
    for (int row = 0; row < ROWS; row++) {
        for (int col = 0; col < COLS; col++) {
            if (checkRow(theSeed, row, col) ||
                checkColumn(theSeed, row, col) ||
                checkForwardDiagonal(theSeed, row, col) ||
                checkBackwardDiagonal(theSeed, row, col)) {

                return true;
            }
        }
    }
    return false;
}

UPDATE

As suggested in the comments, the algorithm could be more efficient if only the row, column and diagonals of the last move are checked.

The method checkLine would be more useful to implement this change if the full line is checked for a winner combination:

/**
 * 
 * @param theSeed   Value expected in each cell
 * @param row       Row index to check
 * @param col       Col index to check
 * @param count     Number of consecutive elements in the line. 
 * @param rowIncrement   Increment to the row index for the next evaluation
 * @param colIncrement   Increment to the col index for the next evaluation
 * @return  true if there is a winner combination in the line, otherwise false. 
 */
private boolean checkLine(Seed theSeed, int row, int col, int count, int rowIncrement, int colIncrement) {
    if (!areValidIndexes(row, col)) {
        return false;
    }

    if (theSeed == cells[row][col].getContent()) {
        count++;
        if (count >= WIN_SIZE) {
            return true;
        } else {
            return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement);
        }
    } else {
        // Reset the count and keep processing the line
        return checkLine(theSeed, row + rowIncrement, col + colIncrement, 0, rowIncrement, colIncrement);
    }
}

Now, the wrapper methods to check each direction have more functionality and they calculate the beginning of the row, column or diagonal. The methods for the row and column are straightforward, just set to 0 the index for the row or column:

private boolean checkRow(Seed theSeed, int row, int col) {
    return checkLine(theSeed, 0, col, 0, 1, 0);
}

private boolean checkColumn(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, 0, 0, 0, 1);
}

For the diagonals, we need to calculate the starting indexes. We are at the start of the diagonal when the row index or column index are in the edge, so we calculate the minimum distance to the edge and increase or reduce the indexes that amount:

private boolean checkForwardDiagonal(Seed theSeed, int row, int col) {
    int minDistanceToEdge = Math.min(row, col);
    return checkLine(theSeed, row - minDistanceToEdge, col - minDistanceToEdge, 0, 1, 1);
}

private boolean checkBackwardDiagonal(Seed theSeed, int row, int col) {
    int minDistanceToEdge = Math.min(ROWS - 1 - row, col);
    return checkLine(theSeed, row + minDistanceToEdge, col - minDistanceToEdge, 0, -1, 1);
}

The hasWon method can now use the wrapper functions to check only the row, column and diagonals of the last move:

public boolean hasWon(Seed theSeed, int row, int col) {
    return checkRow(theSeed, row, col) ||
           checkColumn(theSeed, row, col) ||
           checkForwardDiagonal(theSeed, row, col) ||
           checkBackwardDiagonal(theSeed, row, col);
}
\$\endgroup\$
  • \$\begingroup\$ I like your approach in one way, but your hasWon method will be ineffective. It is better to loop through all the rows and columns and diagonals and count all the tiles in a row while looping and then return if one of them has a win. See the determineWinnerNew method in TTWinCondition in my recursive Tic-Tac-Toe implementation (and also TicUtils.setupWins) \$\endgroup\$ – Simon Forsberg Sep 12 '16 at 11:28
  • \$\begingroup\$ @SimonForsberg So it is better to loop through all rows,columns and diagonals than just through these containing last move? \$\endgroup\$ – Aro400 Sep 12 '16 at 19:46
  • \$\begingroup\$ I don't see that you are only checking those containing the last move. If it can be done in a reliable way, then that would of course be very fast. As far as I can see in your current hasWon method, you are looping through all the rows and columns and then check all the rows, columns and diagonals connected to each tile. \$\endgroup\$ – Simon Forsberg Sep 12 '16 at 20:05
  • \$\begingroup\$ @SimonForsberg I updated the answer to improve the algorithm to only check the row, columns and diagonals of the last move. \$\endgroup\$ – David SN Sep 13 '16 at 7:54
  • 1
    \$\begingroup\$ I like the recursive solution, but why are you starting at 0 in your checkXXX checkLine, you could optimise it to check from current - sizeToWin to current + sizeToWin. No need to check the entire line (especially if the line is huge). Of course, the out of bounds need to be checked \$\endgroup\$ – AxelH Sep 15 '16 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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