Bug with trying to count the no. of moves it takes to get from point A to point B on a grid. Not working for all values

user_9520056 0
Viewed 44

I'm working on a challenge to count the number of moves it takes to get from point A to point B on a grid which is set out like a chessboard and the moves you can make are that of the Knight so 2 in any direction and 1 perpendicular.

I've gotten most of it worked out but for some reason, my counter is not returning the number of moves between the two points. Below is what I have regarding the counting.

You'll notice I'm using a dict called position and the reason for this is so that I can store an int representing the no of moves that particular position is from the destination.

I thought at the end I should be incrementing the move value after a move is deemed valid but I'm still failing to get the right number.

def solution(src, dest):
# Chessboard made using nested lists. The indexes will act as coordinates.
chessboard = [
    [0,1,2,3,4,5,6,7],
    [8,9,10,11,12,13,14,15],
    [16,17,18,19,20,21,22,23],
    [24,25,26,27,28,29,30,31],
    [32,33,34,35,36,37,38,39],
    [40,41,42,43,44,45,46,47],
    [48,49,50,51,52,53,54,55],
    [56,57,58,59,60,61,62,63]
    ]

# Find index values of src and dest
for row in chessboard:
    if src in row:
        srcX = chessboard.index(row)
        srcY = row.index(src)
    if dest in row:
        destX = chessboard.index(row)
        destY = row.index(dest)
    
# Position dict to store indexes and no of mvoes when using bfs
position = {
    'x': 0,
    'y': 0,
    'moves': 0,
    }

position['x'] = srcX
position['y'] = srcY

# Below represents the knights moves to be applied to the index of position
row = [-2,-2,-1,1,2,2,1,-1]
col = [-1,1,2,2,-1,1,-2,-2]


# We use an if-statement to check for valid moves 
def isValid(x, y):
    return not (x < 0 or y < 0 or x >=8 or y >=8)
    

q = []
q.append(position)

# Record spaces visited already
isVisited = []

while len(q)>0:
    space = q.pop()
    x = space['x']
    y = space['y']
    moves = space['moves']
    
    
    # if the position matches the destination, return no.moves
    # I'm just using print to see the result in the terminal
    if x == destX and y == destY:
        print(moves)
        
   
    if (x,y) not in isVisited:
        isVisited.append((x,y))
    
        
        # Loop over possible moves
        for i in range(len(row)):
            newX = x + row[i]
            newY = y + col[i]

            
            if isValid(newX, newY):
                position['x'] = newX
                position['y'] = newY
                position['moves'] = moves+1
                q.append(position)
breadth-first-search iteration python-3.x python
1 Answers

This is a common Python issue. You create a dictionary called "position" and add it to the queue. Then, any time you have a new move, you MODIFY that same dictionary and add it to the queue again, but that's not creating a NEW dictionary. What you will end up with is a queue that full of references to the exact same dictionary. Every time you change "position", you're changing every dict in the queue. You need to create a new object each time.

This seems to work.

# We use an if-statement to check for valid moves 
def isValid(x, y):
    return (0 <= x <= 7) and (0 <= y <= 7)

def solution(src, dest):
# Chessboard made using nested lists. The indexes will act as coordinates.
    chessboard = [
        [0,1,2,3,4,5,6,7],
        [8,9,10,11,12,13,14,15],
        [16,17,18,19,20,21,22,23],
        [24,25,26,27,28,29,30,31],
        [32,33,34,35,36,37,38,39],
        [40,41,42,43,44,45,46,47],
        [48,49,50,51,52,53,54,55],
        [56,57,58,59,60,61,62,63]
        ]

# Find index values of src and dest

    srcY = src % 8
    srcX = src // 8
    destY = dest % 8
    destX = dest // 8
        
# Position dict to store indexes and no of mvoes when using bfs
    position = {
        'x': srcX,
        'y': srcY,
        'moves': 0,
        }

# Below represents the knights moves to be applied to the index of position
    row = [ -2, -2, -1, -1,  1,  1,  2,  2]
    col = [ -1,  1,  2, -2, -2,  2, -1,  1]

    q = []
    q.append(position)

# Record spaces visited already
    isVisited = []

    while q:
        space = q.pop()
        print( "Checking", space )
        x = space['x']
        y = space['y']
        moves = space['moves']
        
        
        # if the position matches the destination, return no.moves
        # I'm just using print to see the result in the terminal
        if x == destX and y == destY:
            print(f"{moves}!!!")
            return moves
       
        if (x,y) not in isVisited:
            isVisited.append((x,y))
        
            # Loop over possible moves
            for dx,dy in zip(row,col):
                newX = x + dx
                newY = y + dy
                
                if isValid(newX, newY):
                    position = {
                        'x': newX,
                        'y': newY,
                        'moves': moves+1
                    }
                    q.append(position)

print( solution( 3, 61 ) )
user_18833160
Related