# Help understanding similarities pset6

I still don't get it yet how the 2D list/array works to figure out the cost between the strings (Is the tuple in matrix[len(a)][len(b)] right ?

I would like some explanation please kk

I have something going on already. I filled the base cases but don't know how to access the tuples already filled to compute all other cells the code:

``````    from enum import Enum

class Operation(Enum):
"""Operations"""

DELETED = 1
INSERTED = 2
SUBSTITUTED = 3

def __str__(self):
return str(self.name.lower())

def distances(a, b):
"""Calculate edit distance from a to b"""

# generating 2d list
matrix = []
for i in range(len(a)+1): #string a and rows
matrix.append([])
for j in range(len(b)+1): #string b and columns
matrix[i].append(0)

# base cases
c = 1
for i in range(len(a)):
matrix[i+1] = (c, Operation.DELETED)
c += 1
c = 1
for j in range(len(b)):
matrix[j+1] = (c, Operation.INSERTED)
c += 1

#filling in
for i in range(len(a)):
for j in range(len(b)):
matrix[i+1][j+1] = ('x','y')

print(matrix)

distances('cat','ate')
``````

It was the only way I was able to understand the algorithm. Then, once you know what's going on, check this: https://www.youtube.com/watch?v=b6AGUjqIPsA

• up, my code. I think that my code needs to access the first element in the base cases tuples in order to compute the other cells. I dont get this yet May 1, 2018 at 23:08
• First, you have to fill the matrix with the base cases. Your first column and your first row will have the values 0,1,2,3 and so on. Once you have those values, then you can calculate the element (1, 1) of the matrix. Why? Because now you have the values (0,0), (0,1) and (1,0), so you can apply the algorithm (find the minimum of those three value and all that) in order to calculate (1,1). Now that you have the value (1,1), you'll be able to calculate (1,2). Once you have (1,2), calculate (1,3), and so on. This way, you'll be able to fill the entire matrix. May 2, 2018 at 4:20
• I get this but that's the problem. Each element is a tuple and I still don't know how to access the first element in the tuple that lives inside the 2d list. I need to iterate over these values in order to fill the cells. May 2, 2018 at 23:39
• Oh, okay... Maybe the answer is useful to someone else, ha. If I get you right this time, you can access the first element of a tuple through the index 0 (`tuple`). So, you'll have something like this in your code: `matrix[i][j]` May 3, 2018 at 19:06

The cost is actually `matrix[len(a)][len(b)]` (as `matrix[len(a)][len(b)]` is a tuple like `(4, Operation.INSERTED)`. But you are meant to return the matrix (a list of lists of tuples), and the calling code will figure out.

edit, to answer questions not clear from the actual question but comments:

I assume you watched and understood all the videos on dynamic programming?

`matrix[i][j]` is equivalent to transforming `a[:i]` into `b[:j]`.

The base case is `matrix`. This is equivalent to ""->"", means nothing to do, or tuple `(0, None)`. You could also consider a base case elements of form `matrix[i]`. Those are equivalent to "abc"->"", so they can only be constructed by deletion. Elements of form `matrix[j]` can be constructed only by insertion.

All other elements can be constructed with any of the three operations, pick the one with the smallest associated total cost. Don't forget that a substitution of equal characters has no cost (as you don't change anything).

• What I don't get it is how to fill the cells, how to choose the operation and the number of them Apr 29, 2018 at 17:49
• The base cases (first row and column) and the rest of the matrix Apr 29, 2018 at 18:10