Posts

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
Posted on

Ignoring Errors Returned by PHP file_get_contents HTTP Wrapper

PHP logo

I discovered that CodeEval was down briefly for maintenance, which caused my badge (in the sidebar of this blog) to be populated with the error message associated with an HTTP 503 error. Since I didn’t want error messages to be returned by my PHP script, I added one line and changed the line containing the file_get_contents statement, as seen below.

$context = stream_context_create(array(
    'http' => array('ignore_errors' => true),
));
$html = file_get_contents($score_url, false, $context);

Now, if there’s an HTTP error, the badge will be blank, but no error will appear. I was fortunate to find this quick fix on StackOverflow.

Posted on

Fix for “`require’: cannot load such file” Error

Ruby on Rails logo

While working through Chapter 3 of the RailsTutorial for Rails 4.0, I encountered an error when running the first integration test using RSpec.

Upon running the command:

bundle exec rspec spec/requests/static_pages_spec.rb


for the first time, I got the following error:

/Users/davidyoung/.rvm/gems/ruby-2.0.0-p451@railstutorial_rails_4_0/gems/selenium-webdriver-2.0.0/lib/selenium/webdriver/common/zipper.rb:1:in `require': cannot load such file -- zip/zip (LoadError)
	from /Users/davidyoung/.rvm/gems/ruby-2.0.0-p451@railstutorial_rails_4_0/gems/selenium-webdriver-2.0.0/lib/selenium/webdriver/common/zipper.rb:1:in `<top (required)>'
	from /Users/davidyoung/.rvm/gems/ruby-2.0.0-p451@railstutorial_rails_4_0/gems/selenium-webdriver-2.0.0/lib/selenium/webdriver/common.rb:9:in `require'
.
.
.

It appears this is caused by a bug in version 2.0.0 of the ‘selenium-webdriver’ gem. If you change the Gemfile line to use a newer version, this error goes away.

Gemfile:

source 'https://rubygems.org'
ruby '2.0.0'
#ruby-gemset=railstutorial_rails_4_0

gem 'rails', '4.0.0'

group :development, :test do
	gem 'sqlite3', '1.3.7'
	gem 'rspec-rails', '2.13.1'
end

group :test do
	gem 'selenium-webdriver', '~> 2.35.1'
	gem 'capybara', '2.1.0'
end

gem 'sass-rails', '~> 4.0.0'
gem 'uglifier', '2.1.1'
gem 'coffee-rails', '~> 4.0.0'
gem 'jquery-rails', '2.2.1'
gem 'turbolinks', '1.1.1'
gem 'jbuilder', '1.0.2'

group :doc do
  gem 'sdoc', '0.3.20', require: false
end 

group :production do
	gem 'pg', '0.15.1'
	gem 'rails_12factor', '0.0.2'
end

Now when the command is run, I get the proper output:

F

Failures:

  1) Static pages Home page should have the content 'Sample App'
     Failure/Error: expect(page).to have_content('Sample App')
       expected #has_content?("Sample App") to return true, got false
     # ./spec/requests/static_pages_spec.rb:7:in `block (3 levels) in <top (required)>'

Finished in 0.86025 seconds
1 example, 1 failure

Failed examples:

rspec ./spec/requests/static_pages_spec.rb:5 # Static pages Home page should have the content 'Sample App'

Randomized with seed 48261