c1.py

__author__ = 'alex'


def hamming(l1, l2):
    distance = 0
    for i in range(len(l1)):
        if l1[i] != l2[i]:
            distance += 1
    return distance


def manhattan(l1, l2):
    distance = 0
    for i in range(len(l1)):
        distance += abs(l1[i] - l2[i])
    return distance


def levenshtein(l1, l2):
    l1.insert(0, 0)
    l2.insert(0, 0)
    matrix = []
    for i in range(len(l2)):
        matrix.append([0] * len(l1))
    for i in range(1, len(l1)):
        matrix[0][i] = i
    for i in range(1, len(l2)):
        matrix[i][0] = i
    for i in range(1, len(l2)):
        for j in range(1, len(l1)):
            cost = 0 if l2[i] == l1[j] else 1
            matrix[i][j] = min(matrix[i - 1][j] + 1,
                               matrix[i][j - 1] + 1,
                               matrix[i - 1][j - 1] + cost)
    return matrix[len(l2) - 1][len(l1) - 1]


class Node:
    def __init__(self, info, left=None, right=None):
        self.info = info
        self.left = left
        self.right = right


def bfs(root):
    q = [root]
    sol = []
    while q:
        node = q.pop(0)
        sol.append(node.info)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return sol


def dfs(root):
    stack = [root]
    sol = []
    while stack:
        node = stack.pop()
        sol.append(node.info)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return sol


assert (hamming([1, 2, 3, 4], [5, 2, 7, 6]) == 3)
assert (hamming([5, 2, 3, 4], [5, 2, 6, 7]) == 2)
assert (hamming([1, 2, 3, 4], [1, 2, 3, 4]) == 0)
assert (hamming([5, 2, 3, 4], [5, 2, 6, 4]) == 1)
assert (hamming([5, 2, 3, 4], [1, 3, 4, 5]) == 4)

assert (manhattan([1, 2, 3, 4], [5, 2, 7, 6]) == 10)
assert (manhattan([1, 2, 3, 4], [5, 2, 7, 7]) == 11)
assert (manhattan([1, 2, 3, 4], [1, 2, 3, 4]) == 0)
assert (manhattan([1, 2, 3, 4], [2, 4, 6, 8]) == 10)
assert (manhattan([1, 2, 3, 4], [10, 10, 10, 10]) == 30)

assert (levenshtein([1, 2, 3, 4], [5, 2, 4]) == 2)
assert (levenshtein([1, 2, 3, 4], [9, 2, 4]) == 2)
assert (levenshtein([1, 2, 3, 4], [1, 2, 3, 4]) == 0)
assert (levenshtein([1, 2, 3, 4], []) == 4)
assert (levenshtein([1, 2, 3, 4], [1, 2, 3]) == 1)

tree = Node(6, Node(4, Node(3), Node(5)), Node(7))
assert (bfs(tree) == [6, 4, 7, 3, 5])
assert (dfs(tree) == [6, 4, 3, 5, 7])

tree = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
assert (bfs(tree) == [1, 2, 3, 4, 5, 6, 7])
assert (dfs(tree) == [1, 2, 4, 7, 3, 5, 6])

tree = Node(2, Node(3, Node(5)), Node(4, Node(6)))
assert (bfs(tree) == [2, 3, 4, 5, 6])
assert (dfs(tree) == [2, 3, 5, 4, 6])

tree = Node(7, Node(6, Node(5), Node(4)), Node(3, Node(2)))
assert (bfs(tree) == [7, 6, 3, 5, 4, 2])
assert (dfs(tree) == [7, 6, 5, 4, 3, 2])

tree = Node(8, Node(5, Node(6)), Node(7, Node(3), Node(2)))
assert (bfs(tree) == [8, 5, 7, 6, 3, 2])
assert (dfs(tree) == [8, 5, 6, 7, 3, 2])