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 ---")