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
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"""
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"""
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, None) # Fill in base case values for row in range(1, rows): # Delete char to match empty str matrix[row] = (row, Operation.DELETED) for column in range(1, columns): # Insert char to match from empty str matrix[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], Operation.SUBSTITUTED) else: # Operations insertCost = matrix[i-1][j] + 1 deleteCost = matrix[i][j-1] + 1 subCost = matrix[i-1][j-1] + 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