Python3 running the same function with the same input many times but producing different outputs every time

I am currently trying to solve a simple version of checkers with python. Specifically, I am trying to solve the problem “checkers” from USACO 2008 December Bronze contest. (Problem Link)

My idea is to run a recursive dfs function on the location of each of the kings. However, I have encountered some issues with my dfs function. When I run my dfs function multiple times, the function produces different outputs, even with the same parameters. Specifically, it only produces the right outputs in the first time. I don’t know what is happening, any help will be appreciated, thank you! (I am using Python 3.7)

Here is my dfs function:

def dfs(x, y, n, graph, path, count, visited):
    if str([x+1, y+1]) not in visited:
        visited.add(str([x+1, y+1]))
        if count == 0:
            path += [[x+1, y+1]]
            return path
        if x < 0 or y < 0 or x > n or y > n:
            return path
        path += [[x+1, y+1]]
        try:
            if graph[x+1][y+1] == "o":
                graph[x+1][y+1] = "+"
                return dfs(x+2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x+1][y-1] == "o":
                graph[x+1][y-1] = "+"
                return dfs(x+2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y+1] == "o":
                graph[x-1][y+1] = "+"
                return dfs(x-2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y-1] == "o":
                graph[x-1][y-1] = "+"
                return dfs(x-2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        return path

Here is how I called my dfs function:

print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))

Here is the output I am getting:

Here is my full code:

n = int(input())
grid = []
for i in range(n):
    grid.append(list(input().rstrip()))
def dfs(x, y, n, graph, path, count, visited):
    if str([x+1, y+1]) not in visited:
        visited.add(str([x+1, y+1]))
        if count == 0:
            path += [[x+1, y+1]]
            return path
        if x < 0 or y < 0 or x > n or y > n:
            return path
        path += [[x+1, y+1]]
        try:
            if graph[x+1][y+1] == "o":
                graph[x+1][y+1] = "+"
                return dfs(x+2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x+1][y-1] == "o":
                graph[x+1][y-1] = "+"
                return dfs(x+2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y+1] == "o":
                graph[x-1][y+1] = "+"
                return dfs(x-2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y-1] == "o":
                graph[x-1][y-1] = "+"
                return dfs(x-2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        return path

count = 0
Ks = []
for x in range(n):
    for y in range(n):
        if grid[x][y] == "K":
            Ks.append([x, y])
        if grid[x][y] == "o":
            count += 1
print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))

Answer

The .copy() list method will only work on one “layer” of the list. Since grid is a list of lists, the original will still be changed if you change the copy.

For example, try in the Python console

>>> a = [[1,2,3], [4,5,6], [7,8,9]]
>>> b = a.copy()
>>> b
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> b[0][0] = 5
>>> a
[[5, 2, 3], [4, 5, 6], [7, 8, 9]]

You see that a has changed, despite b being set to a.copy(). You will need to make some form of a “double” copy.

Alternatively, use the deepcopy function from copy module:

>>> from copy import deepcopy
>>> a = [[1,2,3], [4,5,6], [7,8,9]]
>>> b = deepcopy(a)
>>> b[0][0] = 5
>>> a
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Advertisement

Answer