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

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

Scraping a DIV Element from a Web Page with PHP

PHP logo

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.

After completing some of the challenges I decided to see if, like Klout 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" />
<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;
background-color: white;
}
.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>

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.