Ruby & (Ampersand) Parameter Demystified

Idea

Recently I was asked a question about ‘& parameters’ when you define and/or call methods which take a block e.g.:

def blah(&block)
  yadda(block)
end

def yadda(block)
  foo(&block)
end

def foo(&block)
  block.call
end

blah do
  puts "hello"
end

As you pass this parameter around, sometimes the ampersand appears in front of it, but other times it doesn’t, seemingly with no rhyme of reason. As we dig into crazy metaprogramming or write various libraries, it is often hard to remember how confusing Ruby can be when you’re starting out. So, let’s dig into this a little more deeply and shed some light on what’s going on.

The Implicit Block

Methods in Ruby can take arguments in all sorts of interesting ways. One case that’s especially interesting is when a Ruby method takes a block.

In fact, all Ruby methods can implicitly take a block, without needing to specify this in the parameter list or having to use the block within the method body e.g.:

def hello
end

hello do
  puts "hello"
end

This will execute without any trouble but nothing will be printed out as we’re not executing the block that we’re passing in. We can – of course – easily execute the block by yielding to it:

def hello
  yield if block_given?
end

hello do
  puts "hello"
end

This time we get some output:

hello

We yielded to the block inside the method, but the fact that the method takes a block is still implicit.

It gets even more interesting since Ruby allows to pass any object to a method and have the method attempt to use this object as its block. If we put an ampersand in front of the last parameter to a method, Ruby will try to treat this parameter as the method’s block. If the parameter is already a Proc object, Ruby will simply associate it with the method as its block.

def hello
  yield if block_given?
end

blah = -> {puts "lambda"}

hello(&blah)
lambda

If the parameter is not a Proc, Ruby will try to convert it into one (by calling to_proc on it) before associating it with the method as its block.

def hello
  yield if block_given?
end

class FooBar
  def to_proc
    -> {puts 'converted lambda'}
  end
end

hello(&FooBar.new)
converted lambda

All of this seems pretty clear, but what if I want to take a block that was associated with a method and pass it to another method? We need a way to refer to our block.

The Explicit Block

When we write our method definition, we can explicitly state that we expect this method to possibly take a block. Confusingly, Ruby uses the ampersand for this as well:

def hello(&block)
  yield if block_given?
end

hello do
  puts "hello"
end

Defining our method this way, gives us a name by which we can refer to our block within the method body. And since our block is a Proc object, instead of yielding to it, we can call it:

def hello(&block)
  block.call if block_given?
end

hello do
  puts "hello"
end

I prefer block.call instead of yield, it makes things clearer. Of course, when we define our method we don’t have to use the name ‘block’, we can do:

def hello(&foo)
  foo.call if block_given?
end

hello do
  puts "hello"
end

Having said that; ‘block’ is a good convention.

So, in the context of methods and blocks, there are two ways we use the ampersand:

  • in the context of a method definition, putting an ampersand in front of the last parameter indicates that a method may take a block and gives us a name to refer to this block within the method body
  • in the context of a method call, putting an ampersand in front of the last argument tells Ruby to convert this argument to a Proc if necessary and then use the object as the method’s block

Passing Two Blocks To A Method

It is instructive to see what happens when you try to pass a both a regular block and a block argument to a method:

def hello(&block)
  block.call if block_given?
end

blah = -> {puts "lambda"}

hello(&blah) do
  puts "hello"
end

You get the following error message:

code.rb:56: both block arg and actual block given

It is not even an exception – it’s a syntax error!

Using Another Method As A Block

It’s also interesting to note that since you can easily get a reference to a method in ruby and the Method object implements to_proc, you can easily give one method as a block to another e.g.:

def hello(&block)
  block.call if block_given?
end

def world
  puts "world"
end

method_reference = method(:world)

hello(&method_reference)
world

Passing The Block Around

We now know enough to easily understand our first example:

def blah(&block)
  yadda(block)
end

def yadda(block)
  foo(&block)
end

def foo(&block)
  block.call
end

blah do
  puts "hello"
end
  • we define blah to expect a block, inside blah we can refer to this block as block
  • we define yadda to expect one parameter, this parameter would be referred to as block inside yadda, but it is not a block in that we could not yield to it inside yadda
  • foo also expects a block and we can refer to this block as block inside foo
  • when we call yadda from within blah we pass it our block variable without the ampersand, since yadda does not a expect a block parameter, but simply a regular method argument, in our case this regular method argument will just happen to be a Proc object
  • when we call foo from inside yadda we pass it our block variable, but this time with an ampersand since foo actually expects a block and we want to give it a block rather than just a regular variable

It should now be much more obvious why the ampersand is used in some cases, but not in others.

The Symbol To Proc Trick

We should now also have a lot less trouble understanding the ‘symbol to proc’ trick. You’ve no doubt seen code like this:

p ["a", "b"].map(&:upcase)

We know that this is equivalent to:

p ["a", "b"].map{|string| string.upcase}

But now we also make an educated guess as to why they are equivalent. We have a Symbol object (‘:upcase’), we put an ampersand in front of it and pass it to the map method. The map method takes a block, and by using the ampersand we’ve told Ruby that we want to convert our Symbol object to a Proc and associate it with the map method as its block. It turns out that Symbol implements to_proc in a special way, so that the resulting block becomes functionally equivalent to our second example above. Of course these days Ruby implements Symbol#to_proc using C, so it’s not quite as nice looking as the examples you’ll find around the web, but you get general idea.

Anyway, hopefully this makes blocks and ampersands a bit more friendly. It’s definitely worth it to occasionally revisit the basics, I’ll try to do it more often in the future.

Image by Martin Whitmore

Ruby – Why U No Have Nested Exceptions?

Why U No

One of the things we almost always do these days when we write our libraries and apps, is use other libraries. Inevitably something will go wrong with those libraries and exceptions will be produced. Sometimes these are expected (e.g. an HTTP client that produces an exception when you encounter a 500 response or a connection timeout), sometimes they are unexpected. Either way you don’t want to allow the exceptions from these external libraries to bubble up through your code and potentially crash your application or cause other weirdness. Especially considering that many of these exceptions will be custom types from the libraries you’re using. No-one wants strange exceptions percolating through their code.

What you want to do, is ensure that all interactions with these external libraries are wrapped in a begin..rescue..end. You catch all external errors and can now decide how to handle them. You can throw your hands up in the air and just re-raise the same error:

begin
  SomeExternalLibrary.do_stuff
rescue => e
  raise
end

This doesn’t really win us anything. Better yet you would raise one of your own custom error types.

begin
  SomeExternalLibrary.do_stuff
rescue => e
  raise MyNamespace::MyError.new
end

This way you know that once you’re past your interfaces with the external libraries you can only encounter exception types that you know about.

The Need For Nested Exceptions

The problem is that by raising a custom error, we lose all the information that was contained in the original error that we rescued. This information would have potentially been of great value to help us diagnose/debug the problem (that caused the error in the first place), but it is lost with no way to get it back. In this regard it would have been better to re-raise the original error. What we want is to have the best of both worlds, raise a custom exception type, but retain the information from the original exception.

When writing escort one of the things I wanted was informative errors and stack traces. I wanted to raise errors and add information (by rescuing and re-raising) as they percolated through the code, to be handled in one place. What I needed was the ability to nest exceptions within other exceptions.

Ruby doesn’t allow us to nest exceptions. However, I remembered Avdi Grimm mentioning the nestegg gem in his excellent Exceptional Ruby book, so I decided to give it a try.

The Problems With Nestegg

Egg

Unfortunately nestegg is a bit old and a little buggy:

  • It would sometimes lose the error messages
  • Nesting more than one level deep would cause repetition in the stacktrace

I also didn’t like how it made the stack trace look non-standard when including the information from the nested errors. If we take some code similar to the following:

require 'nestegg'

class MyError < StandardError
  include Nestegg::NestingException
end

begin
  1/0
rescue => e
  begin
    raise MyError.new("Number errors will be caught", e)
  rescue => e
    begin
      raise MyError.new("Don't need to let MyError bubble up")
    rescue => e
      raise MyError.new("Last one for sure!")
    end
  end
end

It would produce a stack trace like this:

examples/test1.rb:26:in `rescue in rescue in rescue in <main>': MyError (MyError)
	from examples/test1.rb:23:in `rescue in rescue in <main>'
	from examples/test1.rb:20:in `rescue in <main>'
	from examples/test1.rb:17:in `<main>'
	from cause: MyError: MyError
	from examples/test1.rb:24:in `rescue in rescue in <main>'
	from examples/test1.rb:20:in `rescue in <main>'
	from examples/test1.rb:17:in `<main>'
	from cause: MyError: MyError
	from examples/test1.rb:21:in `rescue in <main>'
	from examples/test1.rb:17:in `<main>'
	from cause: ZeroDivisionError: divided by 0
	from examples/test1.rb:18:in `/'
	from examples/test1.rb:18:in `<main>'

After looking around I found loganb-nestegg. This fixed some of the bugs, but still had the non-standard stack trace and the repetition issue.

When you’re forced to look for the 3rd library to solve a problem, it’s time to write your own.

This is exactly what I did for escort. This functionality eventually got extracted into a gem which is how we got nesty. Its stack traces look a lot like regular ones, it doesn’t lose messages and you can nest exceptions as deep as you like without ugly repetition in the stack trace. If we take the same code as above, but redefine the error to use nesty:

class MyError < StandardError
  include Nesty::NestedError
end

Our stack trace will now be:

examples/complex.rb:20:in `rescue in rescue in rescue in <main>': Last one for sure! (MyError)
	from examples/complex.rb:17:in `rescue in rescue in <main>'
	from examples/complex.rb:18:in `rescue in rescue in <main>': Don't need to let MyError bubble up
	from examples/complex.rb:14:in `rescue in <main>'
	from examples/complex.rb:15:in `rescue in <main>': Number errors will be caught
	from examples/complex.rb:11:in `<main>'
	from examples/complex.rb:12:in `/': divided by 0
	from examples/complex.rb:12:in `<main>'

Definitely nicer. We simply add the messages for every nested error to the stack trace in the appropriate place (rather than giving them their own line).

How Nested Exceptions Work

The code for nesty is tiny, but there are a couple of interesting bits in it worth looking at.

One of the special variables in Ruby is $! which always contains the last exception that was raised. This way when we raise a nesty error type, we don’t have to supply the nested error as a parameter, it will just be looked up in $!.

Ruby always allows you to set a custom backtrace on any error. So, if you rescue an error you can always replace its stack trace with whatever you want e.g.:

begin
  1/0
rescue => e
  e.message = "foobar"
  e.set_backtrace(['hello', 'world'])
  raise e
end

This produces:

hello: divided by 0 (ZeroDivisionError)
	from world

We take advantage of this and override the set_backtrace method to take into account the stack trace of the nested error.

def set_backtrace(backtrace)
  @raw_backtrace = backtrace
  if nested
    backtrace = backtrace - nested_raw_backtrace
    backtrace += ["#{nested.backtrace.first}: #{nested.message}"]
    backtrace += nested.backtrace[1..-1] || []
  end
  super(backtrace)
end

To produce the augmented stack trace we note that the stack trace of the nested error should always be mostly a subset of the enclosing error. So, we whittle down the enclosing stack trace by taking the difference between it and the nested stack trace (I think set operations are really undervalued in Ruby, maybe a good subject for a future post). We then augment the nested stack trace with the error message and concatenate it with what was left over from the enclosing stack trace.

Anyway, if you don’t want exceptions from other libraries invading your app, but still want the ability to diagnose the cause of the exceptions easily – nested exceptions might be the way to go. And if you do decide that nested exceptions are a good fit, nesty is there for you.

Image by Samuel M. Livingston

The Best Way To Pretty Print JSON On The Command-Line

Print

Developers tend to work with APIs a lot and these days most of these APIs are JSON. These JSON strings aren’t exactly easy to read unless they are formatted well. There are many services online that can pretty print JSON for you, but that’s annoying. I love the command-line and whenever I am playing with new APIs or writing my own I mostly use CURL which means I need a good way to pretty print my JSON on the command-line. It should be simple, quick, easy to remember, easy to install – we’re not trying to solve complex algorithms, just format some JSON.

The ‘Good’ Old Faithful

One way that is always available is the Python JSON tool. So you can always do this:

echo '{"b":2, "a":1}' | python -mjson.tool

Which will give you:

{
    "a": 1,
    "b": 2
}

This is alright and, as I said, it is always available. However note that it has sorted our keys which is a major disadvantage. It is also a bit of a handful to write when you just want to pretty print some JSON. I only ever use this when I am on an unfamiliar computer and there is nothing better.

YAJL Tools

If you’re not using YAJL you should be. It is a small JSON library written in C. The parser is event driven and super fast. In the Ruby world we have a nice set of bindings and there are bindings for other languages as well. It is my go-to JSON library.

YAJL also cames with a couple of tools, json_reformat and json_verify. These are pretty self-explanatory and you can get your hands on them like this:

brew install yajl

or

sudo apt-get install yajl-tools

After that all you have to do is:

echo '{"b":2, "a":1}' | json_reformat

Which will give you:

{
    "b": 2,
    "a": 1
}

This is pretty nice. My one tiny niggle is that json_reformat is still a bit of a mouthful, but if you just want basic JSON formatting, it’s a good solution.

Ppjson

Of course being developers, we don’t have to put up with even minor niggles since we can build ourselves exactly the tools we need (and a little bit extra to boot). I was writing a command-line framework and I just happened to need a command-line tool, which is how I ended up with ppjson. I use Ruby quite a bit, so it is a Ruby tool and even if I do say so myself, it’s pretty nice.

You just need to:

gem install ppjson

This will let you do:

echo '{"b":2, "a":1}' | ppjson

Which will give you:

{
  "b": 2,
  "a": 1
}

It uses YAJL through multi_json under the hood, so you still get the speed of YAJL, but it can also do a few extra things for you.

You can pass or pipe it some JSON and it will pretty print it to standard output for you. But you can also pass it a file name with some JSON in it and it will pretty print the contents of the file for you:

ppjson -f abc123.json

You can also store the pretty printed contents back into the file:

ppjson -fi abc123.json

Sometimes you have saved some pretty printed JSON in a file, but now you want to use it as a body of a CURL POST request, for example. Well ppjson can uglify your JSON for you as well:

ppjson -fu abc123.json

This will output a minified JSON string to standard output. And of course you can also update the original file with the uglified JSON as well:

ppjson -fui abc123.json

It will do you basic JSON pretty printing with an easy to remember executable name, but it also has a few nice convenience features to make your life that little bit easier.

The best part is that using Escort, it was a breeze to write. I’ll talk about some of the other interesting projects that ‘fell out’ of Escort some other time.

Anyway, now you no longer need to remember that IDE or editor shortcut to format your JSON or look for an online tool to do the same, the command-line has you more than covered.

Image by NS Newsflash

I Was Nominated To Speak At LoneStarRuby Conference 2013

A few days ago I woke up to see this in my Twitter stream:

Looking at the list of nominated speakers, I am in extremely illustrious company which was just amazing to see. Of course I replied with my appreciation. Then a little later I saw this:

Which was also very nice.

Who would have thought something like this would ever happen – thanks @IndianGuru.

Anyway, if LoneStarRuby Conference 2013 is of any interest to you and you’d like to make me write a talk hear me speak, you can go and vote.

A Closure Is Not Always A Closure In Ruby

SurpriseOften you don’t really think about what particular language features mean, until those features come and bite you. For me one such feature was Ruby’s instance_eval. We all know how instance_eval works, it’s pretty straight forward. We pass it a block, and that block gets executed in the context of the object on which we call instance_eval e.g.:

a = Object.new
a.instance_eval do
  def hello
    puts "hello"
  end
end
a.hello

The object a will get a hello method and the subsequent a.hello call will succeed. So what’s the gotcha?

The one overwhelming use of instance_eval is for creating configuration DSLs. I won’t go into that right now – it deserves a post of its own. Suffice to say that when used for this purpose, the closure semantics of the block that you pass to instance_eval don’t matter, i.e. you don’t tend to use the variables (or call methods) from the scope where the block was created. If you do need to use the variables or methods from the scope where the block was created, you might be in for a rude surprise.

What It Means To Evaluate A Block In A Different Context

Let’s create a class with a method that takes a block and call that method from within another class:

class A
  def method1(&block)
    block.call
  end
end
 
class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    @a.method1 do
      p local1
      p @instance_var1
      p helper1
    end
  end
 
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

As expected we get:

"local1"
"instance_var1"
"helper1"

What happens is that when we create the block inside method2, there is a binding that goes along with it. Inside the binding there is a self object which is our instance b of the B class. When we execute the block inside method1, it is executed within the context of this self and so our local variable, instance variable and helper method are all in scope (just as you would expect from a closure) and everything works fine. Let’s modify method1 slightly to get the self from the binding:

class A
  def method1(&block)
    puts block.binding.eval("self").object_id
    block.call
  end
end
 
b = B.new
p b.object_id
b.method2

We get:

70229187307420
70229187307420
"local1"
"instance_var1"
"helper1"

So both b and the self inside the binding are the same object as we expected.

But, what happens if instead of calling method1 with a block on @a we instance_eval the same block within the context of @a.

class A
end
 
class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    @a.instance_eval do
      p local1
      p @instance_var1
      p helper1
    end
  end
 
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

We get:

"local1"
nil
code2.rb:19:in `block in method2': undefined local variable or method `helper1' for #<A:0x007f966292d308> (NameError)

This time local1 is fine, the instance variable is nil and trying to call the method raises an error. This is unexpected, the block should be a closure, but only the local variables were closed over, everything else fell apart. This is not a new issue, but it is important to understand what is happening and why.

When we call instance_eval on an object, the self within the block is set to be the object on which we called instance_eval (Yahuda has more detail and there is even more detail here). So, even though we still manage to capture the locals from the previous scope, the methods (like helper1) are no longer in scope within our new self and the instance variables will be equal to nil since we haven’t initialized them in this new scope (unless you happen to have an instance variable with the same name in which case it will shadow the one from the scope in which the block was defined – which is probably not what you want).

So, even though we know that blocks in Ruby are closures, there is an exception to every rule.

How To Overcome The Limitations

So what can we do if we want access to the instance variables and helper method from the scope where the block was defined. Well, for instance variables, one way around would be to pass them in as parameters to the instance_eval block, that way they could be treated as locals. Unfortunately instance_eval doesn’t take parameters. Luckily some time around Ruby 1.8.7 instance_exec was introduced. Since instance_eval is so much more popular we sometimes forget that instance_exec is even there, it essentially does the same thing as instance_eval, but you can pass some arguments to the block.

class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    @a.instance_exec(@instance_var1) do |instance_var1|
      p local1
      p instance_var1
      p helper1
    end
  end
 
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

We get:

"local1"
"instance_var1"
code2.rb:15:in `block in method2': undefined local variable or method `helper1' for #<A:0x007fea7912d3e0> (NameError)

This time our instance variable is fine since we’ve turned it into an argument, but we still can’t call the method. Still not nice, but instance_exec is obviously somewhat more useful than instance_eval. We will come back to handling method calls shortly, but first a bit of history.

So What Did They Do Before instance_exec Existed

Old

This issue has been around for ages, but instance_exec has only been around for a few years, so what did they do before that, when they wanted to pass parameters to instnace_eval?

When I decided to write Escort, I chose Trollop as the option parser. It is while reading the Trollop source that I accidentally stumbled upon the answer to the above question. The author of Trollop attributes it to _why. It’s called the cloaker and we use it as a replacement for instance_eval. Here is how it works:

class A
  def cloaker(&b)
    (class << self; self; end).class_eval do
      define_method :cloaker_, &b
      meth = instance_method :cloaker_
      remove_method :cloaker_
      meth
    end
  end
end
 
class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    @a.cloaker do |instance_var1|
      p local1
      p instance_var1
      p helper1
    end.bind(@a).call(@instance_var1)
  end
 
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

We get:

"local1"
"instance_var1"
code2.rb:24:in `block in method2': undefined local variable or method `helper1' for #<A:0x007fb963064900> (NameError)

It is somewhat more awkward to use, but the output is identical to that of instance_exec. So why does this work?

We define a method on the metaclass of A using our block as the body, we then remove it and return the UnboundMethod. We then bind the unbound method to our target object and call the method.

In order for the bind to work, the relationship between the object to which we are binding and the object on which the UnboundMethod was originally defined must be a kind_of? == true. Curiously an instance of the class A is a kind_of? metaclass of A which is why everything works.

The Many Faces Of Cloaker

Why did we have to define our UnboundMethod on the metaclass of A? Well there doesn’t seem to be any good reason really. A cloaker like this will work just fine.

class A
  def cloaker(&b)
    self.class.instance_eval do
      define_method :cloaker_, &b
      meth = instance_method :cloaker_
      remove_method :cloaker_
      meth
    end
  end
end

So will this one:

class A
  def cloaker(&b)
    self.class.class_eval do
      define_method :cloaker_, &b
      meth = instance_method :cloaker_
      remove_method :cloaker_
      meth
    end
  end
end

The kind_of? relationship will hold in both cases so everything will hang together.

Did we really need to go through all that history, we just want to call helper methods from within the scope where our block is defined?

What To Do About Method Calls

Let’s have a look at how we can get our helper methods back. One obvious way is to assign self to a local and then use this local to call our helper methods from within the instance_exec block.

class A
end
 
class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    local_self = self
    @a.instance_exec(@instance_var1) do |instance_var1|
      p local1
      p instance_var1
      p local_self.helper1
    end
  end
 
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

We get:

"local1"
"instance_var1"
"helper1"

Everything works, but it is ugly and if you want to call a private helper method, you’re out of luck again since a private method can’t have an explicit receiver. This is where our cloaker comes into its own again. Using a cloaker and a bit of method_missing magic we can create our own version of instance_exec that has all the semantics we’ve come to expect from a closure, but will still execute the block within the context of the object on which it is called. We can also abstract away the ugly bind stuff while we’re at it.

class A
  def cloaker(*args, &b)
    meth = self.class.class_eval do
      define_method :cloaker_, &b
      meth = instance_method :cloaker_
      remove_method :cloaker_
      meth
    end
    with_previous_context(b.binding) {meth.bind(self).call(*args)}
  end
 
  def with_previous_context(binding, &block)
    @previous_context = binding.eval('self')
    result = block.call
    @previous_context = nil
    result
  end
 
  def method_missing(method, *args, &block)
    if @previous_context
      @previous_context.send(method, *args, &block)
    end
  end
end
 
class B
  def initialize
    @instance_var1 = "instance_var1"
    @a = A.new
  end
 
  def method2
    local1 = "local1"
    @a.cloaker(@instance_var1) do |instance_var1|
      p local1
      p instance_var1
      p helper1
    end
  end
 
  private
  def helper1
    "helper1"
  end
end
 
b = B.new
b.method2

Despite the fact that helper1 was private, we get:

"local1"
"instance_var1"
"helper1"

Essentially when we execute the block within the context of on object; we retain (in an instance variable) the self from the context where the block was defined (we get this self from the biding of the block). When a method is called within the block and it is not defined within the current context – method_missing will be called as per usual Ruby semantics. We hook into method_missing and send the method call to the self that we have retained from when the block was defined. This will call our method or fail if it was a genuine error.

Despite the fact that Ruby can surprise you with non-closure blocks, you can have your cake and eat it too, if you’re willing to do just a bit of work and give some new legs to an old trick while you’re at it.

Images by Jenn and Tony Bot and TarynMarie

What Is A Startup (Or A Startup Idea)?

Pirate

Is a startup all about the idea? Is it a bunch of people hacking together? It is not quite a company in the traditional sense of the word (at least not yet). I like to think of a startup as a series of assumptions. Your startup idea is just one assumption or alternatively there are many assumptions inherent in your idea. Let's take a simple one we're all familiar with:

"People want to connect with their friends online"

The main assumption is that people actually DO want to connect with their friends online (of course we know now that they do, but a few years ago it wasn't so obvious). Some of the inherent assumptions might be:

  • People want to know what their friends are doing right now
  • People want to see interesting links from their friends
  • We have a way to acquire users in the initial stages
  • People will want to let their friends know about our service
  • People will want to pay for our service
  • etc.

Your startup is really just a means to validate all those assumptions. If you can do it, then you may pronounce your startup a success (it's not necessarily a success yet, but the rest is really just optimisation), if you can't then it is a failure. Of course things are a bit more complex than that. 

If you follow the Lean Startup movement at all, you're probably aware of pirate metrics (the pirate says 'AARRR'). We have Acquisition, Activation, Retention, Referral, Revenue. The thing about those metrics is that they are a funnel and they are all about users. We start with lots of users in the Acquisition stage and we end up with less users in the Revenue stage. 

AARRR

All the assumptions inherent in your idea are a funnel too (think of them as a more specific version of the pirate funnel) – you start with a bunch of potential users at the top and validating each of the assumptions will whittle away some of those users. Let's take this simplified example:

Assumption funnel

The more people you can get through that funnel successfully the more sure you can be that you're onto a good thing, but if you end up with zero users before you get to the end of your funnel then you have a problem. If no-one wants to click the red button, then people are unlikely to ever tell their friends or upgrade their accounts. Your assumption is flawed and you need to adjust. Perhaps it's as simple as making the button green, or you may have to think of a way to achieve the same result without a button, or there might be a fundamental flaw in the model, in which case you might need to go back to square one, or pivot, or abandon the idea all together. 

Of course your assumption funnel is not strict, you can work on any assumption at any time, but you need to be fully aware of what you're doing. Firstly, it is easier to test the assumptions at the top of the funnel. You can figure out whether or not you can drive some initial traffic with nothing more than a dummy landing page, but to test retention you need to have built something. Secondly, there is 'Danger, Will Robinson!' every time you work on one of the assumptions lower down in the funnel first. You may optimise your big red button with 3 of your mates (the only users you have), but if you can never get anyone to come to the site at all, what's the use? It can still all work out, especially if you're flush with money and have all the time in the world, but it's probably faster and easier to prove those assumptions in order. 

Incidentally this is very similar to the problem we ran into with CrowdHired forcing us to essentially rebuild the site (in a much slimmed down fashion) and to try and bootstrap (userbase-wise) from the YOW! developer conference. Since we're not flush with time and money it was a costly lesson, but one well learned.  

The relevant concept is this, even without building anything you can easily figure out the key actions you and your potential users will have to take in order for your idea to work. You can then come up with a set of assumptions relating to each of those actions and arrange them into a funnel. You can then build the minimal amount of stuff to try and prove each assumption in turn. As you follow this process it can potentially give you some guidance regarding a number of things, such as user behaviour, where to take your idea next, when to pivot, when to get some more funding (e.g. the only way to prove this next assumption is with 10 people working for a year :)) etc. 

It goes without saying that depending on the type of startup your trying to build (network effect, B2B, B2C, etc. – see what I did there, heh), the mechanics will need adjustment. It also goes without saying that you need to validate all assumptions properly, asking 2 of your friends if they would click a button you just drew on a napkin is not an indicator of anything. In-fact this is one of the things I'd like to explore further, but I guess I'll leave it until next time.

Image by spaceninja

Why Developers Never Use State Machines

A few months ago I saw a great little blog post about state machines on the Shopify blog. The message was that state machines are great and developers should use them more – given my recent experiences with state machines at CrowdHired, I could certainly agree with that. But it got me thinking, how many times in my developer career have I actually used a state machine (either separate library or even hand-rolled abstraction)? The answer is zero times – which surprised the hell out of me since state machines really are very useful. So I decided to engage in a bit of introspection and figure out why we tend to manage our "state" and "status" fields in an ad-hoc fashion rather than doing what is clearly called for.

We Don't Need One Until We Do

The problem is that you almost never create an object fully formed with all the behaviour it is ever going to need, rather you build it up over time. The same is true for the "states" that a state machine candidate object can be in. So, early on you don't feel like your objects' state machine behaviour is complex enough to warrant a "full-blown" state machine (YAGNI and all that jazz), but later on – when it IS complex enough – you feel like you've invested too much time/effort to replace it with something that has equivalent functionality. It's a bit of a catch-22. It's overkill and by the time it's not, it's too late.

A State Machine Is A Fluffy Bunny (Not Particularly Threatening)

Bunny

Those of us who went through computer science degrees remember state machines from our computing theory subjects and the memories are often not fond ones. There are complex diagrams and math notation, determinism and non-determinism, Moore and Mealy, as well as acronyms galore (DFA, NFA, GNFA etc.). We come to believe that state machines are more complex than they actually are and it is therefore nothing but pragmatism that makes us consider a "full-blown" state machine overkill.

But most state machines you're likely to need in your day-to-day development have nothing in common with their computing theory counterparts (except the … errr … theory). You have states which are strings, and events which are methods that cause transitions from one state to another – that's pretty much it (at least for the state_machine gem in Ruby). The point is, even if you have two states, a state machine is not overkill, it might be easier that rolling an ad-hoc solution, as long as you have a good library to lean on.

Even A Good Tool Is Not A Good Tool

I would hazard a guess that there are decent state machine libraries for most languages that you can use (the aforementioned state_machine for Ruby is just one example). But even a fluffy bunny has a learning curve (I am stretching the metaphor well past breaking point here). That wouldn't be such an issue if you were solving a problem, but all you're likely doing is replacing an existing solution. Since we tend to turn to a state machine library after the fact (our ad-hoc solution is working right now). Just like with everything that has "potential future benefits" the immediate value is very hard to justify even to yourself (unless you've had experience with it before). The slight learning curve only tips the scale further towards the "we can live without it" side. It doesn't matter how good a tool is if you never give it a chance.

It is really difficult to appreciate (until you've gone through it) – how much better life can be if you do give a good state machine library a chance. When we finally "bit the bullet" at CrowdHired and rejigged some of our core objects to use the state_machine gem, the difference was immediately apparent.

  • Firstly the learning curve was minor, I did spend a few hours of going through the source and documentation, but after that I had a good idea what could and couldn't be done (I might do an in-depth look at the state_machine gem at some point). 
  • The integration itself was almost painless, but moving all the code around to be inline with the new state machine was a big pain. In hindsight had we done this when our objects only had a couple of states it would have been a breeze
  • We're now able to easily introduce more states to give our users extra information as well as allow us to track things to a finer grain. Before it was YAGNI cause it was a pain, now we find that we "ai gonna need" after all, cause it's so easy.
  • Our return values from state transitions are now 100% consistent (true/false). Before we were returning objects, arrays of objects, nil, true/false depending on who was writing it and when. 
  • We're now able to keep an audit trail of our state transitions simply by dropping in state_machine-audit_trail (see that Shopify post), before it was too hard to hook it in everywhere so we had nothing.
  • We removed a bunch of code and improved our codebase – always worthy goals as far as I am concerned.

My gut-feel is that most people who read that Shopify post agreed with it in spirit, but did nothing about it (that's kinda how it was with me). We seem to shy away from state machines due to misunderstanding of their complexity and/or an inability to quantify the benefits. But, there is less complexity than you would think and more benefits than you would expect as long you don't try to retrofit a state machine after the fact. So next time you have an object that even hints at having a "status" field, just chuck a state machine in there, you'll be glad you did. I guarantee it or your money back :).

Image by tfangel

When Developers Go To Great Length To Save Typing 4 Letters

Great Lengths

Heroku is a great platform. Long before I joined and when I say long, I mean in startup terms (i.e. a few weeks before I joined :)) – the decision was made that CrowdHired would be hosted on Heroku. Shortly after I came on board, Heroku released their new Cedar stack and we quickly migrated across to that. I find it kinda amusing that we're currently in alpha, deploying to a platform that's in beta. Latest and greatest FTW. While migrating to the new stack we also settled on Thin as our web server. The Cedar stack allows you to use whatever web server you want in production and will run on Webrick by default – not ideal. Since we were going to use Thin in production it made sense that we'd also use it in development instead of Webrick.

When you're using Rails, swapping a new web server in is pretty painless. Just include the gem and then use the rails s command to launch your new server e.g

rails s thin

Pretty simple right? Well, it is, but I am very used to typing rails s to launch my server and no matter what gem you include in your project, rails s still starts Webrick (this is not entirely accurate but bare with me). Muscle memory being what it is, after typing rails s instead of rails s thin a couple of times (and only realising this a few hours later) I decided to see if I could make Thin the default for the rails s command.

Digging Into The Rails Command Line

The key thing here was to figure out how rails s actually works – only way to do that is to read some code. We know that there is a script/rails executable that lives in all our Rails project so it makes sense that this would be the entry point into figuring out rails s, but in reality it's not (or at least it’s not that simple). We don’t actually type script/rails s, we do rails s, so there must be an executable called rails within the Rails gem itself which is declared as such in rails' gemspec. This is indeed the case, it looks like this:

#!/usr/bin/env ruby
 
if File.exists?(File.join(File.expand_path('../..', __FILE__), '.git'))
  railties_path = File.expand_path('../../railties/lib', __FILE__)
  $:.unshift(railties_path)
end
require "rails/cli"

But even that is not the start of the story. Apparently, when you have an executable in a gem, rubygems will not use it as is, but will generate another executable which wraps your one. For the rails command it looks like this:

#!/usr/bin/env ruby
#
# This file was generated by RubyGems.
#
# The application 'rails' is installed as part of a gem, and
# this file is here to facilitate running it.
#
 
require 'rubygems'
 
version = ">= 0"
 
if ARGV.first =~ /^_(.*)_$/ and Gem::Version.correct? $1 then
  version = $1
  ARGV.shift
end
 
gem 'rails', version
load Gem.bin_path('rails', 'rails', version)

This is the true entry point you hit when you type rails s. Of course, all this does is load/call the original executable from the Rails gem.

The Rails source is broken up into several projects such as activerecord, activesupport etc. Probably the most important one of these is railties. This is where the rails executable takes us. Of course, before it does that it needs to put the lib/ folder of the railties project on the load path, but eventually we end up in railties/lib/rails/cli.rb. Here we almost immediately execute the following:

Rails::ScriptRailsLoader.exec_script_rails!

All this does is essentially figure out if we're inside a Rails app and if we are it executes script/rails passing through the command line arguments that you supply. So, we're now back in our Rails app; script/rails is the real entry point after all (although we're about to be taken straight back to railties). The file looks like this:

#!/usr/bin/env ruby
# This command will automatically be run when you run "rails" with Rails 3 gems installed from the root of your application.
 
APP_PATH = File.expand_path('../../config/application',  __FILE__)
require File.expand_path('../../config/boot',  __FILE__)
require 'rails/commands'

We require boot.rb so that we can hook into Bundler and make sure the relevant gems are on the load path (such as rails for example), we then jump into railties/rails/lib/commands.rb. Here everything is pretty straight forward, we have a big case statement which has a clause for "server". We instantiate a new Rails::Server and start it, which tells us very little by itself, but if we jump into railties/rails/lib/commands/server.rb we can see that Rails::Server simply extends Rack::Server (and delegates to Rack::Server's start method from its start method) all it adds is those familiar lines we're all used to seeing e.g.:

=> Booting Thin
=> Rails 3.0.7 application starting in development on http://0.0.0.0:3000
=> Call with -d to detach
=> Ctrl-C to shutdown server

So, if we want to change which server is picked up by default when we type rails s we need to go look in Rack.

A Quick Glance At Rack

Luckily we can easily grab it from Github and crack it open (you have to admire the Ruby open source ecosystem, it is truly awesome, largely due to Github, so big props to those guys). We of course need to check out lib/rack/server.rb where we find the following method:

def server
  @_server ||= Rack::Handler.get(options[:server]) || Rack::Handler.default(options)
end

So, if we don't pass in the name of the server we want, Rack::Handler.default will try to determine it for us.

def self.default(options = {})
  # Guess.
  if ENV.include?("PHP_FCGI_CHILDREN")
    # We already speak FastCGI
    options.delete :File
    options.delete :Port
 
    Rack::Handler::FastCGI
  elsif ENV.include?("REQUEST_METHOD")
    Rack::Handler::CGI
  else
    begin
      Rack::Handler::Mongrel
    rescue LoadError
      Rack::Handler::WEBrick
    end
  end
end

As you can see, it turns out that the real default server is actually Mongrel. So if you included Mongrel in your Rails project, typing rails s would automatically pick that up without you having to do anything. Only if Mongrel fails, do we fall back to Webrick which is part of Ruby and therefore is always present. So what do we do if we want Thin to be one of the defaults? Well, first thing first, we need to check if Rack includes a handler for Thin. If we look in lib/rack/handlers/ we can see that Rack itself includes the following:

cgi.rb
evented_mongrel.rb
fastcgi.rb
lsws.rb
mongrel.rb
scgi.rb
swiftiplied_mongrel.rb
thin.rb
webrick.rb

Luckily Thin is there, so what we really want is that default method to look something like this:

def self.default(options = {})
  # Guess.
  if ENV.include?("PHP_FCGI_CHILDREN")
    # We already speak FastCGI
    options.delete :File
    options.delete :Port
 
    Rack::Handler::FastCGI
  elsif ENV.include?("REQUEST_METHOD")
    Rack::Handler::CGI
  else
    begin
      Rack::Handler::Thin
    rescue LoadError
      begin
        Rack::Handler::Mongrel
      rescue LoadError
        Rack::Handler::WEBrick
      end
    end
  end
end

This way Thin will be the first default, followed by Mongrel and only then falling through to Webrick. Luckily, since we're using Ruby, we can reopen the class and replace the method with our version. I think this is a perfect example where the ability to reopen classes comes in extremely handy, without any need to worry about "scary consequences".

Getting It Working

All we really need to figure out is where to put the code that reopens the class so that it gets picked up before Rails tries to launch the server. The only logical place is the script/rails executable itself, which will now look like this:

#!/usr/bin/env ruby
# This command will automatically be run when you run "rails" with Rails 3 gems installed from the root of your application.
 
APP_PATH = File.expand_path('../../config/application',  __FILE__)
require File.expand_path('../../config/boot',  __FILE__)
require 'rack/handler'
Rack::Handler.class_eval do
  def self.default(options = {})
    # Guess.
    if ENV.include?("PHP_FCGI_CHILDREN")
      # We already speak FastCGI
      options.delete :File
      options.delete :Port
 
      Rack::Handler::FastCGI
    elsif ENV.include?("REQUEST_METHOD")
      Rack::Handler::CGI
    else
      begin
        Rack::Handler::Mongrel
      rescue LoadError
        begin
          Rack::Handler::Thin
        rescue LoadError
          Rack::Handler::WEBrick
        end
      end
    end
  end
end
require 'rails/commands'

This works without any problems, we type rails s and as long as Thin is in our Gemfile it starts up by default. As an aside, notice that I used class_eval to reopen Rack::Handler. Metaprogramming tricks like this should be part of every Ruby developer's toolbox, I'll talk more about this some other time (seeing as I am well into TL;DR land here).

Going through this exercise didn't take long (under 30 minutes) and taught me a bit more about Rails and Rack. Shortly after doing this – in a curious case of the universe working in interesting ways – I came across a Stackoverflow question asking about this exact scenario and got an inordinate amount of satisfaction from being able to easily answer it :). In-fact, even the fact that shortly after Jason found Pow and we switched over to that, doesn't really diminish the satisfaction of quickly solving a seemingly difficult problem in a neat way. The lesson here is this, no matter what problems you come across don't automatically look for a library to handle it. Do spend a few minutes investigating – it might be enough to solve it (especially if you're using Ruby) and you'll certainly learn something.

Image by Gerard Stolk presque 64

Even Boring Form Data Can Be Interesting (For A Developer)

Bored

What could be more boring than capturing credit card data on a form? Well, it's actually not that boring since you may want to encrypt this particular data, which presents it's own set of challenges. Nevertheless, it's still a textbox which takes digits that you store in a database – whoopty doo – not exactly rocket surgery. Well, I've got a piece of data that's got the credit card beat for sheer mundanity – the ABN. If you're an Australian you know all about this. For everybody else, it stands for Australian Business Number which is an 11 digit number, provided by the government to every company. It's not secret (you can look them up online), so you don't even need to encrypt it – difficult to get excited about that. Of course if that was the end of the story, this wouldn't be much of a blog post, so – as you might imagine – things are not as bland as they appear.

The Interesting Thing About A Credit Card Number…

At CrowdHired, we don't tend to deal much with credit card numbers, but ABNs are another matter entirely – since companies are one of the two types of users we have in the system (by the way – as you may have deduced – I've been working for a startup for the last few months, I should really talk about how that happened, it's an interesting story). Just like any piece of data, you want to validate the user input if you possibly can. When I started looking into this for ABNs I discovered that they had an interesting trait, it is a trait which credit card numbers share. You see, both credit cards and ABNs are self-verifying numbers.

I've been doing web development for many years now, but had no idea this was the case. So naturally – being the curious developer that I am – I had to dig a little further. It turns out that these kinds of numbers are quite common, with other well-known examples being ISBNs, UPCs and VINs. Most of these use a variation of a check digit-based algorithm for both validation and generation. Probably the most well-known of these algorithms is the Luhn algorithm which is what credit cards use. So, we'll use a credit card as an example.

Validating And Generating Credit Cards (And Every Other Check-Digit Based Number)

Let us say we have the following credit card number:

4870696871788604

It is 16 digits (Visa and MasterCard are usually 16, but Amex is 15). This number is broken down in the following way:

Issuer Number | Account Number | Check Digit
487069        | 687178860      | 4

You can read lots more about the anatomy of a credit card, but all we want to do is apply the Luhn algorithm to check if this credit card is valid. It goes something like this:

1. Starting from the back, double every second digit

  
4 | 8 | 7 | 0 | 6 | 9 | 6 | 8 | 7 | 1 | 7 | 8 | 8 | 6 | 0 | 4
8 | 8 |14 | 0 |12 | 9 |12 | 8 |14 | 1 |14 | 8 |16 | 6 |00 | 4

2. If the doubled numbers form a double digit number, add the two digits

 
4 | 8 | 7 | 0 | 6 | 9 | 6 | 8 | 7 | 1 | 7 | 8 | 8 | 6 | 0 | 4
8 | 8 |14 | 0 |12 | 9 |12 | 8 |14 | 1 |14 | 8 |16 | 6 |00 | 4
8 | 8 | 5 | 0 | 3 | 9 | 3 | 8 | 5 | 1 | 5 | 8 | 7 | 6 | 0 | 4

3. Sum up all the digits of this new number

  8+8+5+0+3+9+3+8+5+1+5+8+7+6+0+4 = 80

4. If the number is perfectly divisible by 10 it is a valid credit card number. Which in our case it is.

You can see how we can use the same algorithm to generate a valid credit card number. All we have to do is set the check digit value to X and then perform all the same steps. During the final step we simply pick our check digit in such a way as to make sure the sum of all the digits is divisible by 10. Let's do this for a slightly altered version of our previous credit card number (we simply set the digit before the check digit to 1 making the credit card number invalid).

  
4 | 8 | 7 | 0 | 6 | 9 | 6 | 8 | 7 | 1 | 7 | 8 | 8 | 6 | 1 | X
8 | 8 |14 | 0 |12 | 9 |12 | 8 |14 | 1 |14 | 8 |16 | 6 | 2 | X
8 | 8 | 5 | 0 | 3 | 9 | 3 | 8 | 5 | 1 | 5 | 8 | 7 | 6 | 2 | X
 
8+8+5+0+3+9+3+8+5+1+5+8+7+6+2+X = 78+X
X = (78%10 == 0) ? 0 : 10 - 78%10
X=2

As you can see no matter what the other 15 digits are, we'll always be able to pick a check digit between 0 and 9 that will make the credit card number valid.

Of course not every self-verifying number uses the Luhn algorithm, most don't use mod(10) to work out what the check digit should be, and for some numbers like the IBAN, the check digit actually consists of 2 digits. And yet, the most curious self-verifying number of the lot is the first one I learned about – the ABN. This is because, for the life of me, I couldn't work out what the check digit of the ABN could be.

The Curious Case Of The ABN

Curious

Australia is certainly is not averse to using check digit-based algorithms. The Australian Tax File Number (TFN) and the Australian Company Number (ACN) are just two examples, but the ABN seems to be different. At first glance the ABN validation algorithm is just more of the same, it just has a larger than normal "mod" step at the end (mod(89)).

  • Subtract 1 from the first (left) digit to give a new eleven digit number
  • Multiply each of the digits in this new number by its weighting factor
  • Sum the resulting 11 products
  • Divide the total by 89, noting the remainder
  • If the remainder is zero the number is valid

In-fact, here is some ruby code to validate an ABN which I appropriated from the Ruby ABN gem (and then rolled it into a nice Rails 3, ActiveRecord validator so we could do validates_abn_format_of in all out models :)) :

def is_integer?(number)
  Integer(number) 
  true 
rescue 
  false
end
  
def abn_valid?(number)
  raw_number = number
  number = number.to_s.tr ' ', ''
  return false unless is_integer?(number) && number.length == 11

  weights = [10, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  sum = 0
  (0..10).each do |i|
    c = number[i,1]
    digit = c.to_i - (i.zero? ? 1 : 0)
    sum += weights[i] * digit
  end

  sum % 89 == 0 ? true : false
end

But, while validating ABNs is easy, generating them is a whole other matter. As we've seen, with a check digit-based algorithm, generating the number is the same as validating the number, except we pick the digit in such a way as to make our 'mod' step evaluate to zero. But with a number such as the ABN, where there is no apparent check digit (perhaps I am just having a bout of stupid, so if you can see an obvious check digit with ABNs do let me know), how do you easily generate a valid number? In-fact, why would you want to generate these numbers in the first place, isn't being able to validate them enough?

Well, in the case of CrowdHired, we tend to create object trees that are quite deep, so we build an maintain some infrastructure code to allow us to create fake data for use during development (another interesting thing to talk about at a later date). Before we started using the self-validating properties of ABNs we simply generated any old 11 digit number as fake data for ABN fields, but once the validations started kicking in this was no longer an option. Being the pragmatic developers that we are (even if we do say so ourselves), we took some real ABNs (like our own) chucked them into an array and randomly picked from there. But, this offended the developer gods, or my developer pride – whichever, so one Saturday I decided to take a couple of hours to generate some truly random ABNs that were still valid. Here is the code I came up with (it is now a proud part of our fake data generation script):

def random_abn
  weights = [10,1,3,5,7,9,11,13,15,17,19]
  reversed_weights = weights.reverse
  initial_numbers = []
  final_numbers = []
  9.times {initial_numbers << rand(9)+1}
  initial_numbers = [rand(8)+1, rand(7)+2] + initial_numbers
  products = []
  weights.each_with_index do |weight, index|
    products << weight * initial_numbers[index]
  end
  product_sum = products.inject(0){|sum, value| sum + value}
  remainder = product_sum % 89
  if remainder == 0
    final_numbers = initial_numbers
  else
    current_remainder = remainder
    reversed_numbers = initial_numbers.reverse
    reversed_weights.each_with_index do |weight, index|
      next if weight > current_remainder
      if reversed_numbers[index] > 0
        reversed_numbers[index] -= 1
        current_remainder -= weight
        if current_remainder < reversed_weights[index+1]
          redo
        end
      end
    end
    final_numbers = reversed_numbers.reverse
  end
  final_numbers[0] += 1
  final_numbers.join
end

The idea is pretty simple. Let's go through an example to demonstrate:

1. Firstly we randomly generate 11 digits between 0 and 9 to make up our probably ABN (they are actually not all between 0 and 9 but more on that shortly)

7 5 8 9 8 7 3 4 1 5 3

2. We then perform the validation steps on that number

  • multiply the digits by their weights to get weight-digit products 

      
          7x10=70
          5x1=5
          8x3=24
          9x5=45
          8x7=56
          7x9=63
          3x11=33
          4x13=52
          1x15=15
          5x17=85
          3x19=57
        
  • sum the products 70+5+24+45+56+63+33+52+15+85+57 = 505
  • divide by 89 to get the remainder 505 mod 89 = 60

3. Since we do mod(89) at worst we'll be off by 88 (although if we get 0 as the remainder we lucked out with a valid ABN straight away), we now use the weight-digit products to "give change", subtracting from the remainder as we go until we hit zero.

We start with the last digit where the weight is 19. We subtract 1 from this digit, which means we can subtract 19 from our remainder. We then move on to the next digit until the remainder hits zero

  
Initial | Change  | Remainder
-------------------------------
7x10=70 | 7x10=70 | 0
5x1=5   | 5x1=5   | 0
8x3=24  | 8x3=24  | 0
9x5=45  | 9x5=45  | 0
8x7=56  | 8x7=56  | 0
7x9=63  | <strong>6</strong>x9=63  | 0
3x11=33 | 3x11=33 | 9
4x13=52 | 4x13=52 | 9
1x15=15 | 0x15=0  | 9
5x17=85 | <strong>4</strong>x17=68 | 24
3x19=57 | <strong>2</strong>x19=38 | 41

4. This gives us our new number

7 5 8 9 8 6 3 4 0 4 2

5. Now we just need to add 1 to the very first number (as per the ABN validation steps) and we have our valid ABN

85898634042

There are a couple of nuances to those steps.

  • None of our initial generated digits can be zero. Since we "give change" by subtracting 1 from each digit we need to ensure we can actually subtract 1 (otherwise things become much more complex). So we ensure our digits are randomly generated between 1 and 9 rather tahn between 0 and 9.
  • Even when all our initial digits are at least 1 we may still fail to "give change" for some of the remainders, the easiest example of this is when our remainder is 2. The only digit when can use to give change is the one with the weight of 1 (i.e. the second digit of the ABN). If this digit is initially generated to be 1, we can only give change once at which point we end up with a remainder of 1 and there is nothing more we can do about it. In-fact this exact scenario can happen for a few other remainders namely 86, 77, 66, 53, 38, 21. The easies way to overcome this problem is to ensure that the digit that has a weight of 1, is always randomly generated to have a value of at least 2. This way we can use it to give change twice and our problematic remainders are covered.
  • Lastly, since we have to add 1 to the very first digit as our final step, we need to make sure that this digit is not already equal to 9, so we generate that one to be between 1 and 8.

Given these nuances, this algorithm won't generate every possible ABN, but it will give you a large percentage of possible ABNs which is good enough for our needs. It took about an hour to get that working (we won't mention the little bug where I forgot the remainder could be zero from the start, which caused much grief to our random data generator :)), but it was a fun little exercise – time well spent as far as I am concerned. And to think, all this learning about self-validating numbers and algorithmic coding fun was triggered by trying to capture the most mundane piece of data on a form. It just goes to show that you can learn and grow no matter where you are and what you're doing, you just need to see the opportunities for what they are.

Images by Sn.Ho and Sangudo

Algorithms, A Dropbox Challenge And Dynamic Programming

AlgorithmLately I've slowly been trying to grok the fullness of dynamic programming. It is an algorithmic technique that the vast majority of developers never master, which is unfortunate since it can help you come up with viable solutions for seemingly intractable problems. The issue with dynamic programming (besides the totally misleading name), is that it can be very difficult to see how to apply it to a particular problem and even when you do, it is a real pain to get it right. Anyway, I don't want to expound on this, I have something more interesting in mind.

The Dropbox Challenges

I was surfing the web the other day and in the course of my random wanderings I ended up at the Dropbox programming challenges page. Apparently, the Dropbox guys have posted up some coding challenges for people who want to apply to work there (and everyone else, I guess, since it's on the internet and all :)). Challenge 3 (The Dropbox Diet) immediately caught my eye since it looked like one of those problems that should have a dynamic programming solution, so I decided to use it as an opportunity to practice. The full description of the problem is on the challenge page, but here is the gist of it.

We get a list of up to 50 activities and an associated calorie value for each (either positive or negative), we need to find a subset of activities where the sum of all the calorie values is zero.

It sounded easy enough until I thought about it and realised it was more complex than it first appeared. So, I went for a walk :) and when I came back I settled in to analyse it for real. The first part of solving any problem is to really understand what problem you're trying to solve (that one sentence really deserves its own article). In this case the activities list is just extraneous information, what we really have is a list of numbers and we need to find a subset of these numbers where the sum of the subset is equal to a particular value. It took me quite a while to come up with that definition, but once you have something like that, you can do some research and see if it is a known problem.

Of course, I did nothing of the kind, I had already decided that there must be a dynamic programming solution so I went ahead and tried to come up with it myself. This wasted about an hour at the end of which I had absolutely nothing; I guess my dynamic programming chops are still lamb-chops as opposed to nice meaty beef-chops :). Having failed I decided to do what I should have done in the first place – some research. Since I had taken the time to come up with a decent understanding of the problem, it only took 5 minutes of Googling to realise that I was dealing with the subset sum problem.

The Subset Sum Problem

Subset

The unfortunate thing about the subset sum problem is the fact that it's NP-complete. This means that if our input is big enough we may be in trouble. Wikipedia does give some algorithmic approaches to the problem (no code though), but just to cross our t's I also cracked open Cormen et al (have you ever noticed how that book has everything when it comes to algorithms :)). In this case the book agreed with Wikipedia, but once again, no code (there are only two things I don't like about Intro To Algorithms, the lack of real code and the lack of examples). I browsed the web some more, in case it would give me further insight into the problem, but there wasn't much more to know – it was time to get my code on.

The Exponential Time Algorithm

The problem with the exponential time algorithm is its runtime complexity (obviously), but our maximum input size was only 50 and even if that turned out to be too big, perhaps there were some easy optimizations to be made. Regardless I decided to tackle this one first, if nothing else it would immerse me in the problem. I'll demonstrate how it works via example. Let's say our input looks like this:

[1, -3, 2, 4]

We need to iterate through the values and on every iteration produce all the possible subsets that can be made with all the numbers we've looked at up until now. Here is how it looks:

Iteration 1:

[[1]]

Iteration 2:

[[1], [-3], [1, -3]]

Iteration 3:

[[1], [-3], [1, -3], [2], [1, 2], [-3, 2], [1, -3, 2]]

Iteration 4:

[[1], [-3], [1, -3], [2], [1, 2], [-3, 2], [1, -3, 2], [4], [1, 4], [-3, 4], [1, -3, 4], [2, 4], [1, 2, 4], [-3, 2, 4], [1, -3, 2, 4]]

On every iteration we simply take the number we're currently looking at as well as a clone of the list of all the subsets we have seen so far, we append the new number to all the subsets (we also add the number itself to the list since it can also be a subset) and then we concatenate this new list to the list of subsets that we generated on the previous iteration. Here is the previous example again, but demonstrating this approach:

Iteration 1:

[] + [1]

Iteration 2:

[1] + [-3], [1, -3]

Iteration 3:

[1], [-3], [1, -3] + [2], [1, 2], [-3, 2], [1, -3, 2]

Iteration 4:

[1], [-3], [1, -3], [2], [1, 2], [-3, 2], [1, -3, 2] + [4], [1, 4], [-3, 4], [1, -3, 4], [2, 4], [1, 2, 4], [-3, 2, 4], [1, -3, 2, 4]

This allows us to generate all the possible subsets of our input, all we have to do then is pick out the subsets that sum up to the value we're looking for (e.g. 0).

The list of subsets grows exponentially (it being an exponential time algorithm and all :)), but since we know what sum we're looking for, there is one small optimization we can make. We can sort our input list before trying to generate the subsets, this way all the negative values will be first in the list. The implication here is this, once the sum of any subset exceeds the value we're looking for, we can instantly discard it since all subsequent values we can append to it will only make it bigger. Here is some code:

def subsets_with_sum_less_than_or_equal(reference_value, array)
  array = array.sort {|a,b| a <=> b}
  previous_sums = []
  array.each do |element|
    new_sums = []
    new_sums << [element] if element <= reference_value
    previous_sums.each do |previous_sum|
      current_sum = previous_sum + [ element ]
      new_sums << current_sum if current_sum.inject(0){|accumulator,value|accumulator+value} <= reference_value
    end
    previous_sums = previous_sums + new_sums
  end
  previous_sums
end

If we execute that (with our reference value being 0 and our array being [1, -3, 2, 4]), we get the following output:

[[-3], [-3, 1], [-3, 2], [-3, 1, 2]]

All the subsets in that list sum up to less than or equal to our reference value (0). All we need to do now is pick out the ones that we're after.

def subsets_with_sums_equal(reference_value, array)
  subsets_with_sums_less_than_or_equal = subsets_with_sum_less_than_or_equal(reference_value, array)
  subsets_adding_up_to_reference_value = subsets_with_sums_less_than_or_equal.inject([]) do |accumulator, subset|
    accumulator << subset if subset.inject(0){|sum, value| sum+value} == reference_value
    accumulator
  end
  subsets_adding_up_to_reference_value
end

This function calls the previous one and then picks out the subset we're after:

[[-3, 1, 2]]

It's simple and works very well for any input array with less than 20 values or so, and if you try it with more than 25 – good luck waiting for it to finish :). Exponential time is no good if we want it to work with an input size of 50 (or more) numbers.

The Dynamic Programming Algorithm

Matrix

Both Wikipedia and Cormen tell us that there is a polynomial time approximate algorithm, but that's no good for us since we want the subsets that add up to exactly zero, not approximately zero. Fortunately, just like I suspected, there is a dynamic programming solution, Wikipedia even explains how it works, which is only marginally helpful when it comes to implementing it. I know because that was the solution I tackled next. Here is how it works, using the same input as before:

[1, -3, 2, 4]

Just like with any dynamic programming problem, we need to produce a matrix, the key is to figure out what it's a matrix of (how do we label the rows and how do we label the columns). In this case the rows are simply the indexes of our input array; the columns are labelled with every possible sum that can be made out of the input numbers. In our case, the smallest sum we can make from our input is -3 since that's the only negative number we have, the biggest sum is seven (1 + 2 + 4). So, our uninitialized matrix looks like this:

+---+----+----+----+---+---+---+---+---+---+---+---+
|   | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+----+----+----+---+---+---+---+---+---+---+---+
| 0 |    |    |    |   |   |   |   |   |   |   |   |
| 1 |    |    |    |   |   |   |   |   |   |   |   |
| 2 |    |    |    |   |   |   |   |   |   |   |   |
| 3 |    |    |    |   |   |   |   |   |   |   |   |
+---+----+----+----+---+---+---+---+---+---+---+---+

So far so good, but what should we put in every cell of our matrix. In this case every cell will contain either T (true) or F (false).

A T value in a cell means that the sum that the column is labelled with can be constructed using the input array numbers that are indexed by the current row label and the labels of all the previous rows we have already looked at. An F in a cell means the sum of the column label cannot be constructed. Let's try to fill in our matrix to see how this works.

We start with the first row, the number indexed by the row label is 1, there is only one sum that can be made using that number – 1. So only one cell gets a T in it, all the rest get an F.

+---+----+----+----+---+---+---+---+---+---+---+---+
|   | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+----+----+----+---+---+---+---+---+---+---+---+
| 0 | F  | F  | F  | F | T | F | F | F | F | F | F |
| 1 |    |    |    |   |   |   |   |   |   |   |   |
| 2 |    |    |    |   |   |   |   |   |   |   |   |
| 3 |    |    |    |   |   |   |   |   |   |   |   |
+---+----+----+----+---+---+---+---+---+---+---+---+

The number indexed by the second row label is -3, so in the second row, the column labelled by -3 will get a T in it. However, we're considering the numbers indexed by the current row and all previous rows, which means any sum that can be made using the numbers 1 and -3 will get a T in its column. This means that the column labelled with 1 gets a T and the column labelled with -2 gets a T since

1 + -3 = -2
+---+----+----+----+---+---+---+---+---+---+---+---+
|   | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+----+----+----+---+---+---+---+---+---+---+---+
| 0 | F  | F  | F  | F | T | F | F | F | F | F | F |
| 1 | T  | T  | F  | F | T | F | F | F | F | F | F |
| 2 |    |    |    |   |   |   |   |   |   |   |   |
| 3 |    |    |    |   |   |   |   |   |   |   |   |
+---+----+----+----+---+---+---+---+---+---+---+---+

We continue in the same vein for the next row, we're now looking at number 2 since it's indexed by the third row in our matrix. So, the column labelled by 2 will get a T, all the columns labelled by T in the previous row propagate their T value down, since all those sums are still valid. But we can produce a few other sums given the numbers at our disposal:

2 + -3 = -1
1 + 2 + -3 = 0
1 + 2 = 3

All those sums get a T in their column for this row.

+---+----+----+----+---+---+---+---+---+---+---+---+
|   | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+----+----+----+---+---+---+---+---+---+---+---+
| 0 | F  | F  | F  | F | T | F | F | F | F | F | F |
| 1 | T  | T  | F  | F | T | F | F | F | F | F | F |
| 2 | T  | T  | T  | T | T | T | T | F | F | F | F |
| 3 |    |    |    |   |   |   |   |   |   |   |   |
+---+----+----+----+---+---+---+---+---+---+---+---+

There are three patterns that are starting to emerge.

  1. For every row, the column which is equivalent to the number indexed by the row get a T in it (e.g. row zero represents the number 1, so the column labelled by 1 gets a T in row 0, row one represents the number -3 so the column labelled by -3 get a T in row 1 etc.), every row will get one T in one of the columns via this pattern. This is because a single number by itself is a valid subset sum.
  2. If a column already has a T in the previous row, this T propagates down to the current row (e.g. when looking at the second row, the column labelled by 1 has a T in the first row and will therefore have a T in the second row also, when looking at the third row columns labelled by -3, -2 and 1 all had a T in the second row and will therefore contain a T in the third row). This is due to the fact that once it is possible to construct a certain sum using a subset of our input numbers, looking at more of the input numbers does not invalidate the existing subsets.
  3. Looking at any column label X in the current row which still has a value of F, if we subtract the number indexed by the current row from this column label we get a new number Y, we then check the row above the current row in the column labelled by Y, if we see a T, this T is propagated into the column X in the current row (e.g. if we're looking at the second row, column labelled with -2, we subtract the number of the current row -3 from the column label, -2 – -3 = -2 + 3 = 1, this new number is the column label in the first row, we can see that in the first row in the column labelled with 1 there is a T, therefore this T gets propagated to the second row into the column labelled with -2). This is due to the fact that if we take a sum that is already possible and add another number to it, this obviously creates a new sum which is now possible.

Those three patterns are the algorithm that we use to fill in our matrix one row at a time. We can now use them to fill in the last row. The number indexed by the last row is 4. Therefore in the last row, the column labelled by 4 will get a T (via the first pattern). All the columns that already have a T will have that T propagate to the last row (via the second pattern). This means the only columns with an F will be those labelled by 5, 6 and 7. However using pattern 3, if we subtract 4 from 5, 6 and 7 we get:

5 - 4 = 1
6 - 4 = 2
7 - 4 = 3

If we now look at the previous row in the columns labelled by those numbers we can see a T for all three cases, therefore, even the columns labelled with 5, 6 and 7 in the last row will pick up a T via the third pattern. Our final matrix is:

+---+----+----+----+---+---+---+---+---+---+---+---+
|   | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+----+----+----+---+---+---+---+---+---+---+---+
| 0 | F  | F  | F  | F | T | F | F | F | F | F | F |
| 1 | T  | T  | F  | F | T | F | F | F | F | F | F |
| 2 | T  | T  | T  | T | T | T | T | F | F | F | F |
| 3 | T  | T  | T  | T | T | T | T | T | T | T | T |
+---+----+----+----+---+---+---+---+---+---+---+---+

One final problem remains, how can we use this matrix to get the subset that adds up to the value we want (i.e. 0). This is also reasonably simple. We start in the column labelled by the sum we're after, in our case we start in the column labelled by zero. If this column does not contain a T then our sum is not possible and the input does not have a solution. In our case, the column does have a T so we're in business.

  • We start at the last row in this column; if it has a T and the row above has a T we go to the row above.
  • If the row above has an F then we take the number which is indexed by the current row and write it into our final output.
  • We then subtract this number from the column label to get the next column label. We jump to the new column label and go up a row.
  • Once again if there is a T there and there is an F above, then we write the number indexed by the row into our output and subtract it from the current column label to get the next column label.
  • We then jump to that column and go up a row again.
  • We keep doing this until we get to the top of the matrix, at this point the numbers we have written to the output will be our solution.

Let's do this for our matrix. We start at the column labelled by 0 since that's the sum we're looking for. We look at the last row and see a T, but there is also a T in the row above so we go up to that row. Now there is an F in the row above, so we write the number indexed by this row into our output:

output = [2]

We now subtract this number from our column label to get the new column label:

0 - 2 = -2

We jump to the column labelled by -2 and go up a row, there is another T there with an F in the row above, so we write the number indexed by the row to our output:

output = [2, -3]

We perform our subtraction step again:

-2 - -3 = -2 + 3 = 1

We now jump to the column labelled by 1 in the first row in the matrix. There is also a T there, so we need to write one last number to our output:

output = [2, -3, 1]

Since we're at the top of the matrix, we're done. As you can see the procedure we perform to reconstruct the output subset is actually a variant of the third pattern we used to construct the matrix. And that's all there is to it.

Oh yeah, I almost forgot the code :), since it is not tiny, I put it in a gist, you can find it here. But, here are the guts of it:

  def initialize_first_row
    @matrix[1].each_with_index do |element,i|
      next if i == 0 # skipping the first one since it is the index into the array
      if @array[@matrix[1][0]] == @matrix[0][i] # the only sum we can have is the first number itself
        @matrix[1][i] = "T";
      end
    end
    @matrix
  end

  def populate
    ([email protected]).each do |row|
      @matrix[row].each_with_index do |element,i|
        next if i == 0
        if @array[@matrix[row][0]] == @matrix[0][i] || @matrix[row-1][i] == 'T' || current_sum_possible(row, i) 
          @matrix[row][i] = "T";
        end
      end
    end
    @matrix
  end

  def current_sum_possible(row, column)
    column_sum = @matrix[0][column] - @array[@matrix[row][0]]
    column_index = @column_value_to_index[column_sum]
    return false unless column_index
    @matrix[row-1][column_index] == "T";
  end

  def derive_subset_for(reference_value)
    subset = []
    column_index = @column_value_to_index[reference_value]
    ([email protected]).to_a.reverse.each do |row|
      if @matrix[row][column_index] == "F";
        return subset
      elsif @matrix[row-1][column_index] == "T";
        next
      else
        array_value = @array[row - 1] # the -1 is to account for the fact that our rows are 1 larger than indexes of input array due to row 0 in matrix being header
        subset.insert(0, array_value)
        column_index = @column_value_to_index[@matrix[0][column_index] - array_value]
      end
    end
    subset
  end

You can recognise the 3 patterns being applied in the 'populate' method. We're, of course, missing the code for instantiating the matrix in the first place. Grab the whole thing from the gist and give it a run, it generates random inputs of size 50 with values between -1000 and 1000. And if you think that would produce quite a large matrix, you would be right :) (50 rows and about 25000 columns give or take a few thousand). But even with input size 100 it only takes a couple of seconds to get an answer, which is MUCH better than the exponential time algorithm; in my book that equals success. Dropbox Challenge 3 – solved (more or less :))!

By the way if you want to print out a few more matrices, grab the code and uncomment the relevant line (102) and you'll get a matrix similar to those above along with the rest of the output. Obviously, if you're doing that, make sure your input size is small enough for the matrix to actually fit on the screen. I used the great terminal-table gem to produce the nice ASCII tables.

Lastly, if you're wondering what framework this is:

if ENV["attest"]
  this_tests "generating subset sums using dynamic programming" do
    test("subset should be [1,-3,2]") do
      actual_subset_sum = subset_sum_dynamic([1, -3, 2, 4], 0)
      should_equal([1,-3,2], actual_subset_sum)
    end
    ...
  end
end

That would be me eating my own dog food, I took the time to write it, might as well use it :).

By the way, it took me hours (pretty much the better part of a day) to get all of this stuff working properly, dynamic programming algorithms really are fiddly little beasts. But, I had some fun, and got some good practice and learning out of it – time well spent (and now there is some decent subset sum code on the internet :P). Of course once I finished with this I had to look at the other challenges, number 2 didn't really catch my attention, but I couldn't walk away from number 1 with its ASCII boxes and bin packing goodness – I'll write that one up some other time.

Images by johntrainor, infinitewhite and familymwr