Python BreathFirstSearch -pathing problem

This is my first post here, I am a python beginner working on a project for school.

My specific problem is a part of the berkeley pacman project1: https://inst.eecs.berkeley.edu/~cs188/sp19/project1.html

On the BFS part I am running into trouble. specifically on the tinyMap while my program is in 2,2 state it transitions to 2,3 normally but 2,1 has an extra north direction.

successorsVisited is a set of coordinate states myQueue is a regular queue problem is the board getSuccessors returns a list of Tuples (state, direction, cost) which i edit into (state, direction, cost, path) before pushing it back into the queue.

please assume I have handled the base case correctly this is the iteration step starting with 5,4 and 4,5 in the queue.

def BFS_Helper(problem,myQueue,successorsVisited):
    while not myQueue.isEmpty():
        node = myQueue.pop()
        state = node[0]
        for x in range(0,len(problem.getSuccessors(state))):
            aTuple = problem.getSuccessors(state)[x]
            if aTuple[0] not in successorsVisited:
                successorsVisited.add(aTuple[0])
                node[3].append(aTuple[1])
                bTuple = (aTuple[0], aTuple[1], aTuple[2],  node[3]) # new bTuple with path = path + action 
                print(bTuple)
                if problem.isGoalState(aTuple[0]):
                    return bTuple[3]
                myQueue.push(bTuple)
    return BFS_Helper(problem, myQueue,successorsVisited)

i print out a bTuple before checking the goal state here is the print out. the north that is bolded is my problem, i cannot figure out how it happened.

((5, 3), 'South', 1, ['South', 'South'])

((3, 5), 'West', 1, ['West', 'West'])

((4, 3), 'West', 1, ['South', 'South', 'West'])

((2, 5), 'West', 1, ['West', 'West', 'West'])

((4, 2), 'South', 1, ['South', 'South', 'West', 'South'])

((1, 5), 'West', 1, ['West', 'West', 'West', 'West'])

((3, 2), 'West', 1, ['South', 'South', 'West', 'South', 'West'])

((1, 4), 'South', 1, ['West', 'West', 'West', 'West', 'South'])

((2, 2), 'West', 1, ['South', 'South', 'West', 'South', 'West', 'West'])

((1, 3), 'South', 1, ['West', 'West', 'West', 'West', 'South', 'South'])

((2, 3), 'North', 1, ['South', 'South', 'West', 'South', 'West', 'West', 'North'])

((2, 1), 'South', 1, ['South', 'South', 'West', 'South', 'West', 'West', 'North', 'South'])

((1, 1), 'West', 1, ['South', 'South', 'West', 'South', 'West', 'West', 'North', 'South', 'West'])

Thank you very much for any assistance.

Solution

The cause of your problem is here:

node[3].append(aTuple[1])

This will become an issue when the loop over the successors has more iterations. In those iterations the same node[3] is used... which still has the appended value in it from a previous iteration, and you add yet another value to it.

Solution: don't mutate node[3]. Instead, create a new list on-the-fly:

bTuple = (aTuple[0], aTuple[1], aTuple[2],  node[3] + [aTuple[1]])