≡ Menu

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

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

Ignoring Errors Returned by PHP file_get_contents HTTP Wrapper

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.

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

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

Michael Hartl’s Ruby on Rails 4.0 Tutorial

Ruby on Rails, even eight years after its first release, is still recognized as one of the best frameworks for Web applications for many reasons, not the least of which are its cost (it’s free) and its scalability (sites as big as Twitter have used it).

Rails 4.0 was released last year, and soon after, Michael Hartl updated his famous Rails Tutorial.

For those wanting to learn RoR, the Rails Tutorial is (in my opinion) the best way to do it.

I’ve just begun working through the latest release of the tutorial, and have so far been pleased with the small number of typos and various errata that are common in technical instruction manuals.

One error I encountered with the default gemfile configuration file provided in the Rails Tutorial had to do with the versions of sass-rails and coffee-rails. The Tutorial suggests that you use (exactly) version ’4.0.0′ for both of these gems, but I got an error like this:

Bundler could not find compatible versions for gem "railties":
  In Gemfile:
    rails (= 4.0.0) ruby depends on
      railties (= 4.0.0) ruby

    sass-rails (= 4.0.0) ruby depends on
      railties (4.1.0.rc1)

I set both of these gems to ‘~> 4.0.0′, and both bundle update and bundle install worked fine. My gemfile is below:

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

gem 'rails', '4.0.0'

group :development do
	gem 'sqlite3', '1.3.7'
end

group :production do
	gem 'pg', '0.15.1'
	gem 'rails_12factor', '0.0.2'
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

Scraping a DIV Element from a Web Page with PHP

I recently read an article about CodeEval, a free gamified website for ranking developers, and bringing employers and developers together. Essentially, a developer can sign up, complete coding challenges, and earn badges and a “Hacker Ranking” that will compare his or her skills to others who have signed up on the site. Also, completing some challenges will allow the developer to unlock the ability to apply for jobs with various tech startups through the site.

CodeEval logo

After completing some of the challenges I decided to see if, like Kred and some other social ranking sites, I could get a widget to put on my blog that would show my “Hacker Rank”. Unlike Kred, CodeEval apparently does not have this functionality as yet. So I decided to make my own.

The ranking information is shown in a div element on the user’s public profile, assuming that the user allows the profile to be shown.

Using the PHP code below, I was able to scrape the information from CodeEval’s site. Next, in a Text widget on WordPress, I create an empty table and used jQuery to populate the empty table with the div I scraped from CodeEval along with CSS code that I included in my PHP file to give the badge a similar look and feel to what is on the CodeEval site. Ultimately, I could create a WordPress plugin for this, so that it could be done without having to create the codeeval.php file on the site, but I haven’t done that yet.

This code could be used to scrape from any site, as long as the element has a unique class name and PHP has file_get_contents enabled.

codeeval.php:

<?php
$previous_value = libxml_use_internal_errors(TRUE);
$codeeval = $_GET['codeeval'];
$score_url = 'https://www.codeeval.com/public/' . $codeeval . '/';
$html = file_get_contents($score_url);
$classname = 'wrapper-rank';
$dom = new DOMDocument;
$dom->loadHTML($html);
$xpath = new DOMXPath($dom);
$results = $xpath->query("//*[@class='" . $classname . "']");

/* this function preserves the inner content of the scraped element. 
** http://stackoverflow.com/questions/5349310/how-to-scrape-web-page-data-without-losing-tags
** So be sure to go and give that post an uptick too:)
**/
function innerHTML(DOMNode $node)
{
  $doc = new DOMDocument();
  foreach ($node->childNodes as $child) {
    $doc->appendChild($doc->importNode($child, true));
  }
  return $doc->saveHTML();
}
libxml_clear_errors();
libxml_use_internal_errors($previous_value);
?>
<a href="<?php echo $score_url; ?>" style="text-decoration:none;text-align:center;font-family:Arial Black;color:black;" target="_blank">
<div class="codeeval">
<img src="https://www.codeeval.com/site_media/images/logo-code-eval.png" alt="CodeEval" /><br />
<h3>hacker ranking</h3>
<div class="wrapper-rank">
<?php
foreach ($results as $node) {
    $full_content = innerHTML($node);
   echo $full_content;
}
?>
</div>
</div>
</a>

Here is the CSS I used:

.codeeval img {
display: block;
margin-left: auto;
margin-right: auto;
}
.codeeval h3 {
text-align: center;
color: #CC240A;
letter-spacing: 0.2em;
text-transform: uppercase;
margin: 0;
padding: 0;
}
.wrapper-rank {
background: none repeat scroll 0 0 #CC240A;
padding: 5px;
width: 258px;
height: 69px;
font-style: Arial;
font-weight: normal;
font-size: 12px;
}
.wrapper-rank .main-rank {
background: none repeat scroll 0 0 #BB2610;
clear: both;
overflow: hidden;
padding: 15px;
text-align: center;
width: 228px;
height: 39px;
}
.wrapper-rank .main-rank h4 {
color: white;
float: left;
font-size: 58px;
font-weight: normal;
margin: 0;
padding: 0;
text-align: center;
}
.wrapper-rank .main-rank span {
color: #FFFF00;
float: left;
font-size: 20px;
margin: 15px 0 0 5px;
text-align: left;
}
.wrapper-rank .main-rank span em {
color: #222222;
display: block;
font-style: normal;
font-size: 16px;
}

After the codeeval.php file is created, create this table in the Text widget:

<table>
   <tr style="vertical-align:middle;text-align:center;">
      <td id="codeeval" style="width:100%;vertical-align:top;text-align:center;">
      </td>
   </tr>
</table>
<br />

Lastly, you need to get the unique ID in the URL from your CodeEval public profile for use below. This jQuery statement will populate the table above with the scraped div.

(function($) {
$("#codeeval").load("/codeeval/codeeval.php?codeeval=<<your CodeEval ID>>");
})(jQuery);

For further reading about CodeEval and similar sites, read Thoughts on Professional Learning – Inspired by CodeEval & HackerRank.

%d bloggers like this: