Including backtrace pointers with symbols in a Python output of a DP table for min edit distance algorythm

Viewed 17

I have a working min edit distance program for two words that also iterates and outputs a DP table to the console, however I wish to add a backtrace to the programme that also prints arrow pointer symbols in the DP table to show the backtrace clearly on the output. I cannot figure out how to output these symbols correctly.

import re
import time

time1= time.time() 
def printTable(table, description):

print(f'{description}\n')
current_row = current_col = 0
current_row_col = re.search("^row ([0-9]+) , col ([0-9]+)$",description)
if current_row_col:
    current_row = int(current_row_col.group(1))
    current_col= int(current_row_col.group(2))
row_counter=0
for row in table:
    row_counter+=1
    col_counter=0
    for col in row:
        col_counter+=1
        #print(row_counter , row, current_col, col)
        if (row_counter == current_row) and (col_counter == current_col): 
            formatting = '\033[1m'+'\033[91m' #bold + red
        else: formatting = '\x1b[0m' #reset fomatting
        print(formatting + str(col).rjust(10, ' '), end=' ')  # rjust returns a 10-characters long, right justified version of the string
    print('\n\n')
print('---------------------------------------------------------------------------------------------------------------')                       
    

# A DP-based solution for edit distance problem 
def editDistDP(x,y):

leftarrow = "←"
uparrow = "↑"
diagarrow = ""

dp = [] # Create an empty table to store results of subproblems
# fill in the table with zeros 
for row in range(len(x) + 1):
    dp.append([0]* (len(y) + 1))
# Alternatively, you can use List Comprehension to initiate the DP table in one line of code
# dp = [[0 for column in range(len(y) + 1)] for row in range(len(x) + 1)]

# Fill in the base case (easy) subproblems, i.e. the first row and column of the DP table

# first row: base case subproblems for computing the cost of converting "" to y
for i in range(len(y) + 1):
    # If x is empty then the only option is to insert all the characters of y
    # Minimum number of required operations (cost) is i insertions, where i = len(y)
    dp[0][i] = i

# first column: base case subproblems for computing the cost of converting x to ""
for i in range(len(x) + 1):
    # If y is empty then the only option is to delete all the characters of x
    # Minimum number of required operations (cost) is i deletions, where i = len(x)
    dp[i][0] = i


printTable(dp,"DP table after the base case (easy) subproblems are solved");

# Fill in the rest of the DP table in a BOTTOM-UP manner 
for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):

        horizontal_or_insertion_cost = (dp[i][j-1] + 1)
        vertical_or_deletion_cost= dp[i-1][j] + 1
# Weighted Minimum Edit Distance for sub
        if x[i-1] != y[j-1] and x[i-1].isnumeric: 
          delta = 3 
        elif x[i-1] != y[j-1]:
          delta = 2
        else: 
          delta = 0
        diagonal_or_substitution_cost= dp[i-1][j-1] + delta

        minValue = min(horizontal_or_insertion_cost,vertical_or_deletion_cost,diagonal_or_substitution_cost)
        dp[i][j] = minValue          
        # printTable(dp,f'row {i+1} , col {j+1}') #UNCOMMENT this line to see how the DP table is filled at each step

printTable(dp,"Completed DP table after all the subproblems are solved")
return dp[-1][-1]



str1, str2 = "intention", "execution" 
print(f'edit distance between "{str1}" and "{str2}": {editDistDP(str1, str2)}') 

time2 = time.time() 
execTime = time2-time1
execTime = str(execTime)
print("--- Executed in: " + execTime + " seconds ---") 
0 Answers
Related