≡ Menu
Deep in the Code

The Key to Solving CodeEval’s Bay Bridges Challenge

The Bay Bridges Challenge is one of the more difficult challenges on CodeEval (or at least it was for me!), primarily due to the fact that you’re not just looking for any set of bridges that can be built without intersecting, but that you’re looking for the largest possible set of bridges that do not intersect.

Not only do you have to have an algorithm that works for determining if two bridges (which could be thought of as line segments) intersect, but also one that will return the highest number of non-intersecting bridges.

The easy part (which I thought would have been the more difficult one) was how to get the optimal number of bridges. Basically, once you determine which bridges intersect each other and how many intersections there are, you eliminate the ones with the highest number of intersections first, working your way through the set of bridges until all the ones remaining do not intersect.

The part that I had trouble with was determining whether or not they intersected at all. The algorithm I started with was based on simple algebra. First, given the latitudes and longitudes of the endpoints of the bridges, I was able to determine the slopes and intercepts of the bridges. Then, by solving for the intersection point and determining that it fell within the “box” that could by formed by the endpoints, I would declare that the bridges did, in fact, intersect.

This worked fine for the test case given in the problem which only had six bridges, but for larger sets of numbers it did not work – probably due to a flaw somewhere in my equation that allowed for some tolerance to error.

After doing some more research, I discovered an algorithm for determining the intersection of line segments, and decided to implement that. It worked the first time, 100%! The code in Ruby for implementing this algorithm for line segments AB and CD could look something like this:

def ccw(A,B,C)
    (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)

def intersect(A,B,C,D)
    ccw(A,C,D) != ccw(B,C,D) && ccw(A,B,C) != ccw(A,B,D)