Discussion on KnightL on a Chessboard Challenge

4 years ago+ 5 comments

Python 3 solution.

A couple things to note: - The number of moves funciton is symetteric, so I went ahead and memoized it which will half our run time (don't think this is necessary but a good thing to recognize) - I notice a lot of people are using long if statements to get the adjacent list of positions. I felt a simple filter lambda was cleaner.

memo = [[]]

def adj(a, b, x, y, n):
    return filter(lambda v : v[0] >= 0 
      and v[1] >= 0 
      and v[0] < n 
      and v[1] < n,
      [
        [x + a, y + b],
        [x + a, y - b],
        [x - a, y + b],
        [x - a, y - b],
        [x + b, y + a],
        [x + b, y - a],
        [x - b, y + a],
        [x - b, y - a],
    ])

def move(a, b, n):
    global memo
    # Since move(a, b, n) == move(b, a, n),
    # we take advantage of this symmtery by memoization.
    if memo[a][b] is not None:
        return memo[a][b]
    visited = [[False] * n for _ in range(n)]
    # Queue stores elements as [x, y, depth]
    # Start with top left position
    queue = [[0, 0, 0]]
    while len(queue) > 0:
        x, y, l = queue.pop()
        # At the end, return level of node
        if x == n - 1 and y == n - 1:
            memo[a][b] = l
            memo[b][a] = l
            return l
        neighbors = [
            [x_i, y_i]
            for x_i, y_i in adj(a, b, x, y, n) 
            if visited[y_i][x_i] == False
        ]
        
        for x_i, y_i in neighbors:
            visited[y_i][x_i] = True 
            queue.insert(0, [x_i, y_i, l + 1])
            
    memo[a][b] = -1 
    memo[b][a] = -1 
    return -1 
    

# Complete the knightlOnAChessboard function below.
def knightlOnAChessboard(n):
    global memo
    memo = [[None for _ in range(n + 1)] for _ in range(n + 1)]
    results = []
    for a in range(1, n):
        results.append([])
        for b in range(1, n):
            results[a - 1].append(move(a, b, n))
    return results