halma_verify.py

import cStringIO, math, sys
class Board:
    start_locations = [
        [(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),
               (1,2),(1,3),(1,4),(2,0),(2,1),(2,2),
               (2,3),(3,0),(3,1),(3,2),(4,0),(4,1)],
        [(11,14),(11,15),(12,13),(12,14),(12,15),(13,12),(13,13),
                 (13,14),(13,15),(14,11),(14,12),(14,13),(14,14),
                 (14,15),(15,11),(15,12),(15,13),(15,14),(15,15)]]
    adjacent = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if i or j]
    def __init__(self,board=None):
        if board != None:
            self.board = board
        else:
            self.board = [[-1]*16 for i in range(16)]
            for p in (0,1):
                for (x,y) in Board.start_locations[p]:
                    self.board[x][y] = p
        self.player = 0
        self.opponent = 1
    def __str__(self):
        s = cStringIO.StringIO()
        for y in range(16):
            for x in range(16):
                s.write(['0','1','+'][self.board[x][y]])
            s.write('\n')
        v = s.getvalue()
        s.close()
        return v
    def on_board(self,x,y):
        return 0<=x<16 and 0<=y<16
    #Assumes move is valid
    def move(self,m):
        if m != None:
            fx,fy,tx,ty = m
            self.board[tx][ty] = self.board[fx][fy]
            self.board[fx][fy] = -1
        self.player,self.opponent = self.opponent,self.player
    def undo(self,m):
        self.player,self.opponent = self.opponent,self.player
        if m != None:
            fx,fy,tx,ty = m
            self.board[fx][fy] = self.board[tx][ty]
            self.board[tx][ty] = -1
    #all the legal moves from the current player
    def legal_moves(self, player=None):
        if player == None:
            player = self.player
        ms = [None]
        for x in range(16):
            for y in range(16):
                if self.board[x][y] == player:
                    ms.extend(self._steps_from(x,y))
                    ms.extend(self._jumps_from(x,y))
        return ms
    #the number of pieces player has in their goal
    def goal_count(self, player=None):
        if player == None:
            player = self.player
        n = 0
        opponent = 1-player
        for (x,y) in Board.start_locations[opponent]:
            if self.board[x][y] == player:
                n += 1
        return n
    #return True if the game is over
    def game_over(self):
        for p in (0,1):
            if self.goal_count(p) == 19:
                return True
        return False
    #verifies that a move is legal (slow)
    def verify(self,m,player=None):
        return m in self.legal_moves(player)
    def _steps_from(self,x,y):
        ms = []
        for (dx,dy) in Board.adjacent:
            tx,ty = x+dx, y+dy
            if self.on_board(tx,ty) and self.board[tx][ty] == -1:
                ms.append((x,y,tx,ty))
        return ms
    def _jumps_from(self,x,y,fx=None,fy=None):
        if fx == None:
            fx = x
        if fy == None:
            fy = y
        ms = []
        temp = self.board[x][y]
        self.board[x][y] = -2
        for (dx,dy) in Board.adjacent:
            mx,my = x+dx,y+dy
            tx,ty = mx+dx,my+dy
            if self.on_board(tx,ty):
                if self.board[mx][my] >= 0 and self.board[tx][ty] == -1:
                    ms.append((fx,fy,tx,ty))
                    ms.extend(self._jumps_from(tx,ty,fx,fy))
        self.board[x][y] = temp
        return ms

board = Board()
n = 0
while True:
    try:
        move = input()
    except EOFError:
        break
    if not board.verify(move):
        print 'Illegal move on line %d:\n' % (n + 1)
        print move,'player',board.player,'\n'
        print board
        sys.exit()
    board.move(move)
    n += 1
if board.game_over():
    print 'Verified at %d moves.' % n
else:
    print 'The game\'s not finished!'
    print board