Tic-tac-toe 'get winner' algorithm As a first step to attempting the Weekend Challenger Reboot, I decided to first implement a regular 'tic-tac-toe' game and then expand it later to be 'ultimate tic-tac-toe'.

Below is the code for the tic-tac-toe board. It's fully functional and unit tested, but I'm not too happy about the getWinner() method. This method's purpose is to check to see if there is any winner in the game, and to return the identity of said winner if they exist.

The reasons I don't like it are:


The method is very long, which immediately sets off warning flags in my mind.
It makes use of a 'flag' type variable that tracks if we've found a winner yet. I don't like flag variables because they're really something that I got in the habit of doing back when I did procedural programming, and therefore probably shouldn't exist in an object-oriented design.
There's an awful lot of continue and break statements which seem to indicate poorly-designed loops.
I'm pretty sure that if there is no winner, this method is O(n2).


This is the code for the getWinner() method:

public class Board {
    private final Player[][] fields;
    ...
    public Player getWinner() {
        Player winner = null;
        boolean isWon = false;

        // check columns (same x)
        for (int x = 0; x &lt; fields.length; x++) {
            Player value = fields[x][0];

            if (value == null) {
                continue;
            }
            for (int y = 1; y &lt; fields[x].length; y++) {
                Player current = fields[x][y];
                if (current == null || !current.equals(value)) {
                    break;
                }
                if (y == fields[x].length -1) {
                    isWon = true;
                    winner = value;
                }
            }
            if(isWon) {
                break;
            }
        }

        if (! isWon) {
            // check rows (same y)

            for (int y = 0; y &lt; fields[0].length; y++) {
                Player value = fields[0][y];
                if (value == null) {
                    continue;
                }
                for (int x = 1; x &lt; fields.length; x++) {
                    Player current = fields[x][y];
                    if (current == null || !current.equals(value)) {
                        break;
                    }
                    if (x == fields.length -1) {
                        isWon = true;
                        winner = value;
                    }
                }
                if(isWon) {
                    break;
                }
            }

        }
        if (! isWon) {
            // check diagonal (bottom left to top right

            Player value = fields[0][0];
            if (value != null) {
                for (int i = 1; i &lt; fields.length; i++) {
                    if (fields[i][i] != value) {
                        break;
                    }
                    if (i == fields.length -1) {
                        isWon = true;
                        winner = value;
                    }
                }
            }
        }

        if (! isWon) {
            // check anti-diagonal (top left to bottom right)
            int length = fields.length;
            Player value = fields[0][length-1];
            if (value != null) {
                for (int i = 1; i &lt; length; i++) {
                    if (fields[i][length-i-1] != value) {
                        break;
                    }
                    if (i == length -1) {
                        isWon = true;
                        winner = value;
                    }
                }
            }
        }
        return winner;
    }
    ...
}


The rest of the code is mostly irrelevant. Something important to be aware of is that the board will always be a perfect square -- eg. 3x3 or 4x4 or 5x5. The Player is a simple enum:

public enum Player {
    X("X"),
    O("O");

    private String str;
    private Player(String str) {
        this.str = str;
    }

    @Override public String toString() {
        return str;
    }
}
It's method extraction time!

But before that, I have to comment on your Player enum:


str is a bad name, name would be better.
Speaking of name, all enums have a name() method by default. You don't need your str variable, return name(); instead.
Speaking of return name();, that's exactly what the default implementation of toString() already does for enums. Absolutely no need to override it.


And therefore, we've reduced your Player enum to:

public enum Player {
    X, O;
}


Ain't it lovely with enums? :)

Now, back to your getWinner() method:

You have a whole bunch of duplicated code there indeed. It would be handy if you could get a Collection of some kind (or an array), add some elements to it and check: Is there a winner given by these Player values?

This is just one version of doing it, it's not the optimal one but it should get you started. This code will add a bunch of Player objects to a list and then we check if those objects match to find if there's a winner.

List&lt;Player&gt; players = new ArrayList&lt;&gt;();
for (int x = 0; x &lt; fields.length; x++) {
    for (int y = 0; y &lt; fields[x].length; y++) {
        players.add(fields[x][y]);
    }
    Player winner = findWinner(players);
    if (winner != null) 
        return winner;
}

Player findWinner(List&lt;Player&gt; players) {
    Player win = players.get(0);
    for (Player pl : players) {
        // it's fine that we loop through index 0 again,
        // even though we've already processed it. 
        // It's a fast operation and it won't change the result
        if (pl != win)
            return null;
    }
    return pl;
}


Please note that there are even more improvements possible for the getWinner method, I don't want to reveal all my secrets for now though ;) And also, this is just one way of doing it, which will reduce your code duplication a bit at least. There are other possible approaches here as well.