Problem I am experiencing: I have figured out an algorithm for distances to calculate the edit distance between two strings. The costs in the tuples are correct, but the conditions are not properly capturing the operations along the way.

I have tried many different implementations of different conditions, I feel like it should be very simple to capture which operation is the minimum cost and record it along with the cost in the tuple.

I think the issue may be cases where multiple operations have the same cost along the way but if the application.py code provided by the problem works (which I'm sure it does) it should still find the shortest path when in matrix.html.

My code is below, I have tried searching many places but everything I find is concerned with the cost itself.


from enum import Enum

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


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

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

rows = len(a) + 1
columns = len(b) + 1

# List comprehension for 2D matrix
matrix = [[None for _col in range(columns)] for _row in range(rows)]

# Set base case empty string to empty string
matrix[0][0] = (0, None)

# Fill in base case values
for row in range(1, rows):

    # Delete char to match empty str
    matrix[row][0] = (row, Operation.DELETED)

for column in range(1, columns):

    # Insert char to match from empty str
    matrix[0][column] = (column, Operation.INSERTED)

# Complete matrix skipping 0 row/column
for i in range(1, rows):

    for j in range(1, columns):

      if a[i-1] == b[j-1]:
          # Substitution not required chars match
          matrix[i][j] = (matrix[i-1][j-1][0], Operation.SUBSTITUTED)
          # Operations
          insertCost = matrix[i-1][j][0] + 1
          deleteCost = matrix[i][j-1][0] + 1
          subCost = matrix[i-1][j-1][0] + 1

          # Get easiest method
          cost = min(insertCost, subCost, deleteCost)

          if cost == subCost:
                op = Operation.SUBSTITUTED
          elif cost == insertCost:
                op = Operation.INSERTED
          elif cost == deleteCost:
                op = Operation.DELETED

          # Set cell value
          matrix[i][j] = (cost, op)

return matrix


1 Answer 1


I think your insertCost is actually your deleteCost and the other way around.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .