I Programmed My Way Into a Mud Cave

I’m a big fan of Geocaching. If you are unfamiliar with it, it’s a worldwide activity, where by using a GPS you can search out hidden containers. These containers contain a logbook and usually other small toys and trinkets. There are over a million geocaches worldwide in over 200 countries and territories. Learn more about it here.

This post is about geocaching, programming, and the surprise I found when I was able to make them intersect. A special “puzzle” geocache that I came across required you to unscramble this encrypted message using this fuzzy picture and the coordinates N32° 40.990 W117° 11.025 as hints. I knew the real location for the cache was somewhere in the deserts of San Diego county, and I had to solve the puzzle to find the coordinates.

I had figured out the methodology to the decryption and that another word was required as a key. From that, I knew that once I had found the key, the manual process of decrypting that whole message could take hours. Enter coding. I wrote a program that accepted any key and decoded the message with the inputted key. Not yet knowing what the key was, I attempted to cheat and iterate through the entire dictionary to see if anything comprehensible was returned. That failed, and my corner cutting mission was thwarted. Therefore, I knew that the key was not a normal dictionary word.

You can find the program on Github here.

I don’t want to give anything away, but I eventually figured it out. Anyone can figure it out, it isn’t necessary to go to those coordinates, so give it a shot and run it through my program if you think you’ve got it.

The program was relatively simple, and all I did was extend the String class by adding a method that returned the ASCII value of the character. This made the rest of the program easy, as it was just arithmetic from there on out.

1
2
3
4
5
class String
  def to_num
    self.downcase.bytes[0]
  end
end

Once the puzzle was solved, the trek to the Arroyo Tapiado mud caves in the Anza-Borrego desert was a one filled with anticipation. After a grueling hike through the low ceilings and narrow passageways of this mud cave, we emerged, climbed up a few more small mountains, and located the cache. An amazing adventure all around. An adventure with a big assist from code.

If anyone knows of any other caches what were solved with code, or knows of any amazingly adventurous caches such as this, please let me know. I’d love to do them.

Memoization and Why Does It Feel So Good to Optimize?

Recently I was faced with a challenge from Project Euler and asked how I would best optimize the solution I wrote. Thinking for a little bit, I made a few changes, but none were as efficient as memoization.

Memoization is the idea of storing data in memory so it is available to be referenced again at a later time, instead of running logic that you have already ran with the same inputs. I’ll show you how we can use memoization and a little bit of basic math to optimize a different problem from Project Euler.

Project Euler Problem #21: Amicable Numbers

1
2
3
4
5
6
7
8
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair
and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110;
therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

You can find my first solution here. Obviously, the most expensive operations in an program are those which iterate or recurse. In this case, we have one different loop that looks particularly expensive:

1
2
3
4
5
6
7
def find_sum_of_divisors(num)
  sum = 0
  num.times do |i|
    sum += (i+1) if num % (i+1) == 0 && num != (i+1)
  end
  sum
end

Here, we attempt to divide each number by each number smaller than it. If we are calling this loop on elements, then this will loop times for every , for a time complexity of .

As the problem states, we need to compare the sum of the proper divisors to the proper divisors of the sum itself. Therefore, we call the above method twice in this method:

1
2
3
4
5
6
7
8
9
def is_amicable?(num)
  a = find_sum_of_divisors(num)
  b = find_sum_of_divisors(a)
  if num == b && a != b
    true
  else
    false
  end
end

So, we wrote this program. Let’s see how long it takes:

1
This took 5.733192 seconds

Ok, let’s try to do better. First of all, let’s think of a math way to fix that find_sum_of_divisors method. No ruby magic here. Since there are no integers less than 2 that divide into any number to come up with a proper divisor, all the numbers given an in $n\ge a\gt n/2$ do not need to be evaluated as those will always be $\gt2$. So instead of num.times in ruby, we can change it to:

1
2
3
4
5
6
7
def find_sum_of_divisors(num)
  sum = 0
  (num/2).times do |i| # num is now num/2
    sum += (i+1) if num % (i+1) == 0 && num != (i+1)
  end
  sum
end

Now let’s try running the program again:

1
This took 2.88388 seconds

We’ve, predictably, sliced our running time in half. Great! But we can do better. Remember memoization? Let’s do that.

When we run this problem, it is very possible that we will be running find_sum_of_divisors on the same number multiple times. Because this is a posibility, we can try storing the result of each method call in a hash and referencing it if we need it again, instead of calling the same method again.

To do this, let’s initialize an empty hash each time we instantiate a new Amicable object.

1
2
3
4
def initialize(max)
  @max = max
  @hash = {} #<--- Add this line
end

Finally, every time we go to call the find_sum_of_divisors method, we should check to see if we already have for a given number. If we do, we can just use that data and not call the method, saving valuable time:

1
2
3
4
5
6
7
8
9
def is_amicable?(num)
  @hash[num] ||= find_sum_of_divisors(num)
  @hash[@hash[num]] ||= find_sum_of_divisors(@hash[num])
  if num == @hash[@hash[num]] && @hash[num] != @hash[@hash[num]]
    true
  else
    false
  end
end

Great, now instead of calling a method, we can refernce data in a hash. Let’s see how much faster we made it:

1
This took 1.997799 seconds

Just under two seconds, awesome! I’m sure there’s even more optimizations possible. Submit a pull request to my code if you want to try. You can check out my Github repo for the problem here.

Passing Ruby Data to Javascript

Using more front-end APIs and frameworks, I’ve found it useful to be able to, at times, pass data from ruby to my Javascript files. The first time I ran into this problem was in Avoid, the NYC restaurant and health violations lookup tool I helped create. In this app, I used the Google Maps API to dynamically update the geographic coordinates of restaurants in bad shape on a google map. I found this diffucult to do as you can’t normally access Ruby data from Javascript. I’ve since found out a few ways to do so, and I’ll tell you about them now.

Data Attributes

One of the simplest ways to pass a very limited amount of data is to use a data attribute on an HTML tag. For example, if I wanted to pass a longitude and latitude from my rails app to Javascript by extracting it through the DOM with jQuery:

index.html.erb
1
<span class="latlong" data-latitude="32.796283" data-longitude="-117.129574">Something that doesn't matter</span>
coords.js
1
2
$(".latlong").data("latitude"); //= "32.796283"
$(".latlong").data("longitude"); //= "-117.129574"

As you can see, this is realatively simple and straight forward. It doesn’t matter what is inside whatever tag you have used to store your data, you’re just referencing the attributes of the tag itself. Also, it could be any type of tag. This is easy when the data you need to access isn’t an object, but it a more primative data type, or string.

Gon Gem

The Gon Gem is another way to do this, and it is generally more useful when you are trying to pass more complex data-types, such as objects. Very simply, just install Gon: <div class=’bogus-wrapper’>

<figcaption>Gemfile.rb</figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 </pre></td><td class=’code’><pre>gem 'gon' # Put this in your Gemfile </pre></td></tr></table></div>
</div> Then, in your conroller, or really wherever in your app you want to store your data for Javascript use: <div class=’bogus-wrapper’>
<figcaption>Users_Controller.rb</figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 </pre></td><td class=’code’><pre>gon.last_three_users = User.order(name: :desc).limit(3) </pre></td></tr></table></div>
</div> <div class=’bogus-wrapper’>
<figcaption>users.js</figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 </pre></td><td class=’code’><pre>console.log("Welcome our three newest users!"); for( var i=0; i<gon.last_three_users.length; i++ ){ console.log(gon.last_three_users[i].name + "!"); } </pre></td></tr></table></div>
</div> Simple enough. That saves a lot of time and cleans up your views nicely. No more Javascript hanging out in .html.erb files.

Building a Solid Foundation

I’m a math guy, a numbers dude, and and analytical person at my core. The one thing about web design that scared me the most is the front-end. Have you seen my artistic side? One time I drew a stick figure and the paper exploded. True story. Thankfully, things like Twitter Bootstrap and Foundation exist for artistically inept people such as myself to look like we majored in a liberal art.

For those who don’t know, Foundation is basically just a huge CSS library that makes your website actually look visually appealing. You can add class attributes to your HTML elements for control over your layout and other basic functions. For a rails app, here is the long and tedious process to install Foundation:

1
gem 'foundation-rails' # Add this to your Gemfile

Then, on your command line, run ‘bundle install’ and ‘rails g foundation:install’ to generate the Javascript and CSS files it needs. You’re done! Phew!

Foundation will add a few files to your /assets/javascript and /assets/stylesheets directories. The main one you should care about is the foundation_and_overrides file in the stylesheets directory.

The main thing you should know when styling your page with Foundation, is that each “row” is split up into 12 the width of 12 columns. All the neat features are in classes you add as attributes to your tags. For example:

1
2
3
4
5
6
7
8
9
<div class="row">
  <div class="small-4 columns">
    This is some text on the first third of the page, vertically.
  </div>
  <div class="small-8 columns">
    This is some text on the latter two-thirds of the page, vertically.
    <a href="http://www.google.com" class="button">This button goes to Google</a>
  </div>
</div>

As you can see, the number of columns in a row add up to 12, as should be. You can also nest rows and columns inside other rows and columns. For a stylistically challenged person such as myself, this simplicity is invaluable.

But let’s say you want to style your links so that text link fonts are red. Remember that foundation_and_overrides file I talked about earlier? Go to that file and look for anchor tag styling … ah, here it is!

1
2
3
4
// We use these to style anchors
// $anchor-text-decoration: none;
// $anchor-font-color: $primary-color;
// $anchor-font-color-hover: scale-color($primary-color, $lightness: -14%);

Now all you do is uncomment the font color and replace it with hex red:

1
2
3
4
// We use these to style anchors
// $anchor-text-decoration: none;
$anchor-font-color: #f00;
// $anchor-font-color-hover: scale-color($primary-color, $lightness: -14%);

Pretty easy huh. You can still go and define your own CSS if you want, but this process makes things much easier.

One thing I was most worried about when getting the front-end all nice and pretty was the navigation bar. With foundation, key in a few div tags and you’re done.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<div class="contain-to-grid sticky">
  <nav class="top-bar" data-topbar>
    <!-- Left Nav Section -->
    <ul class="left">
      <li><%= link_to "App Name", root_url %></li>
    </ul>
    <!-- Right Nav Section -->
    <ul class="right">
      <li><%= link_to "Products", products_path %></li>
      <li class="has-dropdown">
        User Info
        <ul class="dropdown">
          <li><%= link_to "Sign-In", login_path %></li>
          <li><%= link_to "Sign-Up", new_login_path %></li>
        </ul>
      </li>
    </ul>
  </nav>
</div>

The div class sticky makes it so if you scroll down, the nav bar remains fixed to the top of your screen. I don’t like that, but I thought I’d show you anyway. Everything else is pretty intuitive, just make sure you add the right class to your tags and you’re good to go.

In all, Foundation is a quick way to make your website actually visually appealing in no time at all. And if you’re artistically retarded such as myself, it makes you passable for at least starving-artist status.

Geocoder and My Very First Gem Attempt Part 1

I’ve always been weirdly into maps and geography. Back in 2010 I was introduced to Geocaching and, from then on, suspciously looking around from tupperware was one of my new hobbies. A week ago, I presented the web app I worked on for The Flatiron School’s meetup. The app showed the restaurants with the most health code violations in a zip code. I was able to implement a gem I found, called Geocoder, to convert addresses to geographic coordinates for use in the Google Maps API so I could show the exact location of offending restaurants on a map. I didn’t really know too much about Geocoder and was only able to implement one method to find coordinates:

1
Geocoder.coordinates("11 broadway, new york, ny") #=> [40.7055269, -74.014346]

But there is a much cooler way to use Geocoder: with ActiveRecord.

If you want to geocode your table en masse, you can add both a latitude and longitude column in your database table connected with ActiveRecord. Then, in your model, add the following lines:

1
2
3
extend ::Geocoder::Model::ActiveRecord
geocoded_by :address
after_validation :geocode

That first line apparently provides you with the methods you are using on the next two lines. When you add the geocoded_by line, the geocoder uses the column you designate as the input to be geocoded. I’m not exactly sure what after_validation does, but it seems like that it designates the direction of gecoding. Meaning here we are specifying we want to convert an address into coordinates, as Geocoder also can convert coordinates into and address.

So each time I save an element in my table, the geocoder gets the address and fills in the latitude and longitude automatically. I did all these, ran my program, and got this error:

1
Google Geocoding API error: over query limit.

You have apparently have to be gentle. So I told my program to wait 5 seconds in-between each geocode so Google wouldn’t be upset at me. It may work with a smaller number of seconds, but 5 seemed to work fine for me.

1
2
3
4
5
6
7
8
9
10
def seed_db
  JSON.parse(RestClient.get(url))["data"].each do |line|
    next if line.last == "Borough"
    f = Firehouse.create
    f.address = "#{line[9]} #{line[10]}, NY"
    f.save
    puts "Geocoding: #{f.address}"
    sleep 5
  end
end

So we’re good! Now we have a database full of addresses and their coordinates.

One more thing I found cool with Geocoder was that you can pass it an external IP address and it also returns coordinates! But don’t think you can stay spying on everyone now, the coordinates that it returns have a margin of error which I found pretty significant for NYC, about a half a mile. For the gem I’m attempting to write, I have used the user’s external IP address as the default starting location for directions to the nearest firehouse.

Speaking of which, I am attemping to use this program as an educational experience in my first gem. Using the near function in Geocoder, I can pass geocoder a location (IP, physical address, landmark, etc.) and it can return the nearest location in our geocoded database. I have the program working, but the transition into a gem has been difficult and clunky. Integrating other gems and using bundler has proved to be a thorn in my gem creation’s side. This is the error I’ve been receiving:

1
/Users/caguthrie/.rvm/gems/ruby-2.0.0-p353/gems/bundler-1.5.2/lib/bundler/shared_helpers.rb:24:in `default_gemfile': Could not locate Gemfile (Bundler::GemfileNotFound)

I’ve been pointing directly to the Gemfile in the gemspec and it doesn’t seem to care. Interestingly enough, the gem works if I run it in the directory where my source files are. However, it does not if I attempt to run it outside that folder. The search continues, I will surely, shortly figure out the solution, then people everywhere around NYC can get google maps’ walking directions to the nearest firehouse. Soon enough.

Wait for part 2 of this blog post when I finally figure out how to create a proper gem.

Smooth as Sinatra

The best revenge is massive success.
-Frank Sinatra


Even in death, Sinatra is continuing to make people swoon. Sinatra is a web framework for Ruby applications and it makes creating and deploying them super simple. As a Sinatra beginner, I have been looking into the documentation to find some neat tricks with this framework and I’d like to share them with you. So come fly with me, let’s fly away …


<h3>Sinatra Splat</h3>
<p>Sintra is flexible in that there are many ways to implement wildcards in pathnames. For example:</p> <div class=’bogus-wrapper’>

<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 </pre></td><td class=’code’><pre>get '/favorite_singer/*/favorite_album/*' do # example: /favorite_singer/frank_sinatra/favorite_album/come_fly_with_me params[:splat] # => ["frank_sinatra", "come_fly_with_me"] end </pre></td></tr></table></div>
</div>

Here, you can let your user go to any sub-path where your wildcards are and get those sub-path names back to you in a handy array using the :splat symbol key in the params hash. This could be useful in a product catalog, or in any case where there could be a large number of keys that could return data from a database. There are other useful ways to use splats in pathnames, like for downloads:

1
2
3
4
get '/download/*.*' do
  # goes to /download/path/file.zip
  params[:splat] # => ["path/file", "zip"]
end

If you wanted a custom page for your users to look at while they download a file, you could easily do something similar to that. Sites like cnet.com and download.com may use Sinatra as they similar downloader pages.


<h3>Multiple gets for a sub-path</h3>
<p>Sometimes you want to have a specific sub-path case, with a catch-all, psuedo-else get method if a different sub-path is chosen. Looking back at unnecessary complexity of the previous sentence, that may make zero sense to some people. So, I have an easy example below:</p> <div class=’bogus-wrapper’>

<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 5 6 7 8 </pre></td><td class=’code’><pre>get '/the_capital_of/california/:cap' do pass if params[:cap].downcase != "sacramento" "Correct!!" end get '/the_capital_of/california/*' do "Your knowledge of 3rd grade US geography is disasterous!" end </pre></td></tr></table></div>
</div>

Using the pass method in sinatra, the rest of the logic in the first get block is not executed and the next get method fitting the path parameters is executed. It’s another added bonus of the lazy ruby interpreter.


<h3>Browser Redirect</h3>
<p>Lastly, you may want to redirect a user to a different path after you’ve taken some action. Maybe, for example, after you’ve filled out a form or shown a quick advertisment. The redirect method is a quick way to do that, and you can implement it like so:

1
2
3
4
5
6
7
8
9
get '/restricted_area' do
  "Why are you here!? Go away!"
  sleep 2
  redirect to('/public_area')
end

get '/public_area' do
  "Welcome!"
end

So pull up a fine leather chair, a glass of scotch, and enjoy the classiness that Sinatra has to offer you. If there’s a problem in a web app you need solving, old blue eyes has you covered.

Enumberable Is Enumermazing

Coming from lower-level languages, the vast spectrum of built-in classes, modules, and methods in Ruby is absolutely mind-blowing. One of the most amazing of these is Enumerable. Enumerable is a mixin, which means that it adds functionality to the class that uses it. Oh, and functionality there is. The two most common objects that can call Enumerable methods are arrays and hashes. It is robust and adds some methods that do exactly what you think they would. For example:

1
2
3
find
any?
include?

The functionality I have found most useful are the searching and sorting methods. I’ll tell you about three of my favorites now.

<h3>sort</h3>

The sort method might seem like a shy, simplistic wallflower, but, with the power of blocks in ruby, sort transforms into a something any high school prom king would tremble at the sight of. Take this example:

1
2
3
4
5
6
7
favorite_people = {
    :poet => "Walt Whitman",
    :baseball_player => "Tony Gwynn",
    :jeopardy_champion => "Ken Jennings",
    :billionaire => "Bill Gates",
    :dean => "Avi Flombaum"
  }

Let’s say you have this hash of favorite people and wish to sort it into an array, based on alphabetical order of their last name. Is that description of what I want to do longer than the code?

1
2
3
4
5
6
7
favorite_people.sort{ |a, b| a[1].split(" ").last <=> b[1].split(" ").last}

#=> [[:dean, "Avi Flombaum"],
#   [:billionaire, "Bill Gates"],
#   [:baseball_player, "Tony Gwynn"],
#   [:jeopardy_champion, "Ken Jennings"],
#   [:poet, "Walt Whitman"]]

Yep.

When used on a hash, sort converts your hash to an array of arrays of length 2, where each sub-array is a key/value pair. This is defined in the hash’s each method, a method I will talk more about a little later. Enumerable’s sort function uses these return values to sort your input. The great thing about the sort method is that you can sort it however you tell your program to. No more iterating though your entire data structure. This is even more relevant because if you have an object you would like to use with Enumerable, all you have to do is define an each method in your class which yields each value you would like Enumerable to operate on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class DeliciousFood

  include Enumerable

  def yum
    ["Tangerine", "Burrito", "Cake", "Artisanal Pizza", "Bacon Grease"]
  end

  def each
    yum.each do |y|
      yield y
    end
  end
end

DeliciousFood.new.sort { |a, b| a <=> b } #=> ["Artisanal Pizza", "Bacon Grease", "Burrito", "Cake", "Tangerine"]

You want your class to be Enumermazing? Just like that, it’s as easy as defining an each method.

<h3>grep</h3>

The method grep is, just as you command line monkeys would think, a function that allows you to search through your data and find what matches your search parameter(s). Just like sort, and many other methods in Enumerable, grep can take a block to create your own custom searches. Let’s return to our DeliciousFood class above and try searching for each piece data that includes the letter “k” or “z”, because I only eat food that contains at least one of those letters:

1
DeliciousFood.new.grep(/(k|z)/) { |a| "I ate some " + a } #=> ["I ate some Cake", "I ate some Artisanal Pizza"]

<h3>partition</h3>

Lastly, a fun, easy, and quick way to put things into two different arrays. The partition method takes in some data, and outputs it in an array of two arrays. If the block passed into it evaluates as true, it gets placed in the first sub-array. If not, it gets placed in the second sub-array. Lets say I’m hungry but I’m confused about what to eat from my kitchen table:

1
2
3
4
5
6
7
food = ["Tangerine", "Burrito", "Cake", "Artisanal Pizza", "Bacon Grease"]
not_food = ["Concrete", "Fedora", "Silica Gel", "Cigarette Butt"]

my_kitchen_table = ["Concrete", "Tangerine", "Burrito", "Fedora", "Cake"]

output = my_kitchen_table.partition { |item| food.include?(item) } #=> [["Tangerine", "Burrito", "Cake"],["Concrete","Fedora"]]
puts output[0] #=> ["Tangerine", "Burrito", "Cake"]

Thankfully Enumerable and partition saved me from eating concrete or my fedora. What can’t Ruby do?