Dynamic programming solution for finding the longest sequence of length 2^n in a m x o matrix (Winner

connect4.py

'''Expressing "Find the winner in connect 4" as a dynamic programming
problem.
'''

import json
lines = []
while True:
    try:
        lines.append(raw_input())
    except EOFError:
        output = '\n'.join(lines)
        break

board_as_arrays = json.loads(output)

NUM_ROWS = len(board_as_arrays)
NUM_COLUMNS = len(board_as_arrays[0])

ROWS = range(NUM_ROWS)
COLUMNS = range(NUM_COLUMNS)

#print '\n'.join([str(x) for x in board_as_arrays])

# EVERYTHING ABOVE HERE IS BORING

# Sparse board
board = {(i,j):board_as_arrays[i][j] for i in ROWS for j in COLUMNS}
VECTORS = [(1,0), (1,1), (1, -1), (0, 1)]

#Memoisation
class Memo(object):
    def __init__(self, fn):
        self.fn = fn
        self.cache = {}
    def __call__(self, *args):
        if args not in self.cache:
            self.cache[args] = self.fn(*args)
        return self.cache[args]


def win(board, line_size, player):
    set_of_lines = frozenset([((row, column), vector,)
                        for (row, column) in board
                        for vector in VECTORS if board[row, column] == player])
    return check(set_of_lines, 4)

#0,0, 1,1 -> check 1,1, 2,2, 3,3
#0,0, 1,1 -> check 1,1,1,1

def filter_breaker(hot_set, n):
    def break_filter(point_vector):
        '''If we are looking for point 0,0 along vector 1,1 at length 2,
           Then we see if 1,1, 1,1 is in check(hot_set
        '''
        point, vector = point_vector
        row, column = point
        d_row, d_column = vector
        return ((row + d_row * n, column + d_column * n), (d_row, d_column)) in hot_set
    return break_filter

@Memo
def check(hot_set, n):
    '''Returns a set of point, vectors in the board where there is a
    contiguous series of length n along vector starting at point.
    '''
    if n is 1:
        return hot_set # Trivially true.
    else:
        half_n = check(hot_set, n/2) # looking for paths of length n/2

        #Filter based on
        # in the half_n, for every point, vector,
        # Does point + (vector * n/2) exist in the half_set?
        return frozenset(filter(filter_breaker(half_n, n/2),
                          half_n))

winner = False
for player in 'XO':
    if win(board, 4, player):
        print 'Winner: {}'.format(player)
        winner = True
if not winner:
    print "No winner"