One more doubt has arised, as I get closer to the end of this course. Doing the less complicated version of Similarities was trivial to me; however, I am going through some issues with the outcomes of my helpers.py for the more comfortable version of this problem.
My implementation is as follows:
helpers.py
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"""
# DOING
# create table of distances, based on the lengths of the strings provided
editDistances = [[tuple((0,None)) for j in range(len(b) + 1)] for i in range(len(a) + 1)]
emptyTuple = tuple((0,None))
# stipulate first values based on conversions from empty strings to a and b
for column in range(1, len(editDistances[0])):
editDistances[0][column] = (column, Operation.INSERTED)
for row in range(1, len(editDistances)):
editDistances[row][0] = (row, Operation.INSERTED)
# iterate through each element, search for empty tuples and replace them with previous answers
for row in range(1, len(editDistances)):
for column in range(1, len(editDistances[0])):
# create set of options, based on the three possible actions and conditioned to the substitution alternatives
if a[row - 1] == b[column - 1]:
options = [(editDistances[row-1][column][0] + 1, Operation.DELETED), (editDistances[row][column - 1][0] + 1, Operation.INSERTED), (editDistances[row - 1][column - 1][0], Operation.SUBSTITUTED)]
else:
options = [(editDistances[row-1][column][0] + 1, Operation.DELETED), (editDistances[row][column - 1][0] + 1, Operation.INSERTED), (editDistances[row - 1][column - 1][0] + 1, Operation.SUBSTITUTED)]
# find the optimal solution
optimalOption = options[0]
if options[1][0] < optimalOption[0]:
optimalOption = options[1]
elif options[2][0] < optimalOption[0]:
optimalOption = options[2]
# insert the optimal solution to the distances table
editDistances[row][column] = optimalOption
# return finished table
return editDistances
check50 returns the following result when checking my implementation:
check50
~/workspace/pset6/similarities/more/ $ check50 cs50/2018/x/similarities/more
Connecting.....
Authenticating......
Preparing............
Uploading...........
Checking.......
:) helpers.py exists
:) helpers.py compiles
:) takes 0 operation to convert "" to ""
:) takes 3 operation to convert "dog" to ""
:) takes 4 operation to convert "" to "dog"
:) takes 1 operation to convert "a" to "b"
:( takes 1 operation to convert "cat" to "coat"
Expected edit distance of 1, not 3
:) takes 1 operation to convert "frog" to "fog"
:) takes 1 operation to convert "year" to "pear"
:) takes 0 operations to convert "today" to "today"
:( takes 5 operations to convert "today" to "yesterday"
Expected edit distance of 5, not 9
:) takes 6 operations to convert "tomorrow" to "today"
:) takes 3 operations to convert "today" to "ToDaY"
See https://cs50.me/checks/7a76bad31ed34bfc6358951f8313ad567096e5a1 for more detail.
~/workspace/pset6/similarities/more/ $
It is my understanding that my code is ignoring the insertion possibilities and going straight away with the replacement. However, I am unable to see which changes could be made in order to mitigate this issue. Can someone share some thoughts? It would be much appreciated.
--
I'd like to seize this opportunity and externalize how fruitful this course has been to me. Even throughout the Python and HTML parts, which elaborate on languages that I already know and have experience on, I have been constantly challenged. This is definitely how every Computer Science bachelor degree should begin!
--
Thank you in advance for the assistance provided.
~imatheussm