Help understanding similarities pset6

Question

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][0] = (c, Operation.DELETED)
            c += 1
        c = 1
        for j in range(len(b)):
            matrix[0][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')

Answer 1

See this: https://stackoverflow.com/questions/30792428/wagner-fischer-algorithm

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

Answer 2

The cost is actually matrix[len(a)][len(b)][0] (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[0][0]. This is equivalent to ""->"", means nothing to do, or tuple (0, None). You could also consider a base case elements of form matrix[i][0]. Those are equivalent to "abc"->"", so they can only be constructed by deletion. Elements of form matrix[0][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).