Python "int * list" operation: the illusion of safety

Today I solved a problem using dynamic programming: that means that I had to construct, initialize and fill a matrix, according to a recurrence formula.

The problem was, roughly speaking, "compute the minimal number of character substitutions needed to make a 'valid' string out of the input string".

My algorithm and code were sound, but when I executed the code, the answers I got were obviously incorrect. For all inputs, I got 0 as an answer. I knew, from trivial input cases, that the answer wasn't 0 for most of my test cases.

Happily enough, I had the reflex of printing the initial and final matrix. And what I saw was surprising: the initial matrix was wrong!!!

Here's the initialization code that I was using for the dp matrix:

dp = (N+1)*[ 5*[N] ]
dp[0][0] = 0

where N is a strictly positive integer, the length of the input string. From this initialization code, I expected a matrix where all values where equal to the value of N, except for the value at entry [0][0]. Please stop here and make your best guess about what I really got.

Got a guess? Well, the following Python session exhibits the problem:

>>> N = 2
>>> dp = (N+1)*[ 5*[N] ]
>>> dp
[[2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2]]
>>> dp[0][0] = 0 
>>> dp
[[0, 2, 2, 2, 2], [0, 2, 2, 2, 2], [0, 2, 2, 2, 2]]

As you see, there are 0s in the first entry of every row of the matrix!! What happened?

Well, at this point, you got it: the binary operator *, which applies to an integer, say k, on the left, and a list, say L, on the right, creates a new list consisting of the k-fold concatenation of L, and this new list contains references to the same objects pointed-to by the entries of the original list.

As you see, the line

>>> dp[0][0] = 0

above is actually modifying the object pointed-to by dp[0], dp[1] and dp[2], and that explains the strange behavior of my program.

Well, as the protip comes to its end, I'll state some conclusions. I'm really happy to have printed the data early in the debugging process. That shed much light on what was really happening.

Now, in what concerns the operator itself, my conclusion is the following: the 'int * list' operator must only be used when all the elements of the list are immutable, or at least read-only.

By the way, I finally used the line

dp = [ 5*[N] for _ in xrange(N+1) ]
dp[0][0] = 0

for initializing my matrix.