Ruby Koans

I’ve hosted my solutions for the Ruby Koans on GitHub here:

https://github.com/skunkworks/ruby-koans

I’ve kept up a verbose commentary within the koans code files — each novel insight receives a comment, and every question posed receives a detailed answer.

My approach has been to honor the intentions of its creators by reflecting on deeper insights into Ruby. Lots of googling, lots of reading, lots of pulling up irb to experiment. On more than a few occasions, a novel concept or a “why” question has caused me to get sidetracked for an hour or more just trying to learn more about the mechanics of Ruby

Needless to say, the koans have been really, really fun.

attr_accessor_with_history

The Engineering SaaS textbook for the CS169.1x edX course I’ve been taking has a list of exercises and “suggested projects” for each chapter. I’ve been working through them, along with the Ruby Koans, and came upon the following question:

Project 3.6: Define a method attr_accessor_with_history that provides the same functionality as attr_accessor but also tracks every value the attribute ever had.

class Foo
  attr_accessor_with_history :bar
end
f = Foo.new # => #
f.bar = 3 # => 3
f.bar = :wowzo # => :wowzo
f.bar = 'boo!' # => 'boo!'
f.history(:bar) # => [3, :wowzo, 'boo!']

This is a great question to demonstrate Ruby’s metaprogramming. As I sat down, I got a creeping sensation that I’d done this before. Of course: the corresponding edX online course used this as a homework question, except…

Except the requirements were slightly different.

The online version of the question asked for f.bar_history whereas the book version asks for f.history(:bar).

This was enough of a difference to throw me.

Here’s the general framework for my solution:

First, we’re opening up the “Class” class, which will allow any class definition to declare an attr_acceessor_with_history.

class Class
  def attr_accessor_with_history(attr_name)
  ...
  end
end

This is truly mind-bending. What the hell is going on?

Well, in Ruby, there are no static class declarations like you’d see in Java or C#. A class declaration in Ruby is really just a call to a method named “class”, which creates an instance of the Class class with whatever behavior you choose to bestow to that class’s type. Your class is just an object, but it’s an object that helps define what the behavior of that class type’s instances will be.

Let’s look at an example:

class Foo
  attr_accessor :foo
end

Inside of your Foo object — which is a Class instance — you’ve invoked a call to the attr_accessor method with :foo as a parameter. This creates a getter and setter method named after :foo.

What we want to do is make it so that Foo can call the attr_accessor_with_history method.

Our first attempt might do something like this:

class Class
  def attr_accessor_with_history(attr_name)
  ...

but if you look at the Ruby docs for attr_accessor, attr_accessor is defined in the Module class, so let’s modify it there:

class Module
  def attr_accessor_with_history(attr_name)
  ...

We want the instance of our class to respond to the getter method so that we can do this:

f = Foo.new # => #
f.foo = 3 # => 3

We can do this by leveraging a method that already exists, which is attr_reader.

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
  ...

At this point, you can actually do this:

f = Foo.new # => #
f.foo # => nil

But doing this will fail:

f.foo = 3
NoMethodError: undefined method `foo=' for #

Of course, we haven’t created a setter. Let’s do that.

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_writer attr_name # or attr_accessor attr_name
  ...

No! Don’t do this! I mean, well, yeah, you will then be able to assign values to foo, but we need to do more than just that: we need to keep track of its history too.

To do that, we need to provide a custom definition for the assignment method. To do this, we will leverage another method called class_eval, which allows a class to add an instance method to itself:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
    ...
    }
  ...

In this example, we’ve passed it a string (read up on %Q if you’re confused how that’s a string). That string needs to contain the method definition:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
      ...
    }
  ...

Remember that “def #{attr_name}=(value)” once interpolated will become “def foo=(value)”.

We need to save the value into the instance variable (which is already created by attr_reader):

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name} = value
      end
    }
  ...

But now we need to add the history functionality. Let’s review the possible cases:

  • foo has not been set: foo_history should return nil
  • foo has been set to 1: foo_history should return [nil]
  • foo has been set to :bar: foo_history should return [1]
  • etc.

Let’s save the history of values in an array, which we stash into an instance variable named @#{attr_name}_history:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }
  ...

We need to user to be able to call f.foo_history to get this instance variable:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }
  ...

Note that wrapping up attr_name into an interpolated string makes sure that the name of the attr_reader gets properly converted.

When we run this code, it totally works!

foo.foo_history works, but we need to get foo.history(:foo) to work.

This is where things got really difficult for me. Okay, let’s take a swing at it!

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
      def history(name)
        @#{name}_history
      end
    }
  ...

This won’t work, sadly. Why not? Because when we call @#{name}_history, it won’t work since the scope of attr_accessor_with_history doesn’t have a variable “name”.

What we need is to somehow create an interpolated string with the history argument’s value.

The solution is to use the version of class_eval that accepts a block, and use a method called instance_variable_get to return the instance variable:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }

    class_eval do
      def history(name)
        instance_variable_get("@#{name}_history")
      end
    end
  end
end

Note how instance_variable_get makes it possible to get a variable from its name string only.

Initial impression of CS169.1x

I’ve been taking an edX course CS169.1x Software as a Service, which is a UC Berkeley course on building SaaS apps with Ruby on Rails.

One of the lecturers, Armando Fox, might be the most talented lecturer I’ve seen.

The authors openly embrace the concept of the 5 Whys and do a really wonderful job of not just explaining what to do, but why we do it. This fits in line with what I’ve read about effective learning: you need the big picture to tie together disparate concepts into a cohesive framework. Setting up the big picture allows you to snap the little bits into place with ease. And finally, when it comes time to apply that knowledge, the framework itself serves as a mnemonic.

The accompanying textbook, Engineering SaaS, which is written by the instructors of the class, is also rather good at providing a framework of “why”:

  • Why do we build SaaS apps?
  • Why is Rails a good choice to build SaaS apps?
  • Why is Agile a good process for building SaaS apps?
  • Why does Rails embrace MVC?
  • Why do my instance variables disappear after each Rails controller action?

The course spends a decent chunk of its time explaining not only the Agile process, but the *opposite* of the Agile process, which is Plan-and-Document. It’s a smart choice to offer the alternate perspective because it ultimately strengthens understanding of Agile; again, it answers the question, “Why do we use Agile?”

On a personal note, as an old dinosaur who graduated from a CS program in 2004, it’s hilarious to see how much has changed. I remember taking a class dedicated to building software requirement specifications. We drew UML diagrams in Rational, came up with formal use cases, learned about Waterfall and Spiral, and oh yeah, there’s this new methodology called Agile that iterates super-fast but it’s sort of unclear if it’s really a formal methodology. I remember giggling to myself when we touched on Extreme Programming (XP): TOTALLY EXTREMEEE.

iOS 7 support for ColorMyWorld

iOS 7 support for ColorMyWorld was a little trickier than I thought it would be. I added support for Pantone colors, fixed a bug with some jumpiness during zoom, added a double-tap to zoom feature. That was all easy.

The trickiest part was fully adopting a pure Auto Layout implementation of the UI, as is recommended in iOS 7. It took the better part of two days to fully grasp the basics. In the future, I’ll have to learn a little bit more about how to manipulate constraints programmatically, as I only know the basics of the visual format language, but for now, I’m happy to be where I’m at.

Floyd’s Cycle Detection Algorithm

I just spent half a day trying to wrap my brain around how to detect cycles within linked lists, as well as how to find the first node of the cycle. After perusing all the Stack Overflow and Wikipedia entries, I had a pretty good mechanical understanding of the most elegant solution, which is known as Floyd’s Cycle-Finding Algorithm, or more informally, the tortoise and the hare algorithm.

The problem with my mechanical understanding was that it’s a classic case of surface-level learning, the kind of sloppy, rote-memorization cramming that somehow powered me through UCI to a 3.2 GPA but left me utterly uninterested and disengaged from my craft. I’d perform well if an interviewer asked me that question tomorrow, but I’d feel like a charlatan if I only parroted an answer back at him. Just because I flipped through some old tome and found an incantation that allowed me to cast a black magic wizard spell doesn’t make me Harry Potter.

I wanted an intuitive understanding of the solution. If I have that, I will carry it for the rest of my life.

In the name of that pursuit, I sat down and turned that problem over and over through my head until I found an elegant way to visualize and understand the reason behind the math. Since it’s an approach I wish I’d thought of six hours ago, I want to share it.

First off, let’s assume everyone knows what a linked list is. I’m talking about your standard, garden-variety singly linked list: it has a head pointer but no tail pointer, made up of nodes that contain a pointer to the next node in the list (except for the last node, which points to null).

Drawing1

A linked list with a cycle in it has one or more nodes that point to a previous node in the list. If you traverse the node starting from the head, you’ll get caught in the cycle loop.

Drawing2

Did you ever play Super Mario Bros. 1? On the Level 8 and 9 dungeons, if you didn’t go the right path, you would cycle backwards until you did. It’s sort of like that.

The Floyd Cycle Detection Algorithm works by using two pointers, one slow and one fast. We’ll call them the tortoise and the hare, respectively. They start at the first node.

Drawing3

The hare travels 2 nodes per move, and the tortoise travels 1 node per move.

Drawing4

Drawing5

Drawing5a

And so on. If the hare pointer meets the tortoise pointer, you’ve got yourself a cycle:

Drawing5c

To visualize why this works, let’s go back to our Mario analogy. Imagine you could play a co-op two-player mode of those cycle-containing dungeons. If Luigi always moved slower than Mario, and Mario keeps hitting the cycle part of the dungeon, Mario will at some point pass Luigi.

But why do we choose to go 2 nodes per move? Couldn’t you go 3 nodes per move? Well, yes, you could, but it’s not important how fast the hare goes. The hare could go light speed for all we care, but it can only pass the tortoise once the tortoise reaches the cycle.

There are some interesting properties about this algorithm:

  • The hare is always twice as many steps ahead of the tortoise (if an interviewer asks you how to find the middle of a linked list, have the hare run off the end of your list and the tortoise will be at exactly the middle)
  • The hare can never “skip” over the tortoise without them first sharing the same node. It seems like it might because it moves in chunks of two, but remember that for each step, the hare only gains one node on the tortoise.

Now that we can detect cycles, the next step is figuring out where the cycle starts and how to fix the cycle. This is where it gets tricky.

All of the Stack Overflow answers talk about the tortoise being Xi, the hare being X2i, and lambda (the length of the cycle) and mu (the number of steps to get to the cycle).

Let’s toss that all aside and agree upon this: the hare has always taken twice as many steps as the tortoise, right? Right.

So the tortoise and the hare meet at a particular node for the first time. The tortoise has entered the cycle but hasn’t done a full loop. The hare, depending on the size of the list and the cycle, may have done the loop only once, or it could have done the loop a million times. However, no matter how many times the poor hare has been spun through the cycle, we can guarantee that it has traveled twice as many steps as the tortoise has.

Drawing6

Again, that’s very important. It means that at that meeting point node, if the tortoise has taken i steps, and if the tortoise takes another i steps (i + i = 2i), it will end up at that same node. If it’s a big loop, it’ll only have to loop once, but if it’s a tight loop, it might go through it a lot of times, just like the hare had to do. But no matter what, we can guarantee that it’ll end up on the meeting node after i steps.

So here’s the heart and soul of Floyd’s Cycle Detection Algorithm: if we cloned the tortoise and placed one at the head of the list and one at the meeting point node, if we had them take i steps, we would guarantee that they would reach the meeting point node at the same time. Why? Because the cloned tortoise starts at position i and takes i steps, which makes a total distance of 2i.

But think about it: they wouldn’t just meet at the meeting point node, they would meet for all of the nodes at the beginning of the cycle until they reached the meeting point node. In fact, it means that the very first node that they meet is the very first node of the cycle.

Once we know the first node of the cycle, fixing the cycle is trivial: plop down a pointer to this first node, and use another pointer to traverse the rest of the cycle until you reach the node who points at the first node.

Eating as a metaphor for productivity

I’ve been thinking about diet as a metaphor for the things I do every day. There are good and bad things I can eat, the same way that there are productive tasks that nourish my life as well as unproductive or even harmful things that diminish me.

Lean meats and vegetables are equivalent to work, study, organization, errands. Fruits might be enjoying the company of friends and loved ones, or working on a fun hobby. Watching TV might be a nice rack of BBQ ribs, and sitting on the couch playing video games like a zombie would be akin to stuffing doughnut after doughnut down your gullet.

Lately, I’ve noticed that keeping a steady, monotonous diet of one or two foods will kill my appetite. I eat less overall. This matches pretty closely with a study that shows a correlation between increased variety of foods and greater food consumption.

It seems to be the same with my daily tasks. If I spent all day watching TV (which I wouldn’t), I’d feel sick in the same way I’d feel after cleaning out a bucket of ice cream. If I worked and studied all day, I’d feel healthy and proud of myself the same way I would if I’d eaten lean meats and fibrous vegetables, but I’d also be dreaming about that bucket of ice cream.

The problem is that too much of one thing will kill my appetite for that thing. That’s not a problem with ice cream, since I don’t want to overeat empty calories or watch TV all day. However, if I want to be very productive at one thing (e.g. convert ColorMyWorld to iOS 7), eventually I get fatigued of the lack of variety, which isn’t too dissimilar from eating grilled chicken breast day-in, day-out.

I think the best productivity hack to keeping a healthy diet is to keep a wide variety of foods so that you don’t get tired or bored of any one meal. Different proteins, different preparations, different sauces, different vegetables. There’s room for fruit, of course; that’s important. There’s also room for occasional indulgences, if only to give yourself a mental break and not feel deprived. But if you want to eat healthy foods consistently, you can’t let yourself get bored, frustrated, or tired of healthy foods.

I’m feeling the same way about work and productivity. Doing one task for eight hours will fatigue anyone. I’ve found that switching between different productive tasks is a great way to keep productivity up while combating monotony. It’s important that I don’t get sick of ColorMyWorld, so I might switch to interview questions or learn about Auto Layout or watch Coursera lectures.

A mindset for progress

I’m learning the value of plugging away on a task without judgment instead of obsessing about progression.

Progression isn’t linear. Some problems remain shrouded in a thick fog until you put in the time and work, and suddenly the fog is lifted and you break through to a new level of understanding.

If you’re worried about your progress or lack thereof, you won’t have the patience to wait for the breakthrough.

This Coursera class on Algorithms that I’m taking is a good example. It’s a tough version of a basic course on algorithms and data structures, and not so different from the one I took at UCI a decade ago except that the video game difficulty setting has been jacked up a few notches. A lot of the exercise problems I’m facing are novel in presentation and concept.

Thankfully, I’m armed with the best that Adam Robinson, Toni Krasnic, and the XMind mind mapping software have to offer, and putting in the effort is easier when there’s a framework that you can put your faith into. Yes, I have faith in these systems, and these systems have empowered me to take control of my own education.

Instead of forcing myself to memorize how to use a union-find data structure, I ask myself a series of questions. What is this data structure trying to solve? What’s the naive approach? What are some optimizations? How might I use this in other situations? On and on, I ask myself better questions and am rewarded with better answers. I map these concepts, stare at them, ask more questions, draw relationships, and constantly edit and reorganize until they make sense. I flex those muscles with exercises, and reinforce them after some time has passed.

It works, oh miracle of miracles, it does. I wish I’d known earlier that learning is about asking good questions, wanting good answers, and having the mindfulness and patience to enjoy the ride. Still, I’m thankful that I know now what I couldn’t before.

These days I don’t experience much dread when I run into an obstacle, I experience bemusement. “How will I get past this,” I wonder. And off I go.

Circling back on iOS

Having completed the fairly comprehensive iOS online course offered by Stanford on iTunes U, and having completed ColorMyWorld as my “final project”, it’s time to circle back on some important topics that I haven’t covered yet or only skimmed the first time around:

  • Unit testing
  • Memory management that’s not ARC (i.e. pre-iOS 5)
  • Reading the Apple Human Interface Guidelines
  • Fully understanding the app submission process: certificates, provisioning profiles, etc.

There’s so much more I want to learn, though:

  • Core Graphics (Quartz)
  • Core Animation

But then even apart from iOS, there’s a desire to explore other topics: web, deeper CS theory and mathematics, etc. Too many paths, not enough time and energy to explore them all.