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

 

 

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?

 

Foray into Cryptography

Until recently my main experience with cryptography was fitting my password to the arbitrary requirements of whatever website I’m signing up for. ‘Crypto’ keeps popping up randomly in web apps, so I bought a used version of Understanding Cryptography to understand… cryptography. The previous owner extensively highlighted the introductory chapter, but abruptly stopped at around page 22. I was about ready to give up too, but the next page has this fantastic quote in the “Lessons Learned” summary section:

“Never ever develop your own crypto algorithm unless you have a team of experienced cryptanalysts checking your design.”

I can definitely get behind something that not only recommends being lazy, but is also one of the major tenets of the field. Despite the brilliance of a single person or small team working in isolation, they will probably never beat the time-tested, heavily researched methods. I love that in the job of hiding information, the experts are extremely open about how to hide it.

One of the first exercises in the book is to crack a deciphered message that uses the infamous Caesar cipher.

The Caesar Cipher, or Shift Cipher, encrypts a document by assigning each letter a numerical value then ‘shifting’ it by some amount. For example, if the key is 3 then ‘A’ becomes ‘D’, ‘B’ becomes ‘E’, and so on. Once you get to ‘Z’ it loops around, so ‘Y’ becomes ‘B’, ‘Z’ becomes ‘C’, etc.

The encryption function e for our cleartext (normal) letter x, looks like this:

e(x) = (x + k) % 26

The decryption function for the encrypted letter y, looks like this:

d(y) = (y - k) % 26

where is the key (the number of spaces to shift) and is the modulo operator.

This encryption method isn’t very secure because the encrypted data retains characteristics of English (or whatever language the cleartext is written in). Certain letters and words are statistically more likely than others, so through analysis of the encrypted text you can determine the encryption key. Here’s the encrypted text given in the book:

“xultpaajcxitltlxaarpjhtiwtgxktghidhipxciwtvgtpilpitghlxiwiwtxgqadds”

Now the plan for decryption (in ruby):

  1. Write helper functions to convert words to numbers where A = 0, B = 1, C = 2, and vice versa.
  2. Write a function that will retrieve the letter frequency from the text
  3. Compare the most frequent letters to the most frequent letters in English to determine the key.

Admittedly, that’s a lot of work when you could just count the letters to skip right to step 3. But let’s pretend we had to do this on thousands of pages worth of data.

To turn letters into numbers I added a method to the String class named numerify:

class String
  #makes it so that 'a' is 0, 'b' is 1, etc.
  def numerify
    num = []
    self.downcase.each_char {|c| num << c.ord - 97}
    num
  end
end

Notice that returns an Array of numbers, so to reverse that function I had to modify the Array class:

class Array
  #takes an array of encrypted letters (as numbers) and turns into lowercase letters
  def denumerify
    letters = ""
    self.each {|n| letters += (n + 97).chr}
    letters
  end
end

Now we write the encryption and decryption functions using the equations from above.

#input: string to be encrypted, key (int)
#output: encrypted string as a comma separated string
def encrypt(x, k)
  e = []
  x.numerify.each {|i| e << ((i + k) % 26)}
  e.denumerify
end
#input: takes in an encrypted string and the key,
#output returns the decrypted string
def decrypt(y, k)
  d = []
  y.numerify.each{|i| d << ((i - k) % 26)}
  d.denumerify
end

Finally, we have to count the letter frequency so we can actually decipher the message. Here was my original way of doing it, which returns a key => value hash (letter => count).

letter_freq = {}
encrypted_text.chars.each do |i|
  letter_freq[i].nil? ? letter_freq[i] = 1 : letter_freq[i] += 1
end

But there’s always a better way! I found this more rubyesque method on Stack Overflow which I could tack onto the ‘String’ class:

class String
  def frequency
    self.chomp.each_char.with_object(Hash.new(0)) do |letter, hash|
      hash[letter.downcase] += 1
    end
  end
  #makes it so that 'a' is 0, 'b' is 1, etc.
  def numerify
    num = []
    self.downcase.each_char {|c| num << c.ord - 97}
    num
  end
end

Almost there. Now we can call the frequency method on our encrypted string to get the letter count, then sort by occurrence:

letter_freq = encrypted_string.frequency
#sort by occurance
sorted_letter_frequency = []
letter_freq.each_pair do |i|
  sorted_letter_frequency << i
  sorted_letter_frequency.sort! do |i, j|
    j[1] <=> i[1]
  end
end

The most common letter in the encrypted text is t, then i, then x. Wikipedia has some nice graphs on letter frequency, but usually you can just assume the most common letter is ‘e’.

E(4) -> T(19) = 15 letters in between, so we print out the decryption with a key of 15, and there’s our answer.

p decrypt(encrypted_string, 15)

I’m not going to spoil this one, but let’s just say these crypto guys are a bit sick in the head. Anyways, it was fun pretending to be Jake Gyllenhaal in Zodiac and I hope to write more about encryption in the future.

 

Mental Exercise for Menial Chores

If there’s one thing I learned from teaching, it’s that one of the most mind numbing activities is test proctoring. Most proctors aren’t allowed to use their smartphone, read a book, draw, or even sit. You are supposed to walk around and “actively proctor,” whatever that means. One of my coping tricks was to determine the collatz sequence of a random starting number, mentally.

A collatz sequence is a simple algorithm that creates a chain of numbers based on a starting ‘seed’ number. The rule is simple:

If n is even then:

n –> n/2

If n is odd then:

n –> 3n + 1

For example if you start with 5, an odd number, the next number would be

3*5 + 1 = 16

Since 16 is even, we divide it by two, so the next number is 8. So far our sequence is

5 –> 16 –> 8

Since 8 is even, we divide by two again, giving us 4. Divide that, and on and on until you reach 1. The overall sequence contains 6 numbers:

5 — > 16 –> 8 –> 4 –> 2 –> 1

This is called the collatz conjecture because it’s unproven whether or not any starting number will always reach one, like in the example above. Here is the question from Project Euler  which I will try to solve.

Which starting number, under one million, produces the longest chain?

How I will approach this problem

  1. Write a helper function that will determine the next number in the sequence
  2. Write a function that will loop through every number keeping track of the number of iterations.
  3. Once the chain has finished, check if it has surpassed the last winner. If it has, then replace it as the current ‘leader’ .

First, the helper function to determine the next number:

def next_collatz(n)
  if (n%2 == 0)
    return n/2
  else
    return 3*n+1
  end
end

Then, declare the variables to keep track of the current leader (longest)

longest = 0
counter = 1
winning_num = 0
x = 1

Construct the loop to go through all numbers less than one million

while counter < 1000000
  x = counter
  chain = 1
  while x > 1
    x = next_collatz(x)
    chain+=1
  end
  #print("N: ", counter, " Had a chain of: ",chain,"\n")
  if (chain > longest)
    longest = chain
    winning_num=counter
  end
  counter+=1
end

Print the winner!

print("longest: ",longest," winningnum: ",winning_num,"\n") #Note this is the number that produces the longest chain, not the length of chain

 

Champernownes Constant

Champernowne was a mathematician/friend of Alan Turing who is most well known for his research on his self-named number, Champernowne’s Constant. You can generate this number by appending positive integers in ascending order after the decimal place:

0.123456789101112131415… etc.

It was a lot easier to come up with unique numbers in the 30’s.

Here are the challenges

1. Write an algorithm to quickly determine what number (0-9) is at a given index. For example, c(4) = 4, c(11) = 0, c(14) = 1, etc.

2. From Project Euler: Determine the product of c(1) * c(10) * c(100) * c(1,000) * c(10,000) * c(100,000) * c(1,000,000)

Since this number is a geometric series, you must know the previous number to generate the next. There is a tempting brute force approach:

c = "0."
i = 1
while i < 10000000
  c += i.to_s
  i += 1
end

While that does work, after 100,000 loops you’re going to start running out of memory. Here’s a better, but still nonfunctional solution:

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
i = 1 #loop number counter
prod = 1
index = 1
c = "0"
while i <= 1000000
  s = i.to_s #we need to check each digit in the string
  #p s
  #c += s
  s.chars.each_index do |j|
    if idxs.include?(index)
      prod *= s[j].to_i
    end
    index += 1 #this is the current place in the constant
  end
  i+=1
end
p prod

That works by changing a second incrementor, index, based on each number’s value. For example, the number ’12’ would change index by 2, the number ‘142’ would change index by 3, etc. It is still too slow to actually do the math.

Unable to find a solution fast enough to store the value in memory and look through it, I went with storing the data into a file instead, and reading in from the file.

First we create the file:

#Approximately 6mb
File.open("champernownes", "a") do |f|
  i = 0
  while i < 1000000
    f<<i.to_s
    i+=1
  end
end

Then we read through it character by character, storing the product whenever we reach one of the indices relevant to the challenge.

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
prod = 1
File.open("champernownes", "r") do |f|
  i = 0
  f.each_char do |c|
    if idxs.include?(i)
      prod *= c.to_i
    end
    i+=1
  end
end
p prod

Be assured this is nowhere near the fastest algorithm for solving this problem, but it was one of the first times that I considered storing the ‘brute force’ solution into a file and then reading from that.