The first task of this year qualification round of google code jam was only the problem: “check if a given tic-tac-toe game field has won by player “X” or “O” or it is a draw or “is not finished”. Read the complete description on the google code jam dashboard.
One change: There is a field “T” used as joker (for both player).
+----+ |XOOX| # The "\"-line with XXTX won! |OXXO| |OOTX| |OOOX| +----+
This kind of problem can easy solved with a regex if you use the field in one string:
lines = “XOOX\nOXXO\nOOTX\nOOOX”
my solution
import re, sys pattern = "OOOO|O....O....O....O|O.....O.....O.....O|O...O...O...O" checkO = re.compile(pattern, re.S) checkX = re.compile(pattern.replace("O","X"), re.S) def solve_with_regex(lines): #set T to O and test with the O-regex if checkO.search(lines.replace("T", "O")): return "O won" #set T to X and test with the X-regex if checkX.search(lines.replace("T", "X")): return "X won" if lines.find(".")!=-1: return "Game has not completed" return "Draw" #solved IN = file(sys.argv[1]) for t in range(1, int(IN.readline())+1): lines = "".join([IN.readline() for x in range(5)]) print "Case #%d: %s" % (t, solve_with_regex(lines))
solution with bit masks
The game field has 16 items with 4 states [“.”, “O”, “X”, “T”]. This can be converted into a 32 bit value. And if you choose “O”:1 and “X”:2 then will result “T”:3 with an AND-operation for both in a TRUE!
def solve_with_bits(lines): mapping = {".":0, "O": 1, "X":2, "T":3} m = 0 #convert input lines in 32-bit-number! for c in lines: if mapping.has_key(c): m = (m<<2)+mapping[c] pat = [(4, 0x55, 1, 7), # 4x, horicontal, 1 bit for O, 8 bit next test (4, 0x01010101, 1, 1), # 4x, vert. line, next Vert. only 1 bit (1, 0x01041040, 1, 1), # 1x, /, 1 bit shift (1, 0x40100401, 1, 1) # 1x, \, 1 bit shift ] #check win situation for O and X for loop, hBits, shift1, shift2 in pat: for i in range(loop): if m & hBits == hBits: return "O won" hBits = hBits << shift1 # 1 bit shift for X if m & hBits == hBits: return "X won" hBits = hBits << shift2 if lines.find(".")!=-1: return "Game has not completed" return "Draw"
The large data has 1000 testcases – this will easy fit with 2000 regex or 20*1000 bitmask checks in the 8 minuts time limit – the optimization was just for fun.
other solutions
- the java solution from toughprogramming is very long
- on puzzlers world is a simple count-solution 140 lines in java

Christian Harms

Latest posts by Christian Harms (see all)
- google code jam 2013 – tic-tac-toe-Tomek solution - April 16, 2013
- Google code jam 2013 – the lawnmower - April 14, 2013
- code puzzles and permutations - April 11, 2013