ChessMetric - Topcoder Challenge

My solution for the topcoder ChessMetric challenge seems really slow. I feel like there should be a better way, but I'm not sure.


Challenge Description


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 int[]s 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 = [

Since you have decided to go the way of the specialized object for your board, there are two obvious improvements. One is to use Python magic methods to have a more pythonic notation. The other is to offload the bounds checking to this specialized class. For instance:

class Board(object):
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.board = [[0] * cols for row in range(rows)]

    def __getitem__(self, index):
        row, col = index
        if 0 <= row < self.rows and 0 <= col < self.cols:
            return self.board[row][col]
        return 0

    def __setitem__(self, index, value):
        row, col = index
        if 0 <= row < self.rows and 0 <= col < self.cols:
            self.board[row][col] = value

This simple class lets you use typical Python indexing with square brackets to access the board, and silently handles out of bounds access.

You may also want to be a little terser about generating your moves. This is one of many options:

def kingknight_moves(start):
    row, col = start
    dest = []
    for dr in range(-2, 3):
        cols = (1, -1) if abs(dr) != 1 else range(-2, 3)
        for dc in cols:
            dest.append((row + dr, col + dc))
    return dest

I'm also going to write a function to advance the board one move:

def advance_board(board):
    new_board = Board(board.rows, board.cols)
    for row in range(board.rows):
        for col in range(board.cols):
            count = board[row, col]
            if count:
                for dest in kingknight_moves((row, col)):
                    new_board[dest] += count
    return new_board

This is pretty much the same you are doing, modulo a nicer syntax.

Now to the meat of the problem... A naive approach like the one you have implemented works:

def chess_metric_naive(size, src, dst, moves):
    board = Board(size, size)
    board[src] = 1

    for move in range(moves):
        board = advance_board(board)

    return board[dst]

But is indeed kind of slow for the largest of the problems posed:

%timeit chess_metric_naive(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 3.7 s per loop

If you were to time each of your iterations advancing the board one move, you would notice that they get progressively slower, as more and more cells are non-zero and contribute to their neighbors. One way of mitigating this effect is to, rather than completing all moves from the source towards the destination, do half of them like this, and the rest from destination to source. If there are \$m\$ ways of getting from the source to a certain cell in half the moves, and \$n\$ ways of getting from the destination to the same cell in the remaining moves, then there are \$mn\$ ways of getting from source to destination. You could implement this like:

def chess_metric(size, src, dst, moves):
    src_board = Board(size, size)
    src_board[src] = 1
    dst_board = Board(size, size)
    dst_board[dst] = 1

    for move in range(moves // 2):
        src_board = advance_board(src_board)
        dst_board = advance_board(dst_board)

    if moves % 2:
        src_board = advance_board(src_board)

    total = 0
    for row in range(size):
        for col in range(size):
            total += src_board[row, col] * dst_board[row, col]

    return total

And it turns out to be substantially (3x) faster:

%timeit chess_metric(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 1.2 s per loop

We can do even better though: an alternative approach is to use something akin to a branch and bound approach. We know that the maximum distance that our made up chess piece can move is \$\sqrt 5\$, so we need not consider cells that are further from the destination more than that value times the number of moves left. A possible approach is to create a board holding minimum number of moves to get to the destination from any other cell:

def moves_lower_bound(rows, cols, dst):
    from math import sqrt, ceil
    dst_row, dst_col = dst
    board = Board(rows, cols)
    for row in range(rows):
        row2 = row - dst_row
        row2 *= row2
        for col in range(cols):
            col2 = col - dst_col
            col2 *= col2
            dist2 = row2 + col2
            # rounded up int division dist2 // 5
            board[row, col] = int(ceil(sqrt(dist2) / sqrt(5)))
    return board

With the aid of this auxiliary board, we can prune the cells that cannot add to the final result whenever we advance the board:

def advance_and_prune_board(board, bounds, moves_left):
    new_board = Board(board.rows, board.cols)
    for row in range(board.rows):
        for col in range(board.cols):
            count = board[row, col]
            if count and bounds[row, col] <= moves_left:
                for dest in kingknight_moves((row, col)):
                    new_board[dest] += count     
    return new_board

Putting all this together:

```
def chess_metric_bb(size, sr

StackExchange Code Review Q#100980, answer score: 4