How do dynamic arrays work?

Static Arrays

One thing I disliked about C was that I had to know how many elements were going to be in an array at the time it’s initialized. For example, to make an array of 10 integers you would have to declare it as,

int arr[10];

Then you can put actual integers into it using something like a for loop (it initializes with garbage values in every index otherwise),

for (int i = 0; i < 10; i++) { 
  arr[i] = i;
}

That may seem like a small gripe, but when you start adding user interaction you need a way of handling arbitrary inputs. One solution is to allocate a gigantic amount of memory and just assume the user will get bored of your program before they hit the limit. Another solution is to allocate memory cleverly using malloc() and free(). Isn’t there a better (re: easier) way?

Dynamic Arrays 

One thing I really like about programming languages like Ruby, Python, and JavaScript is arrays are natively dynamic. That means if you declare a pointer to an array in ruby,

arr = []

You can push elements into that array to your heart’s content.

9999.times { |i| arr << i }

Ruby compiles down to C, though, so how come the arrays act different? Ruby arrays dynamically allocate memory based on need, so the programmer doesn’t have to worry about it. How does Ruby accomplish this without allocating a massive amount of memory for every array?

Arrays are initialized as a fixed size, but under certain circumstances they perform an O(n) operation to double the size of the array. Every time this operation occurs, we now have twice as much data we can put in the array. Therefore, push operations still only take O(1) amortized time. You may suspect that in order to add elements to the start of the array it should take O(n) time because we have to scoot every value over, but unshift also only takes O(1) time. This is achieved because the array’s data store acts like a Circular Buffer and adding elements to the beginning or the end of the array is equally as efficient.

 

 

 

OnionUp: Uptime Checker for Tor Onion Services

GitHub | Live

As an extension to the Tor project, three collaborators and I built a tool to automatically check the ping response and load time of Tor hidden services (.onion sites).

Description

Onion services are websites that are accessible through the Tor anonymity network. These services are gaining popularity among journalists and people in repressive countries. In fact, major companies like the New York Times and Facebook recently launched Onion services for their content. By going through Tor, users gain superior encryption relative to unencrypted, or “clearnet,” websites. In order to maintain anonymity, there are certain tradeoffs Tor users are accustomed to. Onion services are much slower than their clearnet counterparts and they go offline frequently. Thus, Tor users would benefit from a utility to check which sites are online before they devote a substantial amount of time and effort connecting. OnionUp is a Pingdom-inspired uptime checker that displays the health of both Onion services and clearnet websites. As an added feature, OnionUp allows users to easily keep track of their favorite Onion services. You can also see handy metrics like average load time, maximum response time, etc.

Metrics!

Project Details

The idea for this project came from asking an experienced Tor user and cyber security advocate what we could do to help the Tor project. He pointed us to the service Pingdom and explained that it would be nice to have that  utility for Tor. After all, it takes a ton more effort to load up a hidden service, so a user dashboard with all your Tor sites would be phenomenal. We sketched out a rough outline of the models: users have many sites, sites have many pings, and got to work filling out the details. After a lot of trial and error with the ruby gem Socksify, we eventually pulled together a proof of concept bare-bones rails app.

(It looked nothing like this…)

A few weeks later, we decided to revisit this project and ‘build it right.’ The biggest issue with the initial application was pinging multiple sites simultaneously. To solve this, we leveraged ruby’s ability to add multiple ‘workers’ to run tasks concurrently (or is it “in parallel?”). The other issue was the cookiecutter 90s looking HTML we hadn’t bothered to style.

We took this opportunity to build out a Single Page App (SPA) using Vue with Vuex for state management. This had the benefit of 1. keeping state manageable, 2. helping us work on separate tasks simultaneously, and 3.  preventing pull requests from causing merge conflicts. We had all built projects with React + Redux before, so it did not take long for us to integrate Vue into this project. The bigger (and unforeseen) roadblock was getting Yarn and webpacker, not webpack, configured properly. It wasn’t until we had to push this to our EC2 instance that we actually started to understand out how the Rails 5.1 webpacker  gem was handling our asset pipeline.

We also popped in the Vuetify plugin to get some fancy spinner animations, important because Tor sites take forever to ping.

Ignore the weird jump at the end

Conclusion 

At its current state, there are still so many things we want to do. Currently, sites come in batches. It would be much nicer if sites updated as soon as they respond, not once the slowest site responds. If Pingdom’s ginormous userbase is any indication, there’s plenty of demand for this tool.

SpaceX Flights: Interactive display of every SpaceX mission

SpaceX Flights

America’s dwindling enthusiasm for space exploration is an unfortunate result of greater societal issues. Thankfully, tech leaders Elon Musk and Jeff Bezo are combatting our apathy by founding their respective innovative aerospace companies SpaceX and Blue Origin. To celebrate their accomplishments, I created SpaceX Flights, an open source tool to visualize every SpaceX Flight from their first mission to their latest.

Users first select the mission they would like to view using an interactive chart that displays the payload mass color-coded by orbit type.

Interactive Chart

After selecting a flight, the orbit is visualized on a spinning Earth using the popular D3 JavaScript Library.

Orbit animation

Many other aspects of the flight are displayed including payload information, rocket type, launch site, and the press video.

Panoramic and satellite view of the launch-site using Google Maps API

 

EventBike: Prototype for Motorcycle Event Planning

EventBike is an event planning tool designed for the motorcycle and bicycle communities. Inspired by Eventbrite, it shares many features such as user authentication, event search, an interactive map, and a user dashboard. The frontend technology for this project is ReactJS styled with Sass. The backend technology is Ruby on Rails with a database powered by PostgreSQL. Check out the Live Version and the GitHub Repo.

User dashboard
Gif!

Using Subversion to Export GitHub Subdirectories

The other day I was trying to download part of an absolutely massive GitHub repository and it took quite a bit of googling to figure out how to do it quickly. I ended up finding a great way to do it using Apache Subversion from the command line.

First, install subversion through brew

brew install subversion

Then, get the directory URL directly from github. For demonstration purposes, I’ll grab a random directory from the postgres repository

https://github.com/postgres/postgres/tree/master/contrib/dict_xsyn

There is one change we have to make to the URL before it can work with SVN, replace tree/master with trunk and paste it into the console in the appropriate directory.

svn export https://github.com/postgres/postgres/trunk/contrib/dict_xsyn

That should automatically retrieve the correct directory and any subdirectories.

How do attr_accessors in Ruby work?

What is attr_accessor?

The attr_accessor automatically creates getter and setter methods for instance variables. The way it generates the new methods for the instance variables is a manifestation of “meta”-programming which we can recreate using define_method. It calls this method once for the setter (attr_writer) and once for the getter (attr_reader).

 

These two examples have the exact same behavior, because Ruby lets you omit parentheses around parameters to beautify your code:

class Dog
  attr_reader :name 
end 
class Dog
  attr_accessor(:name)
end

Making attr_reader

Instead of trying to make both the reader and the writer at once, it might be easier to create the getter method first. We want the generated methods to apply to all instances of the class, but if we called define_method at the instance level how would we know what argument to pass it? Fortunately, if you call define_method in a class method it does the right thing and creates the new method on instances of the class.

class Dog
  def self.getter(instance_var)
    define_method("#{instance_var}".to_sym) do
      instance_variable_get("@#{instance_var}".to_sym)
    end
  end
end

Notice that this uses a baked in method on the Object class, instance_variable_get to retrieve the value of interest.  Now we can monkey-patch Dog to fetch 😉 the value of an instance variable.

class Dog
  getter :nickname
  def initialize
    @nickname = 'doggy'
  end
end

Making a new instance and checking its nickname caused desired behavior. Yay!

spot = Dog.new
spot.nickname #=> 'doggy'

Making attr_writer 

This is almost identical, however, we need to include an equal sign in the method name and an argument in the define_method block.

def self.setter(instance_var)
    define_method("#{instance_var}=".to_sym) do |arg|
      instance_variable_set("@#{instance_var}".to_sym, arg)
    end
  end
end

As you may have guessed, there is also a built-in method on the Object class known as instance_variable_set. 

Putting it all together 

Now with the proof of concept, we can combine the two to create our own version of attr_accessor:

def self.my_attr_accessor(*names)
    names.each do |instance_var|
      define_method("#{instance_var}".to_sym) do
        instance_variable_get("@#{instance_var}".to_sym)
      end
      define_method("#{instance_var}=".to_sym) do |arg|
        instance_variable_set("@#{instance_var}".to_sym, arg)
      end
    end
  end
end

 

 

GitHub: Creating Repositories and Opening/Closing Issues Entirely from the Terminal

You can delegate almost everything essential for git and github to the command line. There two obvious missing links: creating repositories and handling project issues. Here are two tools that allow you to complete these tasks.

Hub for creating repositories from the command line 

1. Install hub using brew with the command

brew install hub

2. Init your repository and do your first commit.

git init 
git add -A
git commit -m "First Commit"

3. Create the repository using Hub’s create command

git create -d "New Project"

4. It may ask you to log in with your GitHub credentials at this step

5. Push to your new repository!

git push origin master

GHI to handle GitHub issues from the command line

1. Install GHI using brew

brew install ghi

2. That’s it! Now you can use ghi to open, close, and edit your issues. Here’s a list of useful commands from the github page

usage: ghi [--version] [-p|--paginate|--no-pager] [--help] <command> [<args>]
           [ -- [<user>/]<repo>]

The most commonly used ghi commands are:
   list        List your issues (or a repository's)
   show        Show an issue's details
   open        Open (or reopen) an issue
   close       Close an issue
   lock        Lock an issue's conversation, limiting it to collaborators
   unlock      Unlock an issue's conversation, opening it to all viewers
   edit        Modify an existing issue
   comment     Leave a comment on an issue
   label       Create, list, modify, or delete labels
   assign      Assign an issue to yourself (or someone else)
   milestone   Manage project milestones
   status      Determine whether or not issues are enabled for this repo
   enable      Enable issues for the current repo
   disable     Disable issues for the current repo

See 'ghi help <command>' for more information on a specific command.

 

 

Simple Web Task Automator using Selenium WebDriver (Ruby Gem)

Tutorial to minimally build an automator that can perform the following actions on an arbitrary website through your chrome browser:

  • Find elements.
  • Click buttons.
  • Enter data into forms.

To accomplish this I used the Selenium Webdriver gem in ruby.

Setup 

Download the latest chromedriver. If you are on a modern version of mac, use macos64 link. Put the downloaded file into your ruby env $PATH. To find that location in the terminal do

$PATH

and look for a path that looks like /Users/name/.rbenv/shims and open that folder.

Move chromedriver into that directory.

Now open a directory and invoke

gem install selenium-webdriver

Browsing Through Pry

Open up pry and load in the webdriver

pry> require 'selenium-webdriver' #=> true

If that does not return ‘true’ there may be an issue with your selenium installation. For the rest of us, go ahead and load the webdriver into a variable and go to the website of interest.

pry> driver = Selenium::WebDriver.for :chrome
pry> driver.navigate.to "https://google.com"

You should see a browser with the message “Chrome is being controlled by automated test software” as you navigate. This will be helpful for selecting the elements we are interested in. Open up the chrome inspect (cmd + option + i) and click on the selector tool (cmd + shift + c). For this tutorial, I will select the Google Search bar.

Right click on the element from the inspector and select “Copy XPath”

Now back in pry, set a new variable as our element of interest using the xpath key:

pry> element = driver.find_element(xpath: '//*[@id="q"]')

We can now set this using the send_keys method on our element.

pry> element.send_keys "puppies"

Now find the ‘Google Search’ button using the same method as before (inspector), get the xpath, and click on it.

pry> button = driver.find_element(xpath: '//*[@id="tsf"]/div[2]/div[3]/center/input[1]')
pry> button.click

If everything worked, puppies should appear! If you want to automate a similar task on a regular schedule, create a ruby file executable and set it to automatically run using cron jobs.

Issues

My chromedriver would occasionally remove itself from the ruby shims folder. To remedy this, I created a bash script that would copy  chromedriver into this folder.

Ensure your chromedriver file is in a directory that is not in your $PATH and do the following:

Open a bash script file (foo.sh) 

#!/bin/bash
cp chromedriver '/Users/path/to/.rbenv/shims'

Ideally I would figure out the root of this error, but this hacky solution worked for me.

Add Two Numbers Without the Addition Sign (Ruby)

A weird interview question for software development interviews is “add these two numbers without using the plus sign.” I was taken aback by how zen-like and strange this question sounds at first, but by using a bit of binary math I was able to solve it.

My First Approach

Example input: Add 5 and 8

In ruby, the to_s method can turn Fixnums into their binary form.

I’m going to add a “0” to the start of the binary representation of five so it’s the same length as the eight.

Adding 5 to 8 is a special case because there is no instance where you have to carry the one. My naive first approach was to use the | (or) operation on each digit and you will get the desired result.

0101 | 1010 => 1101

Because,

0 | 1 => 1

0 | 0 => 0

1 | 0 => 1

0 | 1 => 1

So our answer is “1101”, which is equal to our goal, 13. (1 + 4 + 8)

However, this will not work with something like 4 + 4. The binary form of 4 is “100” and 8 is “1000”. Trying the naive approach above,

100 | 100

0 | 0 => 0

0 | 0 => 0

1 | 1 => 1

100 + 100 = 100? Something went wrong. So, we need to literally “carry the one” when both digits equal 1

0 ? 0 => 0

1 ? 0 => 1

1 ? 1 => 10

0 ? 1 => 1

It took me quite a bit of trial and error to tackle this problem, but here is my solution.

The Plan

(1) Helper function to go from a decimal number to a binary number array, e.g., 5 -> [1, 0, 1]

(2) Helper function to add zeros to the front of the shorter array to equalize the length of two binary arrays, e.g.,

[1, 0, 1] and [1, 0, 0, 0] become

[0, 1, 0, 1]  and [1, 0, 0, 0]

(3) Function to add bits, e.g., 0 & 0, 1 & 0, and also take into account ‘carrying’ bits over.

(4) Function to add the entire binary array

(5) Function to convert back from binary array to decimal

(6) Function that puts it all together! Input two decimal numbers and output their sum.

The Ruby Program 

(1) Decimal to binary array

#input: decimal e.g. 5
#output: binary array e.g. [1,0,1]
def dec_to_bin_array(dec_num)
  #turn into array of string chars
  bin = dec_num.to_s(2).chars
  #convert to integers
  bin.map(&:to_i)
end

(2) Equalize length of two binary arrays

#input: two arrays of 0s and 1s
#insert leading zeros to beginning of shorter array to equalize length
def equalize_length(arr1, arr2)
  while arr1.length < arr2.length
    arr1.unshift(0)
  end
  while arr2.length < arr1.length
    arr2.unshift(0)
  end
end

(3) Add bits together and take into account carry operations

#input: bit1, bit2, amount to carry
#output: [digit to carry over, digit to insert to end of sum]
def add_bits(bit1, bit2, carry)
  return [1, 1] if bit1 == 1 && bit2 == 1 && carry == 1
  return [1, 0] if (bit1 == 1 || bit2 == 1) && carry == 1
  return [0, 1] if (bit1 == 0 && bit2 == 0) && carry == 1
  return [1, 0] if bit1 == 1 && bit2 == 1 && carry == 0
  return [0, 1] if (bit1 == 1 || bit2 == 1) && carry == 0
  [0, 0]
end

(4)  Add each bit of the arrays together to form the bit sum

def add_binary_arrays(arr1, arr2)
  sum = []
  equalize_length(arr1, arr2)
  carry_digit = 0
  while !arr1.empty?
    m = arr1.pop
    n = arr2.pop
    v = add_bits(m, n, carry_digit)
    carry_digit = v[0]
    sum.unshift(v[1])
  end
  sum.unshift(carry_digit)
  sum
end

(5) Go from binary array to decimal (recursive approach)

def bin_array_to_dec10(arr, n = 0, pow = 0)
  return n if arr.empty?
  n += arr.pop * (2**pow)
  bin_array_to_dec10(arr, n, pow + 1)
end

(6) Put all the above together to get the answer.

#input: two base10 numbers
#output: their sum 🙂
def add_two_numbers_using_bitwise_operations(a, b)
  m = dec_to_bin_array(a)
  n = dec_to_bin_array(b)
  v = add_binary_arrays(m, n)
  bin_array_to_dec10(v)
end

I found this problem enjoyable to work through because it helped me understand one of the most fundamental operations performed by the computer.

Computer Time is Cheap – Human Time is Expensive

While working on a simple roulette betting game I ran into a roadblock with two ways I could proceed. I asked on reddit and stackoverflow, but in the meantime I realized I should just implement one and get on with my life. Seizing up/writer’s block is a real problem!

Background on Roulette 

While roulette is one of the simplest casino games, there are over a hundred unique bets. The simpler ones are bets on red or black, even or odd, or a specific number (playing it straight). However, There are plenty of weird edge case betting strategies in roulette, which makes bet checking nontrivial. For example, Street bets are a bet on three numbers, but not just any random three — they must be in a grid row. In American Roulette there are

  • 10 simple bets (red, black, etc.)
  • 38 straight up bets (0,00,1,2,3,..,36)
  • around 50 split bets (1 + 2, 4 + 7, 0 + 1, etc.)
  • 12 street bets (1 + 2 + 3, 22 + 23 + 24, etc.)
  • 22 corner bets (1 + 2 + 4 + 5, 8 + 9 + 11 + 12, etc.)
  • 3 column bets (1 + 4 + 7 +.. +34)
  • 6 six-line bets (1 + 2 + 3 + 4 + 5 + 6)

Bet Validity Check

The Simple Route (Hash Table): Create a hash table that contains all possible hash values and check against the table. Human Time Estimate: ~1 hour

The Fancy Route (Linked List of Nodes): Create a doubly-linked list of elements where each element represents a possible outcome (e.g., 0,1,2,3 .. 36) and each is linked to its neighbors. For example the number ‘1’ would be linked to ‘2’, ‘4’, and ‘5’. This gets complicated because you cannot make a split bet on ‘1’ and ‘5’, but you can make a corner bet on ‘1’, ‘2’, ‘4’ and ‘5’.

I’m interested in what the time difference between each would be, so I am going to try both and profile the results. This is a scenario where I can estimate the human time as well. Is it faster to brute force the two hundred or so unique bets into a hash table, or create the data structure?