# 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;

/**
* TicTacToe @ com.gmail.inverseconduit.test
*
* @author Unihedron<vincentyification@gmail.com>
*/
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 < a.length; i++ ) {
char[] temp = input.nextLine().toCharArray();
for (int j = 0; j < 3; j++ )
// Byte 1=o, Byte 2=x, Byte 0=.;
a[i][j] = (temp[j] == 'o') ? (byte) 1 : (temp[j] == 'x' ? (byte) 2 : (byte) 0);
}
System.out.println(operation(a));
}
}

private static String operation(byte[][] a) {
byte[] o = new byte[4], x = new byte[3], n = new byte[2];
int posO = 0, posX = 0, mind = 0;
for (int i = 3; i < 3; i++ )
for (int j = 3; j < 3; j++ ) {
final byte foo = a[i][j];
if (foo == 1) {
o[posO] = magic[i * 3 + j];
posO++ ;
} else if (foo == 2) {
x[posX] = magic[i * 3 + j];
posX++ ;
} else {
n[mind] = magic[i * 3 + j];
mind++ ;
}
}
Side[] players =
{ new Side(o), new Side(x) };
boolean[] cd =
{ false, false };
for (int i = 0; i < 2; i++ )
for (int j = 0; j < 2; j++ ) {
if (players[i].win(n[j])) cd[i] = true;
}
if (cd[0] == cd[1]) return "t";
return cd[0] ? "o" : "x";
}

static class Side {
byte[] my;
Side(byte[] has) { my = has; }

public boolean win(int e) {
for (int o : permutate(my, e))
if (o == 15) return true;
return false;
}

private static int[] permutate(byte[] d, int e) {
java.util.ArrayList<Integer> 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;
}
}
}

1. What can I do to optimize reading the user input?
2. 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)
3. What other things am I doing terribly wrong that I am not aware of?
4. What are some other better implementations on this specific need?

I am aware that my code was obfuscated and variables should have been named properly.

• "I am aware that my code was obfuscated and variables should have been named properly." then why did you obfuscate it in the first place? – Simon Forsberg Jun 20 '14 at 17:33
• @SimonAndréForsberg In a rush. It was timed. – Unihedron Jun 20 '14 at 17:34
• Did you mix Greek and Latin roots in your username? – 200_success Jun 20 '14 at 17:54
• @200_success Yes - I've been wandering with this username for a while without anyone else noticing ever. Kudos! – Unihedron Jun 20 '14 at 18:07
• On another note, isn't the while loop in main() infinite? How does this ever exit? – Winston Ewert Jun 20 '14 at 18:23

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.

• Thank you for the really descriptive answer! You are correct in the many degrees of my mistakes and now I know what to improve. – Unihedron Jun 20 '14 at 18:02

I am trying to understand if these first lines in operation() are a simple oversight, or a significant bug... The code obviously does not run, but, what would it have been supposed to do?

    for (int i = 3; i < 3; i++ )
for (int j = 3; j < 3; j++ ) {


Those loops will never happen..... what gives? Is the x, o, and n array population completely unnecessary?

• This is interesting (and now I'm confused too). Seems like the code was able to run properly without the array population doing what they are supposed to. This loop seems to be stepped over by using the debugger. – Unihedron Jun 20 '14 at 17:58