1
\$\begingroup\$

I am trying to write code to determine a win in tic-tac-toe game. In this question, I am not focusing on the whole game, I am only interested in the question of how to determine that the game ended with the victory of one of the players. So I made a synthetic example to test different approaches.

My guess is that a winning line on the board can only appear after the current player has made his move. Therefore, it makes no sense to check all the lines on the board. I only consider those that include the last move made. I assume that the board can be of any size (but only square) and the winning line has the same size. Thus, it is one of the rows, or one of the columns, or one of the two diagonals.

After several attempts, I ended up with the code below:

import java.util.List;
import java.util.function.Predicate;

enum Cell {
    X,
    O,
    B // blank cell
}

public class Board {

    private final int size = 3;
    private final Cell[][] board;

    public Board(Cell[][] board) {
        this.board = board;
    }

    private boolean isLineCompleted(Predicate<Integer> predicate) {
        boolean result = true;
        int i = 0;
        while (result && i < size) {
            result = predicate.test(i);
            i++;
        }
        return result;
    }

    public boolean hasWinningLine(int row, int col) {
        if (board[row][col] == Cell.B) return false;

        Cell base = board[row][col];
        List<Predicate<Integer>> checks = List.of(
                i -> board[row][i] == base, //columns
                i -> board[i][col] == base, //rows
                i -> board[i][i] == base,   //top-down diagonal
                i -> board[size - i - 1][i] == base //down-top diagonal
        );

        boolean lineCompleted = false;
        for (var check : checks) {
            if (!lineCompleted) {
                lineCompleted = isLineCompleted(check);
            }
        }

        return lineCompleted;
    }
}

And I wrote some tests that use this code something like this:

Cell[][] xWins = {
    {Cell.X, Cell.O, Cell.X},
    {Cell.O, Cell.X, Cell.O},
    {Cell.X, Cell.B, Cell.B}};

board = new Board(xWins);
AssertTrue(board.hasWinningLine(0, 2));

I have several questions:

  1. How easy is this code to read and understand? How can you improve it in this sense?

  2. I try not to make unnecessary checks. The algorithm should return false as soon as it finds an unsuitable cell. Should I handle the loop like this

for (var check : checks) {
            if (!lineCompleted) {
                lineCompleted = isLineCompleted(check);
            } else break; // That's better? 
        }

Is it possible to rewrite this loop using a stream API?

  1. When checking each line, this code can compare the cell to itself. How can i avoid this without complicating the code? Should I even think about it?

I am new to programming and would appreciate any advice that would help me code better.

EDITED: The predicate checking loop can be rewritten as

return checks.stream()
    .map(this::isLineCompleted)
    .filter(b -> b == true)
    .findFirst()
    .orElse(false);

What are the disadvantages of this approach?

\$\endgroup\$
3
\$\begingroup\$

First off, considering the small number of lines and items in a line, your (and my following) optimizations are probably not really worth it. That said, as you have noticed, your loops run through all all items, even when not necessary, and that would be bad in more complex situations.

Generally your code tends to be a bit too complex/verbose. For example, isLineCompleted would be much simpler using a regular for loop and early exit:

private boolean isLineCompleted(Predicate<Integer> predicate) {
    for (int i = 0; i < size; i++) {
         if (predicate.test(i)) {
             return true;
         }
    }
    return false;
}

By extracting the checks loop into a separate method, the same pattern could be used there.

Or Java's Stream has the .anyMatch() method, which simplifies it even more:

return checks.stream().anyMatch(this::isLineCompleted);

Using a IntStream allows isLineCompleted to do simular using .allMatch():

private boolean isLineCompleted(Predicate<Integer> predicate) {
    return IntStream.range(0, size).allMatch(predicate);
}

One final point: The value B in the Cell enum is badly named considering you need to add the comment "blank cell". Call it BLANK instead. Also it would seem more logical to put it first in the enum, where it would have the cardinal value 0. Or you may even want to drop it all together and just use null.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ isLineComplete(...) would need .allMatch(...), not .anyMatch(...), as the existence of just one match does not a complete line make. \$\endgroup\$ – AJNeufeld Feb 16 at 15:02
  • \$\begingroup\$ @AJNeufeld Yes, of course. Thank you. \$\endgroup\$ – RoToRa Feb 16 at 15:07
  • \$\begingroup\$ @RoToRa thanks a lot, it was helpful \$\endgroup\$ – chptr-one Feb 17 at 14:26
  • \$\begingroup\$ @RoToRa "Or you may even want to drop it all together and just use null." -- I try to avoid null wherever possible. Many people argue that using the null value is bad practice. \$\endgroup\$ – chptr-one Feb 17 at 14:34
  • 1
    \$\begingroup\$ Normally I'd agree, but in this case, there are less disadvantages. For example, there are no methods or fields that need to accessed from the instance. \$\endgroup\$ – RoToRa Feb 17 at 15:49
3
\$\begingroup\$

Bugs

Board Size

I assume that the board can be of any size (but only square) ...

private final int size = 3;

You mean, the board can be any size as long as it is 3-by-3?

Perhaps you meant ...

    private final int size;
    private final Cell[][] board;

    public Board(Cell[][] board) {
        this.board = board;
        this.size = board.length;
    }

hasWinningLine(row, col)

I only consider those that include the last move made.

In your test case, board.hasWinningLine(0, 0) would return true despite 0, 0 not being on a winning line. Your code unconditionally checks the diagonals.

Instead, your code should only add the diagonal checks if the last move was on those diagonals:

        List<Predicate<Integer>> checks = new ArrayList<>();
        checks.add(i -> board[row][i] == base);
        checks.add(i -> board[i][col] == base);
        if (row == col)
            checks.add(i -> board[i][i] == base);
        if (size - row - 1 == col)
            checks.add(i -> board[size - i - 1][i] == base);

        ...

Instead of building a temporary list, we could build a stream of predicates directly. For example, using .anyMatch() as suggested in RoToRa's answer:

        Stream.Builder<Predicate<Integer>> builder = Stream.builder();
        builder.add(i -> board[row][i] == base);
        builder.add(i -> board[i][col] == base);
        if (row == col)
            builder.add(i -> board[i][i] == base);
        if (size - row - 1 == col)
            builder.add(i -> board[size - i - 1][i] == base);

        Stream<Predicate<Integer>> stream = builder.build();
        return stream.anyMatch(this::isLineCompleted);
\$\endgroup\$
2
  • \$\begingroup\$ "Instead, your code should only add the diagonal checks if the last move was on those diagonals:" -- yes, my bad \$\endgroup\$ – chptr-one Feb 17 at 14:29
  • \$\begingroup\$ "You mean, the board can be any size as long as it is 3-by-3?" -- I mean, the algorithm is not tied to the board size. It should work at any size. private final int size = 3 -- just for example. And thank you very much, it was helpful too. \$\endgroup\$ – chptr-one Feb 17 at 14:30

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.