Global list keeps changing despite copy

Question

I'm having difficulty understanding why expqueue keeps changing to multiple iterations of state, I've tried everything I have looked up from [:] to deep copy. Can someone explain whats wrong? The code is for a 8 puzzle game, and if I could get a running list going of all the different combinations I'm sure I could complete this myself, and yes, it is homework.

import copy
init = [[2,0,3], [1,5,6],[4,7,8]]
goal = [[1,2,3], [4,5,6],[7,8,0]]
expqueue = []
tempqueue = []
depth = 0

def myappend(lst1, lst2):
    new = list(lst1)
    new2 = list(lst2)
    new.append(new2)
    global expqueue
    expqueue = new

def makeState(state):
for x in range(0,3):
    for i in range(0,3):
        print state[x][i],
    print "\n"


def locate(state):
    for x in range(0,3):
        for y in range(0,3):
            if state[x][y] == 0:
                return [x, y]

def moveU(state):
    location = locate(state)
    x = location[0]
    y = location[1]
    s = x-1
    if x>0:
        swap = state[x][y]
        state[x][y] = state[s][y]
        state[s][y] = swap
        myappend(expqueue, state)

def moveL(state):
    location = locate(state)
    x = location[0]
    y = location[1]
    s = y-1
    if y>0:
        swap = state[x][y]
        state[x][y] = state[x][s]
        state[x][s] = swap
        myappend(expqueue, state)

def moveR(state):
    location = locate(state)
    x = location[0]
    y = location[1]
    s = y+1
    if y<2:
        swap = state[x][y]
        state[x][y] = state[x][s]
        state[x][s] = swap
        myappend(expqueue, state)

def moveD(state):
    location = locate(state)
    x = location[0]
    y = location[1]
    s = x+1
    if x<2:
        swap = state[x][y]
        state[x][y] = state[s][y]
        state[s][y] = swap
        myappend(expqueue, state)

def expand(lst):
    tempqueue = lst[:]
    while tempqueue != []:
        state = tempqueue[0]
        current = state[:]
        moveU(current)
        moveL(current)
        moveR(current)
        moveD(current)
        del tempqueue[0]
    return expqueue

def solve(queue, initial, solution, level):
    length = len(queue)
    for x in range(length):
        if queue[x] == solution:
            return "This works!"
    return solve(expand(queue), initial, solution, level+1)

print solve([init], init, goal, 0)

I've since added deepcopy over the initial slices, and I've noticed the ID's are coming back the same after the copy. Does anyone know why?

Apparently I don't have enough street cred to post a screen shot so here's a link to it: Matching id's after copy

Note that in Python you can swap variables directly: `state[x][y], state[s][y] = state[s][y], state[x][y]`. — Daniel Roseman, Oct 01 '14 at 12:03
Thank you for the tip! Fairly new to python and figuring out how it works has been, well, interesting... — Blake Howard, Oct 01 '14 at 12:59

score 3 · Accepted Answer · answered Oct 01 '14 at 12:03

3

You are altering the nested lists, but only copied the outer list; a list(original) or original[:] call only creates a shallow copy; the new list 'inherits' the references to the contents, and if those contents are mutable then you'll see the changes to those contents in both places.

Create copies of the nested lists:

new = [nested[:] for nested in lst1]

and

tempqueue = [nested[:] for nested in lst]

This creates a shallow copy of each nested list instead.

Or use the copy.deepcopy() function to recursively copy objects.

answered Oct 01 '14 at 12:03

Martijn Pieters

1,048,767
296
4,058
3,343

Thanks, I tried your suggestions, but am still receiving messed up lists in the debugger. As mentioned above, I attempted to deep copy pretty much everything I could to no avail. I'm starting to think I may just need to scrap and go for a different approach. – Blake Howard Oct 01 '14 at 13:02
@BlakeHoward: test functions individually, use `id()` to see memory addresses for each object (if they match, it is not a copy but a shared reference), etc. In other words: debug! You now have more information on how copies work, in any case. – Martijn Pieters Oct 01 '14 at 13:08
Thanks for the tips! Curiously, i checked the id of new, and lst and they are the exact same. I wonder why the copy isn't actually creating a copy....... – Blake Howard Oct 01 '14 at 13:12

score 3 · Answer 2 · edited May 23 '17 at 11:57

tempqueue = lst[:] makes a shallow copy, not a deep copy. That means you get a new container list, but references to the exact same contents. Since the contents are themselves lists, you are getting references to mutable objects. If you mutate those lists in either lst or tempqueue, then the other is also affected.

If you want a deep copy of a list of lists, you could use

tempqueue = [[x for x in item] for item in lst]

or

tempqueue = [list(item) for item in lst]

or

tempqueue = [item[:] for item in lst]

or, for even more deeply nested structures, you could use

tempqueue = copy.deepcopy(lst)

The example here shows the difference between using a shallow versus a deep copy.

I changed tempqueue to copy.deepcopy(lst), same with the new and new2 in myappend(). After that failed I also changed the current to be a deep copy in expand(), also to no avail.... Thank you for the attempt though. — Blake Howard, Oct 01 '14 at 13:09

Global list keeps changing despite copy

2 Answers2