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