Find the maximum number of bridge connections given the random order.

find_max_num_bridges.py

"""
A B C D
-river-
B C A D


Find the maximum number of bridge connections given the random order.
top = {A : 0,
       B : 1,
       C : 2,
       D : 3}

bottom = {B : 1,
          C : 2,
          A : 0,
          D : 3}
"""

# top : list of cities
# bottom : list of cities


def find_max_num_bridges(top, bottom):
    top_cities = {}
    for i in range(len(top)):
        top_cities[top[i]] = i

    bottom_mapping = {}
    for j in range(len(bottom)):
        city = bottom[j]
        bottom_mapping[city] = top_cities[city]

    max_len = 1
    prev = None
    for city in bottom:
        v = bottom_mapping[city]
        if prev is not None:
            if v > prev:
                max_len += 1
                prev = v  # 1, 2, 3
            else:
                prev = v
                max_len = 1
        else:
            prev = v
    return max_len

print(find_max_num_bridges(["A", "B", "C", "D"], ["B", "C", "A", "D"]))

print(find_max_num_bridges(["A", "B", "C", "D"], ["D", "C", "A", "B"]))

print(find_max_num_bridges(["A", "B", "C", "D"], ["B", "A", "C", "D"]))