# Similarities (More) sometimes fails but works in most cases

For some reason, for some combinations of strings, I receive an IndexError on the compilation of `Operations` in `application.py`. However, for most cases, the table renders properly, and in every case, running `./score` on the same strings runs perfectly.

I have tried strings of the same length, and these almost always work. I have also tried strings of differing lengths. It seems that in most cases this works, however, I tried the combination of converting `grunt` into `runt`, or `rainy` and `grain`, and vice-versa. These combinations and others like them, where there is significant overlap causes the following error:

``````File "/home/ubuntu/workspace/pset6/similarities/application.py", line 68, in score
s = (prev[:i], s2[i], prev[i:])
IndexError: string index out of range
``````

I am stumped here.

helpers.py

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

x = len(a) + 1
y = len(b) + 1

# helper to return the value of the first element in a tuple
def cost(cell):
return cell[0]

# Set up 2D list
matrix = []
for m in range(x):
column = []
for n in range(y):
column.append((0,))
matrix.append(column)

for i in range(x):
for j in range(y):
# add values for base cases
if i == 0 and j == 0:
matrix[0][0] = 0, None
elif i == 0 and j != 0:
matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.DELETED
elif j == 0 and i != 0:
matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.INSERTED
else:
# fill in other entries
possibilities = [
(1 + cost(matrix[i - 1][j]), Operation.DELETED),
(1 + cost(matrix[i][j - 1]), Operation.INSERTED),
# account for difference in length of array and length of string
(cost(matrix[i - 1][j - 1]) if a[i-1] == b[j-1] else (1 + cost(matrix[i - 1][j - 1])), Operation.SUBSTITUTED) ]

matrix[i][j] = min(possibilities, key=cost)
return matrix
``````

I would appreciate any help in pointing me in the right direction. Am I calculating something improperly??

You seem to confuse `Operation.DELETED` and `Operation.INSERTED`.

`Operation.DELETED` is used when you advance in the source string `a` (so you change `i`) without advancing in target string `b`, i.e. the source character is deleted.

`Operation.INSERTED` is used when you don't advance in `a`, but only in `b`.

`Operation.SUBSTITUTED` is used when you advance in both at the same time.

Calculations look correct otherwise, but haven't tested.

• Thanks. I have put the solution to the problem in a separate answer to be more clear.
– wlh
Commented May 22, 2018 at 14:41

Based off @Blauelf's earlier response, the following change was necessary. When I was setting up the state of the matrix for converting each string to an empty string, I had inverted the operations.

• `matrix[0][j - 1]` represents the cost of insertion along `string2` since each inner array is of length `string2 + 1`
• `matrix[i - 1][0]` represents the cost of deletion along `string1` since the length of the outer array is of length `string1 + 1`

original

``````elif i == 0 and j != 0:
matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.DELETED
elif j == 0 and i != 0:
matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.INSERTED
``````

correct

``````elif i == 0 and j != 0:
matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.INSERTED
elif j == 0 and i != 0:
matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.DELETED
``````