Python for Bioinformatics: tic-tac-toe: utilities

Thursday, August 6, 2009

tic-tac-toe: utilities

Let's continue with what is admittedly a rather silly example: a simulation of tic-tac-toe boards with the ultimate goal of analyzing strategy. This post just gives some code for utility functions. For example, there are functions to give all rotations and reflections for a board.

There are other functions (not yet debugged properly) for assessing board status. If you want to follow along at home, save the code as TTTUtils.py on your Desktop so you can import it in the following steps.

Here is the output, along with comments to tell what is going on:

# start
1  2  3
4  5  6
7  8  9

# rotations (left)
3  6  9
2  5  8
1  4  7

9  8  7
6  5  4
3  2  1

7  4  1
8  5  2
9  6  3

# reflections
7  8  9
4  5  6
1  2  3

3  2  1
6  5  4
9  8  7

1  4  7
2  5  8
3  6  9

9  6  3
8  5  2
7  4  1

[Update: I added several functions (multipleReps, winners, doubleThreat, etc.)]
Here's the code:

rows =  [ [0,1,2], [3,4,5], [6,7,8] ]
cols =  [ [0,3,6], [1,4,7], [2,5,8] ]
diags = [ [0,4,8], [2,4,6] ]
corners = [0,2,6,8]
all =   rows + cols + diags

def boardRep(bL):
    rL = list()
    for iL in [[0,1,2],[3,4,5],[6,7,8]]:
        line = list()
        for i in iL:
            e = bL[i]
            if e:  line.append(e)
            else:  line.append('.')
        rL.append('  '.join(line))
    return '\n'.join(rL) + '\n'
    
def multipleReps(mD,kL):
    repL = list()
    for k in kL:
        repL.append(boardRep(mD[k]))
    pL = [[],[],[]]   
    for rep in repL:
        L = rep.strip().split('\n')
        for i,line in enumerate(L):
            pL[i].append(line)
    L = [k.ljust(11) for k in kL]
    pL.append(''.join(L))
    for i in range(3):  
        pL[i] = (' '*4).join(pL[i])
    return '\n'.join(pL) + '\n'
    
R = range(1,10)

def rotateLeft(bL):
    # easier to think in 1..9
    D = {1:3,2:6,3:9,4:2,5:5,
         6:8,7:1,8:4,9:7}
    # keep lists indexed in 0..8
    return [bL[D[i]-1] for i in R]

def threeRotations(bL):
    rL = list()
    for i in range(3):
        bL = rotateLeft(bL)
        rL.append(bL)
    return rL
    
def switch(bL,i,j):
    bL[i],bL[j] = bL[j],bL[i]
    
def fourReflections(L):
    rL = [ L[6:] + L[3:6] + L[:3] ]
    bL = L[:]
    for i,j in zip((0,3,6),(2,5,8)):
        switch(bL,i,j)
    rL.append(bL)
    bL = L[:]
    for i,j in zip((1,2,5),(3,6,7)):
        switch(bL,i,j)
    rL.append(bL)
    bL = L[:]
    for i,j in zip((1,0,3),(5,8,7)):
        switch(bL,i,j)
    rL.append(bL)
    return rL
    
def allPermutations(bL):
    rL = threeRotations(bL)
    rL.extend(fourReflections(bL))
    return rL

# find a line that can win
def winners(bL,who):
    #print 'test winners for', who
    #print boardRep(bL)
    rL = list()
    for line in all:
        vL = [bL[i] for i in line]
        vL.sort()
        if vL == [None, who, who]:
            for i in line:
                if not bL[i]:  break
            # return a list of (i, line)
            rL.append((i,line))
    #if rL:  print 'returning', rL,'\n'
    return rL
        
def doubleThreat(bL,p,v=False):
    if v:  print 'doubleThreat DT'
    iL = openPos(bL)
    rL = list()
    for i in iL:
        if v:  print 'testing', i
        bL2 = bL[:]
        bL2[i] = p
        if v:  print boardRep(bL2)
        wL = winners(bL2,who=p)
        if wL and len(wL) > 1:
            if v:  print 'DT saving', 
            if v:  print i
            rL.append(i)
    if v:  print 'DT returning', rL
    return rL

def promisingLines(bL,who):
    #print 'promisingLine', bL, who
    rL = list()
    for line in all:
        vL = [bL[i] for i in line]
        if vL.count(who) == 1:
            if vL.count(None) == 2:
                for i in line:  
                    if not i:  break
                rL.append((i,line))
    return rL
    
def wonPosition(bL):
    for line in all:
        vL = [bL[i] for i in line]
        if vL.count(None) == 0:
            p = vL[0]
            if vL.count(p) == 3:
                return p

def noPossibleWin(bL):
    for line in all:
        vL = [bL[i] for i in line]
        vL = [e for e in vL if e]
        if len(vL) == 1:  return False
        if len(vL) == 2:
            if vL[0] == vL[1]:  return False
    return True

def openPos(bL):
    return [i for i in range(len(bL)) if not bL[i]]

def closedPos(bL):
    return [i for i in range(len(bL)) if bL[i]]
    
def findKforBoard(bL):
    for k in mD:
        if mD[k] == bL:
            return k

if __name__ == '__main__':
    bL = list()
    for i in R:  bL.append(str(i))
    print boardRep(bL)
    for e in threeRotations(bL):
        print boardRep(e)
    for e in fourReflections(bL):
        print boardRep(e)