I was writing an implementation of Levenshtein distance in Python and I found my code really ugly.Have you any idea how to make it more elegant?import unittestimport enumdef seq_dist(first, second):    Direction = enum.Enum('Direction', 'gap_first gap_second match finish')    def find_dist():        dist_table = [(len(second) + 1) * [0] for i in range(len(first) + 1)]        directions = [(len(second) + 1) * [None] for i in range(len(first) + 1)]        for i in range(len(first) + 1):            for j in range(len(second) + 1):                if (i, j) == (0, 0):                    dist_table[i][j] = 0                    directions[i][j] = Direction.finish                elif i == 0:                    dist_table[i][j] = j                    directions[i][j] = Direction.gap_first                elif j == 0:                    dist_table[i][j] = i                    directions[i][j] = Direction.gap_second                else:                    gap_first = dist_table[i - 1][j] + 1                    gap_second = dist_table[i][j - 1] + 1                    match = dist_table[i - 1][j - 1] + (first[i-1] != second[j-1])                    if gap_first <= min(gap_first, match):                        dist_table[i][j] = gap_first                        directions[i][j] = Direction.gap_second                    elif gap_second <= min(gap_second, match):                        dist_table[i][j] = gap_second                        directions[i][j] = Direction.gap_first                    else:                        dist_table[i][j] = match                        directions[i][j] = Direction.match        return dist_table, directions    def backtrack(directions):        i, j = (len(first), len(second))        seq = []        while directions[i][j] != Direction.finish:            direction = directions[i][j]            if direction == Direction.gap_first:                seq.append((None, second[j-1]))                j -= 1            elif direction == Direction.gap_second:                seq.append((first[i-1], None))                i -= 1            elif direction == Direction.match:                seq.append((first[i-1], second[j-1]))                i -= 1                j -= 1        seq.reverse()        return seq    dist_table, directions = find_dist()    dist = dist_table[-1][-1]    diff = backtrack(directions)    return (dist, diff)class MatchSeqsTest(unittest.TestCase):    def test_seq_dist(self):        self.assertMatchDist(0, '', '')        self.assertMatchDist(2, 'something cool', '')        self.assertMatchDist(0, 'first', 'first')        self.assertMatchDist(1, 'first', 'first second')        self.assertMatchDist(1, 'fourth second', 'first second')        self.assertMatchDist(1, 'first second third', 'second third')    def assertMatchDist(self, dist, first, second):        self.assertMatchDistOneWay(dist, first, second)        self.assertMatchDistOneWay(dist, second, first)    def assertMatchDistOneWay(self, dist, first, second):        actualDist, actualDiff = seq_dist(first.split(), second.split())        self.assertEqual(dist, actualDist)        self.assertEqual(dist, self.alignment_dist(actualDiff))        self.assertEqual(self.extract_first(actualDiff), first.split())    def extract_first(self, diff):        return [f for f, s in diff if f is not None]    def alignment_dist(self, diff):        return sum(1 for f, s in diff if f != s)if __name__ == '__main__':    unittest.main()
Making the Levenshtein distance code cleaner
python;algorithm;python 3.x;unit testing;edit distance