Google Code Jam 2013 - Tic-Tac-Toe-Tomek
Almost two weeks ago, I participated in the Qualification Round of the Google Code Jam. The Google Code Jam is a competitive algorithm programming competition with multiple online rounds before the on-site finals at a Google campus somewhere in the world. This year's finals are in London.
For the Qualification Round, contestants have to reach a point threshold during a 25h period. Because only points matter at this phase, one can attempt all the problems without worry of penalties. I solved small and/or large datasets for three out of four problems securing a spot in Round 1. In this and the next couple posts, I'm going to go through my solutions. The stuff for file input and ouput and counting the number of test cases is pretty mundane so I'll be leaving those parts out.
The first problem I attempted was titled Tic-Tac-Toe-Tomek, a modified take on Tic-Tac-Toe. The task was to take a 4x4 grid and determine the game state(X won, O won, draw, or game not finished). A player could win with 3 of their symbols and a 'T' or 4 of their symbols. I used Groovy, a dynamic language on the JVM, for this solution.
Tic-Tac-Toe-Tomek Solution
I began with a small snippet of code to read in the lines of the grid. These are four of the ten variations we need to check for wins. The last line calls checkWinner which does the real work.
def a,b,c,d
a = lines.remove(0)
b = lines.remove(0)
c = lines.remove(0)
d = lines.remove(0)
text += "Case #${i}: ${checkWinner(a,b,c,d)}\n"
Upon receiving the input strings, I created the other test cases benefiting from the fact that strings in Groovy can use array indexes instead of the longer to type charAt.
def checkWinner = {a,b,c,d ->
def winner = ""
// down
def g = a[0]+b[0]+c[0]+d[0]
def h = a[1]+b[1]+c[1]+d[1]
def m = a[2]+b[2]+c[2]+d[2]
def n = a[3]+b[3]+c[3]+d[3]
//diag
def o = a[0]+b[1]+c[2]+d[3]
def p = a[3]+b[2]+c[1]+d[0]
[a,b,c,d,g,h,m,n,o,p].each {
def x = []
x.addAll(it.toCharArray())
x.sort()
if (x.join('').equals('TXXX') || x.join('').equals('OOOT') || x.join('').equals('XXXX') || x.join('').equals('OOOO')) {
x = x - 'T'
winner = x[0].toString() +" won"
} else {
def xx = a + b + c + d
if (xx.indexOf('.') == -1 && !winner.equals("X won") && !winner.equals("O won"))
winner = "Draw"
else if (winner == "")
winner = "Game has not completed"
}
}
return winner
}
As opposed to having a bunch of if-statements to check every permutation of O's, X's, and T's, I instead sorted the strings to get them into one of a few known states. The String class doesn't give you an easy way to sort strings so you have to create an ArrayList and then add the output of toCharArray to the collection. You can get a string back out by calling join on the collection. Trying to do the same in Java would be much more verbose.
After getting the resulting sorted strings, I checked them against the four base states for a win. If a winner is not declared and there are empty slots, the game isn't done. If there are no empty slots, it's a draw.
Further Optimizations
Having some time away from the problem, if I were to do it again, I might attack it in a slightly different way. What if the sorting wasn't needed? Groovy allows us to call unique on a collection to get the unique values. If you had a line represented by ['X','X','X','X'] or ['X','X','T','X'], calling unique would return ['X'] or ['X','T'], both indicating a win. The set ['.', 'O', 'X'] would disqualify a win.
Conclusion
Tic-Tac-Toe-Tomek was a fun first problem and I was able solve both the small and large datasets receiving 30 of the 35 points needed to advance to the next round.