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

1. Jul 31, 2013

### Swimmingly!

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. Jul 31, 2013

### Grep

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. :)

3. Jul 31, 2013

### Swimmingly!

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
4. Jul 31, 2013

### Grep

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! :)