0

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

0

Oh, gosh! What a silly mistake!

It was just a matter of changing the elif I put there to a mere if! After all, if one option was meant to be smaller than the other (like 3, 2 and 1, for instance), my original implementation would settle with 2 and leave the 1 there!

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .