ChessMetric - Topcoder Challenge

Question

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 = [
            (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)

Answer 1

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, src, dst, moves):
    board = Board(size, size)
    board[src] = 1
    bounds = moves_lower_bound(size, size, dst)

    for move in range(moves):
        board = advance_and_prune_board(board, bounds, moves - move)

    return board[dst]

We get close to a 9x improvement over the simpler approach:

%timeit chess_metric_bb(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 424 ms per loop

Answer 2

My suggestions:

• Avoid copying the board, this is very expensive. Try to make and undo the moves. Maybe this will be easier to implement using a recursive function.

• Instead of using a 2 dimensional array to represent the board, you can use a 1 dimensional array (for instance with a 2 square border on the board to detect when you're going off the board), and then define the moves accordingly.

---

Update: (1D solution based on backtracking, not suited for long paths)

To illustrate how nice it is in 1 dimension, I added a complete solution (<50 lines) that also prints every possible path. (Note: In this code each path will visit each square only once. The code will be ever simpler if you remove this restriction.)

size=8
start=[0,0]
finish=[7,7]
moves=9

#transform to 1D:
t=size+4
A=start[0]+2+(start[1]+2)*t
B=finish[0]+2+(finish[1]+2)*t

#board
b=[-1]*t*t
for i in range(size*size):
    b[i%size+2+(i/size+2)*t]=0

#moves
m=[-t-t-1,-t-t+1,-t-1-1,-t+1+1,t-1-1,t+1+1,t+t-1,t+t+1]

#search
total=0

def dump():
    txt="\nSolution "+str(total)+":\n"
    for i in range(2*t,(size+2)*t,t):
        for j in range(size):
            txt+=".123456789"[b[i+2+j]]
        txt+="\n"
    print txt

def doit(pos,count):
    global total
    if b[pos]!=0:
        return
    b[pos]=count
    if count<moves:
        for step in m:
            doit(pos+step,count+1)
    if count==moves:
        if pos==B:
            total=total+1
            dump()
    b[pos]=0

doit(A,1)

print total

Answer 3

Actually, you cannot solve the final problem with 50 steps using backtracking (like I propose it in my previous answer). With 16 moves per step, you'd have to check (with a forward backward approach) around $$2\cdot 16^{25}=2535301200456458802993406410752$$possibilities, which is unfeasible.

---

1D solution based on a convolution (that works for long paths)

A faster approach, which will also work for long paths, is to repeatedly convolve the moves with the board (as proposed by the author of the question). The following program computes the correct solution to the final problem in 0.37 seconds on my computer. (I use again the 1D representation.)

size=100
start=[0,0]
finish=[0,99]
moves=50

#transform to 1D:
t=size+4
t2=t*t
A=start[0]+2+(start[1]+2)*t
B=finish[0]+2+(finish[1]+2)*t

#board
board=[0]*t2
c=[]
for i in range(size*size):
    c+=[i%size+2+(i/size+2)*t]

#moves
m=[-t-1,-t,-t+1,-1,+1,t-1,t,t+1]
m+=[-t-t-1,-t-t+1,-t-1-1,-t+1+1,t-1-1,t+1+1,t+t-1,t+t+1]

#search
def convolve(b):
    r=[0]*t2
    for i in c:
        y=b[i]
        if y!=0:
            for j in m:
                r[i+j]+=y
    return r

board[A]=1
for i in range(moves):
    board=convolve(board)
print board[B]

---

Even faster 1D solution (convolution with forward/backward optimization)

When I add the forward/backward optimization suggested by Jaime (i.e., I compute half the moves from the start position and then half the moves from the end position, and then combine), then I get down to 0.10 seconds for the final problem.

size=100
start=[0,0]
finish=[0,99]
moves=50

#transform to 1D:
t=size+4
t2=t*t
A=start[0]+2+(start[1]+2)*t
B=finish[0]+2+(finish[1]+2)*t

#board
board1=[0]*t2
board2=[0]*t2
c=[]
for i in range(size*size):
    c+=[i%size+2+(i/size+2)*t]

#moves
m=[-t-1,-t,-t+1,-1,+1,t-1,t,t+1]
m+=[-t-t-1,-t-t+1,-t-1-1,-t+1+1,t-1-1,t+1+1,t+t-1,t+t+1]

#search
def convolve(b):
    r=[0]*t2
    for i in c:
        y=b[i]
        if y!=0:
            for j in m:
                r[i+j]+=y
    return r

board1[A]=1
for i in range(moves/2):
    board1=convolve(board1)

board2[B]=1
for i in range((moves+1)/2):
    board2=convolve(board2)

total=0
for i in c:
    total=total+(board1[i]*board2[i])
print total