My solution for the topcoder ChessMetric challenge seems really slow. I feel like there should be a better way, but I'm not sure.
Suppose you had an n by n chess board and a super piece called a kingknight. The kingknight can move either one space in any direction (vertical, horizontal or diagonally) or can make an 'L' shaped move. An 'L' shaped move involves moving 2 spaces horizontally then 1 space vertically or 2 spaces vertically then 1 space horizontally.
Given the size of the board, the start position of the kingknight and the end position of the kingknight, your method will return how many possible ways there are of getting from start to end in exactly numMoves moves. start and finish are ints each containing 2 elements. The first element will be the (0-based) row position and the second will be the (0-based) column position. Rows and columns will increment down and to the right respectively. The board itself will have rows and columns ranging from 0 to size-1 inclusive.
class Board: def __init__(self, size): self.size = size self.board = [[0 for _ in xrange(size)] for _ in xrange(size)] def copy(self): c = Board(0) board_copy =  for val in self.board: board_copy.append(val[:]) c.board = board_copy c.size = self.size return c def is_valid(self, space): i, j = space return 0 <= i < self.size and 0 <= j < self.size def set(self, space, val): assert self.is_valid(space), "Invalid space: set()" i, j = space self.board[i][j] = val assert self.get(space) == val, "Problems in set" def get(self, space): assert self.is_valid(space), "Invalid space: get()" i, j = space return self.board[i][j] def get_adj(self, space): assert self.is_valid(space), "Invalid space: get()" i, j = space result = [ (i+1, j), (i-1, j), (i, j+1), (i, j-1), (i+1, j+1), (i-1, j-1), (i+1, j-1), (i-1, j+1), (i+1, j+2), (i+1, j-2), (i-1, j+2), (i-1, j-2), (i+2, j+1), (i-2, j+1), (i+2, j-1), (i-2, j-1), ] result = filter(self.is_valid, result) return result def chess_metric(size, start, finish, move_limit): board = Board(size) board.set(start, 1) aux = board.copy() for _ in xrange(move_limit): print _ for i in xrange(size): for j in xrange(size): current_space = (i, j) current_val = board.get(current_space) if current_val == 0: continue for neighbor in board.get_adj(current_space): neighbor_val = aux.get(neighbor) new_val = current_val + neighbor_val aux.set(neighbor, new_val) board = aux.copy() return aux.get(finish)