Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python: Fun problem. Solving Program is Bugged. Why?

  1. Jul 31, 2013 #1
    I hope I'm in the right section.
    This part is not important but this is thought behind the program.
    If you have n-mathematicians and each has a secret number. How many phone calls have to be made for all mathematicians to know all numbers? In this brute force approach I, hypothesize that you need m calls and and try all combinations possible. When it works it'll print 1, if not it prints 0.
    D represents what numbers each mathematician knows.
    X represents the combination of phone calls chosen.

    The bug is this:
    D is a list of lists. X is a list.
    The function at "def F(D,X):", makes A=D, makes some additions on A (eg: A+=A[j]), and then turns A into a list of sets. [set()...]
    The loop at bottom repeats this process for all possible X. But somehow D is changed and turns into a list of sets, and since I can't add sets it stops! But why did D become a list of sets? I never tell D to change in the loop.

    Code (Text):
    m=3
    n=3

    X=[]
    Z=[]
    D=[]
    for i in range(0,2*m):
        X.append(0)
        Z.append(n-1)  
    for i in range(0,n):
        D.append([i])
    print 'X,Z,D=',X,Z,D

    def F(D,X):
        A=D
        print 'D=',D                            #Here for debugging purposes:
        print 'A=',A                            #Here for debugging purposes:
        for i in range(0,m):
            [COLOR="Red"]A[X[2*i]]+=[X[2*i+1]][/COLOR]
            [COLOR="Red"]A[X[2*i+1]]=A[X[2*i]][/COLOR]
        for i in range(0,n):
            A[i]=set(A[i])
        return A

    def T(A):
        s=0
        for i in range(0,n-1):
            if A[i]==A[i+1]:
                s+=1
        if s==n-1:
            return 1
        else:
            return 0

    i=2*m-1
    while X!=Z:
        if X[i]!=n-1:
            if i==2*m-1:
                print [COLOR="Red"]T(F(D,X))[/COLOR]
            X[i]+=1
            i=2*m-1
        else:
            if i==2*m-1:
                print T(F(D,X))
            X[i]=0
            i-=1
    Output:
    Code (Text):
    X,Z,D= [0, 0, 0, 0, 0, 0] [2, 2, 2, 2, 2, 2] [[0], [1], [2]]
    D= [[0], [1], [2]]
    A= [[0], [1], [2]]
    0
    D= [set([0]), set([1]), set([2])]
    A= [set([0]), set([1]), set([2])]
    Traceback (most recent call last):
      File "blahblah.py", line 40, in <module>
        print T(F(D,Z))
      File "blahblah.py", line 19, in F
        [COLOR="Red"]A[Z[2*i]]+=[Z[2*i+1]][/COLOR]
    [COLOR="Red"]TypeError: unsupported operand type(s) for +=: 'set' and 'list'[/COLOR]
    Press any key to continue . . .
     
  2. jcsd
  3. Jul 31, 2013 #2
    This is a common stumbling block. You need to be very clear about the difference between mutable and immutable objects in Python. The problem is, A = D leaves A not as a copy of D, but as a reference to the actual D object. They're now just two ways of referencing the same data.

    You'll need to create a new list from the other. Here's a way to do it:

    A = list(D)

    I strongly suggest you find more materials on how mutable and immutable objects, and references, work in Python. That'll help prevent some serious pain later, trust me. :)
     
  4. Jul 31, 2013 #3
    I tried what you said and changed it to:
    Code (Text):
    def F(D,X):
        A=list(D)
        print 'D=',D
        for i in range(0,m):
    but the output is:

    Code (Text):
    X,Z,D= [0, 0, 0, 0, 0, 0] [2, 2, 2, 2, 2, 2] [[0], [1], [2]]
    D= [[0], [1], [2]]
    0
    D= [[0, 0, 0, 0], [1], [2]]
    0
    D= [[0, 0, 0, 0, 0, 0, 1], [1], [2]]
    0
    D= [[0, 0, 0, 0, 0, 0, 1, 0, 0, 2], [1], [2]]
    0
    ie D is still changing. ie A is still a "reference to D".
    I will however read about these "mutable and immutable objects and references". I learned python through copying and testing so sometimes I end up being ignorant about these things. Thanks a lot for giving me a lead on the problem.

    Edit: BOTH the codes are INCOMPLETE. I don't need to post it all. I posted what matters.
     
    Last edited: Jul 31, 2013
  5. Jul 31, 2013 #4
    Ah, I haven't had time to go through your code in great detail, but remember that the method I gave you makes a "shallow copy" of the list, and any mutable objects in that list will still be the original references from the original list. That is, a list of lists, copied in this way, will be a new list containing the lists that were contained in the original one.

    By the way, another method of making a shallow copy, for future reference, is A = D[:].

    Anyways, try a deep copy using the copy module, which will make full copy of everything:

    Code (Text):

    import copy

    A = copy.deepcopy(D)
     
    I'll check back in tomorrow in case you're still stuck. Good luck, and you're welcome! :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Python: Fun problem. Solving Program is Bugged. Why?
  1. How to solve this bug? (Replies: 14)

  2. Programming in Python (Replies: 22)

  3. Python problem (Replies: 3)

Loading...