pset6 similarities How do I fill the rest of cells in edit distance algorithm?

Question

I have the base cases but I don't know how to access them and compute to choose the better operation and save a tuple in the cells

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([])

# 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)+1):
    for j in range(len(b)+1):




#converting to tuple
for i in range(len(a)+1):
    for j in range(len(b)+1):
        matrix[i][j] = tuple(matrix[i][j])

print(matrix)

distances('cat','ate')

Answer 1

I hope you got your indentation right, so the loops are in the function, and not as it appears here.

You forgot that matrix[0][0] should be (0, None), that for the algorithm constructing the path of changes is the stop signal. Oh, and that's a tuple, not a list like [0, None]. Tuples are immutable.

You could have had your rows in an easier way, like matrix.append([None] * (len(b) + 1)), or use a list comprehension to create the matrix in one line.

Any cell with both indices other than 0 can be reached from three other cells. The one up (Operation.DELETED), the one to the left (Operation.INSERTED), and the one up and left (Operation.SUBSTITUTED). Iterate the matrix in an order that ensures you have already calculated all three (which is trivial if you just nest two loops and go in increasing index), and calculate the associated costs for all three, and pick the tuple with the lowest total cost. Note that if you substitute same letters, the additional cost is zero.