Optimizing this inefficient TicTacToe configuration parser

On a programming contest I came upon this question:


Given a partially played 3 × 3 tic-tac-toe configuration, write a program to determine which player will have a better chance of winning if the game is continued, with player "x" playing next. The players are dumb robots and will pick an empty square randomly.


Output "o" if player "o" has a higher chance of winning, "x" if player "x" has a higher chance of winning, or "t" (for "tie") otherwise.

Sample input

oox
xox
o..

Sample output

t

My solution works and but was graded as "inefficient":

package com.gmail.inverseconduit.test;

/**
 * Procrastination: I'll add a javadoc description later.
 * TicTacToe @ com.gmail.inverseconduit.test
 * 
 * @author Unihedron
 */
public class TicTacToe {

    private static java.util.Scanner input = new java.util.Scanner(System.in);
    private final static byte[]      magic =
                                           { 2, 9, 4, 7, 5, 3, 6, 1, 8 };
                                     // Magic Square implementation.
    public static void main(String[] args) {
        while (true) {
            byte[][] a = new byte[3][3];
            for (int i = 0; i  b = new java.util.ArrayList();
            final int l = d.length + 1;
            for (int i = 0; i < l; i++ )
                for (int j = 0; j < i; j++ )
                    for (int k = 0; k < i; k++ ) {
                        if ( !((i == j) || (i == k) || (j == k))) b.add((i < l - 1 ? d[i] : e) + (j < l - 1 ? d[j] : e) + (k < l - 1 ? d[k] : e));
                    }
            java.util.Collections.sort(b);
            final int c = b.size();
            int[] stack = new int[c];
            final Integer[] g = b.toArray(new Integer[c]);
            for (int i = 0; i < g.length; i++ )
                stack[i] = g[i];
            return stack;
        }
    }
}

• What can I do to optimize reading the user input?

• What can I do to optimize resource efficiency and how I am dea

What can I do to optimize reading the user input?

Don't. For these kind of problems you will virtually never need to worry about time spent reading input.


What can I do to optimize resource efficiency and how I am dealing
with the data? I stored bytes instead of char which I think was pretty
clever (I would had stored the board configuration in three shorts but
a board is 9-grid, not 8-grid)

Actually, using bytes wasn't a good idea. You already had char arrays, and then you copied them into byte arrays. The end result is that you used more memory then if you had just used the char arrays. Its especially silly because you throw away the byte array right away in favor of a magic square representation. On top of that, your code is harder to follow and has more potential for mistakes with the copy.

What's actually killing you is this:

for (int i = 0; i < 2; i++ )
    for (int j = 0; j < 2; j++ ) {
        if (players[i].win(n[j])) cd[i] = true;
    }

which eventually calls:

for (int i = 0; i < l; i++ )
    for (int j = 0; j < i; j++ )
        for (int k = 0; k < i; k++ ) {
            if ( !((i == j) || (i == k) || (j == k))) b.add((i < l - 1 ? d[i] : e) + (j < l - 1 ? d[j] : e) + (k < l - 1 ? d[k] : e));
        }

You have 5 nested for loops. If there's one thing you should avoid to get efficient code, it is nested loops.

You are trying to determine if taking a certain square will produce victory. You do this by looking at all possible sums of the magic square to see if any equal 15. But looking at all possible sums is going to take longer than simply doing the simple tic-tac-toe check.

But then the piece of code immediately after that is, quite frankly, really bad.

java.util.Collections.sort(b);
final int c = b.size();
int[] stack = new int[c];
final Integer[] g = b.toArray(new Integer[c]);
for (int i = 0; i < g.length; i++ )
    stack[i] = g[i];
return stack;

Presumably, you are converting to int[] because ArrayList<> aren't as efficient. Firstly, the magnitude of that effect here is really small. You shouldn't be worried about it. Focus on your algorithm. Secondly, converting from ArrayList<> to int[] is itself slow. Whatever speed advantage you might have gained from using int[], you more than lose because of the time spent converting the ArrayList<> to the int[]. 95% of the time, you are better off just using the ArrayList<> rather than converting it.

Your code is especially wrong on this count, because it sorts for no reason, and then copies the array twice. You can just return the array list. Or, even better you can skip storing the item in the list at all. You only care if the sum is 15. Check that right away, and don't store all the values you don't care about in a list to be checked later.

StackExchange Code Review Q#54811, answer score: 15