Building Bridges

buildingbridges.py

'''Building Bridges

Building Bridges. Consider a 2-D map with a horizontal river passing through
its center. There are n cities on the southern bank with x-coordinates a(1) ...
a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You
want to connect as many north-south pairs of cities as possible with bridges
such that no two bridges cross. When connecting cities, you can only connect
city i on the northern bank to city i on the southern bank.

http://people.csail.mit.edu/bdean/6.046/dp/

Note: you need the LongestIncSeq from https://gist.github.com/2723571 to run
this script.
'''

from ..LongestIncSeq.longest_inc_seq import LongestIncSeq
class BuildingBridges:
    def __init__(self, A, B):
        self.A = A
        self.B = B
        self.n = len(A)
        self.m = sorted(range(self.n), key=lambda i:self.A[i])
        self.A2 = [self.A[i] for i in self.m]
        self.B2 = [self.B[i] for i in self.m]

    def solve(self):
        res = LongestIncSeq(self.B2).solve()
        # (numOfBridges, original indecs of cities)
        return (res[0], [self.m[i] for i in res[1]])

def test_0():
    print BuildingBridges([1,2,3],[1,2,3]).solve()

def test_simple():
    A = [1]
    B = [1]
    assert BuildingBridges(A, B).solve() == (1,[0])

def test_normal():
    A = [3,1,5,6]
    B = [7,8,2,5]
    assert BuildingBridges(A,B).solve() == (2, [2,3])