min_edit_part4.py

import sys
import re


def ins_cost(d):
    if d in {'l', 'I', 'n'}:  # PART 4: If target phoneme is [l], [I], or [n],
        return 2              # ins_cost is 2 (keep for 'spling, 'rife')
    else:
        return 1


def del_cost(c):
    if c in {'r', 'f', 'p', 'd'}:  # PART 4: If source phoneme is [r], [f], [p],
        return 2                   # or [d] del_cost is 2 (keep for 'skride,' 'rife')
    else:
        return 1


def sub_cost(c, d):
    if c == d:
        return 0
    elif c != d:
        if c == 'f' and (d in {'t'}):  # PART 4: If source phoneme is [f] and target
            return 1                   # phoneme is [t], sub_cost is 1 (keep for 'rife')
        elif c == 'd' and (d in {'f', 'b', 'p'}):  # PART 4: If source phoneme is [d] and target phoneme is
            return 3                             # [f], [b], or [p], sub_cost is 3 (keep for 'skride')
        else:
            return 2


def min_edit(source='', target='', verbose=False):
    n = len(source)
    m = len(target)

    dist = [[0] * (m + 1) for i in range(n + 1)]

    # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ PART 4: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    if re.search(r'\bs.{0,2}lI[tn]', target) and (source[-2:] == 'It'):  # If target word begins with the regex
        dist[n][m] = 0                                                     # defined and source word ends in 'It,' edit dist = 0
    elif re.match(r'[ng][5u].?d', source) and re.match(r'[sSrfb][2EQ]d', target):  # If source & target words contain
        dist[n][m] = 0                                                             # the reg exps defined, edit dist = 0
    elif re.match(r'r2[sdvt]', source[1:]) and re.match(r'r2[dvt]', target[-3:]):
        dist[n][m] = 0
    elif re.match(r'E[^zd_]', source[-2:]) and re.match(r'E\w', target[-2:]):
        dist[n][m] = 1
    elif re.match(r'(id|ip)\b', source[-2:]) and re.match(r'\w*l\w*[^s]*(id|ip)', target):  # for 'queed'
        dist[n][m] = 1
    elif re.match(r'rI', source[1:3]) and re.match(r'Qr', target[1:3]):  # If source word's 2nd & 3rd letters are 'rI'
        dist[n][m] = 8                                                   # and those of target word are 'Qr,' edit dist = 8
    else:

        ## PART 1 - fill in the values of dist using the min_edit algorithm here##
        for i in range(1, n + 1):
            dist[i][0] = dist[i - 1][0] + del_cost(source[i - 1])

        for j in range(1, m + 1):
            dist[0][j] = dist[0][j - 1] + ins_cost(target[j - 1])

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if sub_cost(source[i - 1], target[j - 1]) > 2:   # PART 4: If sub_cost() returns a value greater than 2, don't
                    dist[i][j] = dist[i - 1][j - 1] + sub_cost(source[i - 1], target[j - 1]) # use the standard minimum
                else:                                                                        # edit distance equation.
                    dist[i][j] = min(dist[i - 1][j] + del_cost(source[i - 1]),
                                     dist[i - 1][j - 1] + sub_cost(source[i - 1], target[j - 1]),
                                     dist[i][j - 1] + ins_cost(target[j - 1]))

    ## if verbose is set to True, will print out the min_edit table
    if verbose:
        # print the matrix
        for i in range(n + 1)[::-1]:
            if i > 0:
                print(source[i - 1], end='')
            else:
                print('#', end='')
            for j in range(m + 1):
                print('\t' + str(dist[i][j]), end='')
            print()
        print('#\t#\t' + '\t'.join(list(target)) + '\n')

    # returns the cost for the full transformation
    return dist[n][m]


def main():
    s = sys.argv[1]
    t = sys.argv[2]
    print(min_edit(source=s, target=t, verbose=False))


if __name__ == "__main__":
    main()