Category: Ruby / Ruby on Rails

Posted on

Code School will be Having a Black Friday Special!

CodeSchool logo

I have found Code School to be a great resource both for those just learning to code as well as those who are experienced coders, but want to learn a new programming language. It has multiple paths: Ruby (including Ruby on Rails), JavaScript (includes jQuery and CoffeeScript), HTML/CSS, iOS, Git, and an Electives path for miscellaneous technologies such as R and Chrome DevTools.

The normal price for a subscription at Code School is $29 per month, or $290 per year. However, it appears that they intend to run a Black Friday special for yearly subscriptions. The price will be revealed this Friday. If you don’t already have a subscription, or your subscription is about to run out, this could be a good time to sign up!

Unfortunately, Code School is still lacking Python, though you can learn it at Codecademy (which is free).

Posted on

The Key to Solving CodeEval’s Bay Bridges Challenge

CodeEval logo

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)
end

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