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 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.

Image by spaceninja

No related posts.

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)

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

Related posts:

1. Why Your Developers Don’t Want To Swap Pairs – Practical Agility
2. The Current State Of The Agile Nation – Agile Process Adoption
3. Fitness for Software Developers (and Other IT Professionals)

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

Related posts:

1. How To Save Money As A Student
2. Fetching RSS Feeds With Ruby From Behind A Proxy
3. How To Write A Simple Web Crawler In Ruby

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

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  | 6x9=63  | 0
  3x11=33 | 3x11=33 | 9
  4x13=52 | 4x13=52 | 9
  1x15=15 | 0x15=0  | 9
  5x17=85 | 4x17=68 | 24
  3x19=57 | 2x19=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

Related posts:

1. The Most Common Things You Do To A Large Data File With Bash
2. Are You The Best Developer In The World?
3. Become A Better Developer By Indexing Your Brain

Lately 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

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

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
    (2...@matrix.size).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]
    (1...@matrix.size).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

Related posts:

1. Effective vs Ineffective Pair Programming
2. Sort Files Like A Master With The Linux Sort Command (Bash)
3. How To Answer A Programming Interview Question And Look Good Doing It

Late last year I attended some workshops which were being run as part of the YOW Melbourne developer conference. Since the workshops were run by @coreyhaines and @jbrains, TDD was a prominent part. Normally this would not be an issue, but in a spectacular display of fail (considering it was a developer conference in 2010), the internet was hard to come by, which left me and my freshly installed Linux laptop without the ability to acquire Rspec. Luckily a few weeks before, I decided to write a unit testing framework of my very own (just because I could :)) and so I had a reasonably fresh copy of that code lying around – problem solved. But, it got me thinking, what is the minimum amount of code needed to make a viable unit testing framework?

A Minimum Viable Unit Test

I had some minimal code when I first toyed with writing a unit testing framework, but then I went and ruined it by adding a bunch of features :), fortunately it is pretty easy to recreate. What we really want is the ability to execute the following code:

describe "some test" do
  it "should be true" do
    true.should == true
  end
 
  it "should show that an expression can be true" do
    (5 == 5).should == true
  end
 
  it "should be failing deliberately" do
    5.should == 6
  end
end

As you can see it looks very much like a basic Rspec test, let's try and write some code to run this.

Building A Basic Framework

The first thing we're going to need is the ability to define a new test using "describe". Since we want to be able to put a “"describe"” block anywhere (e.g. its own file), we're going to have to augment Ruby a little bit. The "puts" method lives in the Kernel module and is therefore available anywhere (since the Object class includes Kernel and every object in Ruby inherits from Object), we will put describe inside Kernel to give it the same ability:

module Kernel
  def describe(description, &block)
    tests = Dsl.new.parse(description, block)
    tests.execute
  end
end

As you can see, "describe" takes a description string and a block that will contain the rest of our test code. At this point, we want to pull apart the block that we're passing to "describe" to separate it into individual examples (i.e. "it" blocks). For this we create a class called Dsl and pass our block to its parse method, this will produce an object that will allow us to execute all our test, but let's not get ahead of ourselves. Our Dsl class looks like this:

class Dsl
  def initialize
    @tests = {}
  end
  def parse(description, block)
    self.instance_eval(&block)
    Executor.new(description, @tests)
  end
  def it(description, &block)
    @tests[description] = block
  end
end

What we do here is evaluate our block in the context of the current Dsl object:

self.instance_eval(&block)

Our Dsl object has an "it" method which also takes a description and a block and since that is exactly what our describe block contains everything works well (i.e. we're essentially making several method calls to the "it" method each time passing in a description and a block). We could define other methods on our Dsl object and those would become part of the "language" which will be available to us in the "describe" block.

Our "it" method will be called once for every "it" block in the describe block, every time that happens we simply take the block that was passed in and store it in hash keyed on the description. When we're done, we simply create a new Executor object which we will use to iterate over our test blocks, call them and produce some results. The executor looks like this:

class Executor
  def initialize(description, tests)
    @description = description
    @tests = tests
    @success_count = 0
    @failure_count = 0
  end
  def execute
    puts "#{@description}"
    @tests.each_pair do |name, block|
      print " - #{name}"
      result = self.instance_eval(&block)
      result ? @success_count += 1 : @failure_count += 1
      puts result ? " SUCCESS" : " FAILURE"
    end
    summary
  end
  def summary
    puts "\n#{@tests.keys.size} tests, #{@success_count} success, #{@failure_count} failure"
  end
end

Our executor code is reasonably simple. We print out the description of our "describe" block we then go through all the "it" blocks we have stored and evaluate them in the context of the executor object. In our case there is no special reason for this, but it does mean that the executor object can also be a container for some methods that can be used as a "language" inside "it" blocks (i.e. part of our dsl can be defined as method on the executor). For example, we could define the following method on our executor:

def should_be_five(x)
  5 == x
end

This method would then be available for us to use inside our "it" blocks, but for our simple test it is not necessary.

So, we evaluate our "it" blocks and store the result, which is simply going to be the return value of the last statement in the "it" block (as per regular Ruby). In our case we want to make sure that the last statement always returns a boolean value (to indicate success or failure of the test), we can then use it to produce some meaningful output.

We are missing one piece though, the "should" method, we had code like:

true.should == true
5.should == 5

It seems that every object has the "should" method available to it and that's exactly how it works:

class Object
  def should
    self
  end
end

The method doesn't really DO anything (just returns the object); it simply acts as syntactic sugar to make our tests read a bit better.

At this stage, we just take the result of evaluating the test, turn it into a string to indicate success or failure and print that out. Along the way we keep track of the number of successes or failures so that we can produce a summary report in the end. That's all the code we need, if we put it all together, we get the following 44 lines:

module Kernel
  def describe(description, &block)
    tests = Dsl.new.parse(description, block)
    tests.execute
  end
end
class Object
  def should
    self
  end
end
class Dsl
  def initialize
    @tests = {}
  end
  def parse(description, block)
    self.instance_eval(&block)
    Executor.new(description, @tests)
  end
  def it(description, &block)
    @tests[description] = block
  end
end
class Executor
  def initialize(description, tests)
    @description = description
    @tests = tests
    @success_count = 0
    @failure_count = 0
  end
  def execute
    puts "#{@description}"
    @tests.each_pair do |name, block|
      print " - #{name}"
      result = self.instance_eval(&block)
      result ? @success_count += 1 : @failure_count += 1
      puts result ? " SUCCESS" : " FAILURE"
    end
    summary
  end
  def summary
    puts "\n#{@tests.keys.size} tests, #{@success_count} success, #{@failure_count} failure"
  end
end

If we "require" this code and execute our original sample test, we get the following output:

some test
 - should be true SUCCESS
 - should show that an expression can be true SUCCESS
 - should be failing deliberately FAILURE
3 tests, 2 success, 1 failure

Nifty! Now, if you're ever stuck without a unit testing framework and you don't want to go cowboy, just spend 5 minutes and you can whip up something reasonably viable to tide you over. I am, of course, exaggerating slightly; you will quickly start to miss all the extra expectations, better output, mocking and stubbing etc. However we can easily enhance our little framework with some of those features (e.g. adding extra DSL elements) – the development effort is surprisingly small. If you don't believe me, have a look at bacon it is only a couple of hundred lines and is a reasonably complete little Rspec clone. Attest – the framework that I wrote is another decent example (even if I do say so myself :P). Both of them do still miss any sort of built-in test double support, but adding that is a story for another time.

Image by jepoirrier

Related posts:

1. True, False And Nil Objects In Ruby
2. Ruby Equality And Object Comparison
3. More Advanced Ruby Method Arguments – Hashes And Block Basics

"I will learn it when I need it"! I've heard that phrase a lot over the years; it seems like a highly pragmatic attitude to foster when you're in an industry as fast-paced as software development. On some level it actually IS quite pragmatic, but on another level I am annoyed by the phrase. It has become a mantra for our whole industry which hasn't changed said industry for the better. The problem is this, in the guise of sounding like a wise and practical developer, people use it as an excuse to coast. There is too much stuff to know, it is necessary to be able to pick certain things up as you go along – part of the job. But, there is a difference between having to "pick up" some knowledge as you go along and doing absolutely everything just-in-time.

The whole industry has become a bunch of generalists, maybe it has always been this way, I just wasn't around to see it, either way I don't like it. Noone wants to invest the time to learn anything really deeply, not computer science fundamentals, not the latest tech you're working with, not even the language you've been coding in every day, for the last few years. Why bother, it will be replaced, superseded, marginalised and out of fashion before you're half way done. I've discussed this with various people many times, but noone seems to really see it as a problem. "Just being pragmatic dude". In the meantime we've all become clones of each other. You want a Java developer, I am a Java developer, you're a Java developer, my neighbour is a Java developer. What differentiates us from each other – not much! Well, I've got some jQuery experience. That's great, so you know how to build accordion menu then? Sure, I Google it and steal the best code I find :). In the meantime, if you need to hire a REAL expert (in anything, maybe you're writing a fancy parser or need to visualise some big data), I hope you've stocked up on beer and sandwiches cause you're gonna be here a while.

Ok, there are ways to differentiate yourself, I have better communication skills, which is why I do better. That's important too, but, developers differentiating themselves based on soft skills rather than developer skills – seems a bit twisted. We all communicate really well but the code is a mess :). Hell, I shouldn't really talk, I am a bit of a generalist too. Of course I'd like to think of myself as a T-shaped individual, but if we're completely honest, it's more of a dash-shaped or underscore-shaped with maybe a few bumps :). To the uninitiated those bumps might look like big giant stalactites – T-shaped indeed. You seem like an expert without ever being an expert, just one advantage of being in a sea of generalists.

Investing In Your Future

I don't want to preach about how we should all be investing in our professional future, everybody knows we should be. Most people probably think they are infact investing, they rock up to work, write a lot of code maybe even do some reading on the side, surely that must make them an expert in about 10 years, and a senior expert in 20 (I keep meaning to write more about this, one day I'll get around to it :))? But, if that was the way, every old person would be an expert in a whole bunch of stuff and that is emphatically not the case. Maybe it is just that people don't know how to build expertise (there is an element of truth to this), but I have a sneaking suspicion that it's more about lack of desire rather than lack of knowledge. What was that saying about the will and the way – totally applicable in this case?

I've gone completely off-track. "Investing in professional future" is just one of those buzzword things, the mantra is "I will learn it when I need it". It was good enough for my daddy and it has served me well so far. Let's apply this thinking to finance, "I will invest my money when I think I need the money". Somehow it doesn't quite have the same kind of pragmatic ring to it.

You Don't Know What You Don't Know

We've all had those moments where you're going through major pain trying to solve a problem until someone comes along and tells you about algorithm X or technology Y and it makes everything fast and simple. It was lucky that person just happened to be there to show you the "easy" way, otherwise you would have spent days/weeks trying to figure it out and it would have been a mess. You can't be blamed for this though, you don't know what you don't know. For me, this is where the "I will learn it when I need it" mentality falls over. You can't learn something if you don't know it exists. Google goes a long way towards mitigating this problem, but not all the way. There are plenty of problems you will encounter in the wild where you can beat your head against the wall ad infinitum unless you know what class of problem you're looking at (e.g. if you know a bit about searching and constraint propagation, solving sudoku is easy, otherwise it's really quite hard). You can't learn about an algorithm if you're not aware of it or its applicability. You can't utilise a technology to solve a problem if you don't even realise it has that capability. You're not going to always have someone there to point you in the right direction. I am willing to bet there is a billion lines of code out there right now which can be replaced with a million lines of faster, cleaner, better code simply because whoever wrote it didn't know what they didn't know.

I seem to be making a case for the opposite side here, if knowing what you don't know is the ticket then surely we should be focusing on breadth of knowledge. Superficial awareness of as much stuff as possible should see us through, we'll be able to recognise the problems when we see them and then learn what we need more deeply. Except it doesn't work like that, skimming subjects doesn't allow you to retain anything, our brain doesn't work that way. If we don't reinforce and dig deeper into the concepts we quickly page that information out as unimportant, it is a waste of time (think back to cramming for exams, how much do you remember the next day?). However if you focus on building deeper understanding of a subject – in an interesting twist – you will gain broad knowledge as well (which you will actually be able to retain). My grandad is a nuclear physicist, several decades of working to gain deeper knowledge of the subject has made him an expert, but it has also made him an excellent mathematician, a decent chemist, a pretty good geologist, a fair biologist etc. Just some empirical evidence that seeking depth leads to breadth as a side-effect.

Can You Learn It Fast Enough

Some stuff just takes a long time to learn. I am confident I can pick up an ORM framework I haven't seen before without even breaking stride, I've used them before, the concepts are the same. But what if you need to do some speech to text conversion, not quite as simple, not enough background. Hopefully Google will have something for us to copy/paste. That was a bad example, only research boffins at universities need to do that crap. How about building a website then, we all know how to do that, but what if you need to do it for 10 million users a day. We just need to learn everything about scaling, I am sure the users will wait a month or two for us to get up to speed :). Yeah, I am just being stupid, all we need to do is hire an expert and … errr … oh wait, we're all out of beer and sandwiches.

Why Should I Care

Working with experts is freaking awesome. You may have experienced it before, everything they say is something new and interesting, you learn new tricks with every line of code, you can almost feel your brain expanding :). You want to learn from the experts, so it's really sad when you can't find any. Since everyone is only learning when they "need it", noone can teach anything to anyone. The chunk of wisdom here is this, you want to work with experts, but the experts also want to work with experts, so what are you doing to make sure the experts want to work with you? Being able to learn something when you need it is a good skill to have, but you can not let it be your philosophy as a developer. Yes it is a big industry you can't learn everything, so pick something and make sure you know it backwards, if you're curious enough to follow up on the interesting bits, you'll find you have a decent grasp of a lot of other stuff at the end. And if you do a good enough job, other super-awesome-smart people are going to want to come and hang around you cause they'll be able to learn something from you and you'll be able to learn much from them. Everybody will be a winner.

Image by SamueleGhilardi and SpecialKRB

Related posts:

1. Software Development And The Sunk Cost Fallacy
2. Here Are Some Words That Rhyme With Orange!
3. You Don’t Need Math Skills To Be A Good Developer But You Do Need Them To Be A Great One

I've talked about interviews from one perspective or another on several occasions, you might even say it is a pet subject of mine. It's fascinating because most people are no good at interviews and when it comes to developer interviews – well; let's just say there is a whole new dimension for us to suck at with coding questions, whiteboards and whatnot. Of course, the other side of the equation is not pristine here, the interviewer can be just as much to blame for a terrible interview, either through lack of training, empathy, preparation or a host of other reasons, but that's a whole separate discussion. So, why are we so bad at interviews? You can probably think of quite a few reasons straight away:

• it is a high pressure situation, you were nervous
• you just didn't "click" with the interviewer
• you were asked all the "wrong" questions
• sometimes you just have a bad day

Infact, you can often work yourself into a self-righteous frenzy after a bad interview, thinking how every circumstance seemed to conspire against you, it was beyond your control, there was nothing you could do – hell, you didn't even want to work for that stupid company anyway! But, deep down, we all know that those excuses are just so much bullshit. The truth is there were many things we could have done, but by the time the interview started it was much too late. I'll use a story to demonstrate.

The least stressful exam I’ve ever had was a computing theory exam in the second year of my computer science degree. I never really got “into it” during the semester, but a few weeks before exam time – for some inexplicable reason – I suddenly found the subject fascinating. I spent hours reading and hours more playing with grammars and automata. Long story short, when exam time rolled around I knew the material backwards – I groked it. There was some anxiety (you can’t eliminate it fully), but I went into the exam reasonably confident I’d blitz it (which I did). Practice and preparation made all the difference. Of course, this is hardly a revelation, everyone knows that if you study and practice you’ll do well (your parents wouldn’t shut up about it for years :)). Interviews are no different from any other skill/subject in this respect, preparation and practice are key.

Can You Wing It?

The one difference with interviews is that they are an occasional skill, almost meaningless most of the time, but of paramount importance once in a long while. It just doesn't seem like it's worth the effort to get good at them, especially if you happen to already have a job at the time (who knows, you may not need those skills for years). There are plenty of other subjects clamouring for your attention and anyway every interview is different, you can never predict what's gonna happen so it would be stupid to waste your time trying. No – good communication skills and decent software development knowledge will see you through, right? Except, they don't and it won't. Sure, you might be able to stave off total disaster, but without preparation and practice, you're mostly relying on luck. Things "click"; you get asked the "right" questions and are able to think of decent answers just in time. This is how most people get hired. As soon as the process gets a little more rigorous/scientific, so many candidates get weeded out that companies like Google, Facebook, Twitter etc. find themselves trying to steal people from each other since they know that those that have passed the rigorous interview processes of their competitors must be alright. The interesting thing is that the rejected candidates are not necessarily worse; they are often simply a lot less prepared and a little less lucky.

Over the last few years presentation skills have seen quite a lot of press. Many a blog post and much literature has come out (e.g. Presentation Zen and Confessions of a Public Speaker are both great books). Many people have decent knowledge of their subject area and have good communication skills, they think they are excellent presenters – they are wrong. They put together some slides in a few hours and think their innate abilities will carry them through, but inevitably their presentations end up disjointed, mistargeted, boring or amateurish. Sometimes they sail through on luck, circumstances conspire and the presentation works, but these situations are not common. Malcolm Gladwell is a master presenter, he is one of the most highly sought after and highly paid speakers in the world (and has written a bunch of awesome books to boot) – this is not by chance. Without doubt he knows his stuff and has better communication skills than the majority of speakers out there and yet all his talks are rigorously prepared for and practiced. To my mind, the situation with interviews is similar to that of presentations, except the deluge of literature about interviews goes almost unnoticed since they are old-hat. The digital world hasn't changed the interview process too significantly (unlike the public speaking process), except the internet age brings all the old advice together in one place for us and all of that advice is still surprisingly relevant.

The Old-School Advice

Everyone (and I mean everyone) always says that you should research the company you'll be interviewing with beforehand. You would think people would have this one down by now, especially developers cause we're smart, right? Nope, no such luck, just about everyone who rocks up for an interview knows next to nothing about the company they are trying to get a job at, unless the company is famous, in which case people are just full of hearsay. But hearsay is no substitute for a bit of research and it is so easy, I am reminded of an article Shoemoney wrote about getting press (well worth a read by the way, if you're trying to promote a product/service) – there is a tremendous amount of info you can find out about a person by trawling the web for a bit and it is just as easy to learn something about a company. I mean, we do work in software, so any company you may want to work for should have a web presence and a half. And even if web info is sparse there is your social network or picking up the phone and seeing if someone will trade a coffee for some info. Yeah, you go to a bit of trouble but the fact that you did will be apparent in an interview, I mean, there is a reason why I work where I work and I'd prefer to work with other people who give a shit (everyone would) – you savvy? Of course if you do go to the trouble to find out what skills/tech/knowledge/processes a company is looking for/values you may be able to anticipate where an interview might head, the value there should be self-evident.

Which leads me to interview questions. When it comes to developers, there are three types of questions we struggle with/despise:

• the behavioural/culture fit
• the coding question
• the Mount Fuji question

With a bit of practice you can blitz all of these. The Fujis are the hardest, but even they can be prepared for, but I'll get back to those shortly.

Behavioural Questions

The behavioural questions seem annoyingly difficult but are actually the easiest. You know the ones "Give me an example of a time when you demonstrated leadership/communication skills/problem solving/conflict resolution". It is always the same question, with a different attribute of yours that you have to spruik. Being in essence the same question you can address all of them with what amounts to the same answer, once again substituting a different attribute. These are actually difficult to handle on the spot, but if you have something prepared it is a breeze. Example:

"There was a time, when Bill the developer was being an obstinate bastard and wouldn't buy in to the awesome that the rest of us were peddling, but I took charge of the situation and was able to convince Bill blah, blah …." – leadership

"Bill the contrary developer just wouldn't agree with the way we were dishing out the awesome, but I took Bill out for coffee and we hashed it out one on one blah, blah …" – communication

"There was insufficient awesome to go around and Bill and Joe just couldn't share it and were coming to blows, but I stepped in and took them both to a whiteboard, we had a long chat blah, blah …" – conflict resolution

As long as you think up a situation beforehand you can adapt it to answer any behavioural question, the situation can even be a fictitious, but you do need to think through it carefully for 10-15 minutes to be able to come up with something coherent. You will never have time to frame a coherent reply in the interview itself. Of course, it is best to have a few situations prepared just so you can change it up a bit, variety never hurt anyone. If the company you're interviewing with is enlightened they won't ask you these questions, but will instead focus on your dev skills, but there are many companies and few are enlightened, might as well prepare for the worst case and be pleasantly surprised if the best case happens.

Coding Questions

Talking about dev skills, the one thing that just about every company that hires developers will do, would be to ask a coding question at some stage. These usually take the form of a sandbox question or what I call a Uni question. You know the ones, "Reverse a list", "Implement a linked list" it's as if they are under the impression you studied computer science at some point, go figure :). People struggle here, because you just don't come across this kind of question in your day-to-day work. If they asked you to implement a Twitter or Facebook clone, you could really show them your chops, but balancing a binary tree – who the hell remembers how to do that? And that's the rub, you probably could dredge the information from the depths of your grey matter, but by the time you do the interview will have been long over. Because you don't do this kind of question daily, you brain has dumped the info you need to tape and sent it to Switzerland (cause backups should be kept off-premises). The answer is simple; you gotta practice these questions well in advance of the interview. Preparation baby, that's the ticket. Preferably you should be doing them regularly regardless of your employment status cause those questions are fun and bite-sized and give your brain a bit of a workout – you'll be a better developer for it. The most interesting thing though is this, you do enough of them and you won't really encounter anything new in an interview. There are really not so many themes when it comes to these questions, it will be the same formulae you'll just need to plug in different numbers (a simplification but not too far from reality). I really gotta follow my own advice here. If you seriously want a leg up, there are books specifically about this, I prefer Cracking the Coding Interview but there is also Programming Interviews Exposed – read them, do the questions.

Puzzles

Mount Fuji questions are the most controversial, but regardless of whether you hate them or not, even they can be practiced. Yeah, alright, maybe you're willing to walk out if any company ever dares to ask you about manhole covers, but I'd much rather answer the questions and then walk out in self-righteous satisfaction rejecting the offers they'll be throwing at my feet, than storm out in self-righteous anger knowing deep down that I was a wuss for doing so. And anyway, I'd like to think that I've already demonstrated that not all Mount Fuji questions are created equal, some are coding problems, others deal with concurrency, others still might be back-of-the-envelope questions (the story of how these originated is actually pretty interesting, I am writing it up as we speak). The subset of questions that are simply a useless puzzle are a lot smaller than you might think. Doing these kinds of questions in your spare time is just another way to build your skills with a side benefit that you become an interview-proof individual. Of course, many people also enjoy an occasional puzzle – I'm just saying.

There is still lots more to say, I haven't even begun to talk about attitude, but this is already a tl;dr candidate, so I'll leave that discussion for another time. Let's sum up, if you feel that you suck at interviews, it's because you didn't prepare well enough and haven't had enough practice – it is that simple. As an interviewer it is most disheartening to see an unprepared candidate, there are just so many of them, on the other hand a person who is clearly on the ball is just awesome. And I am well aware that practicing interviews is hard, there is no Toastmasters equivalent for that particular skill, but thorough preparation can significantly mitigate that issue. Even a few minutes of preparation will put you head and shoulders above most other people since the vast majority don't bother at all. So, take the time to practice/prepare if you have an interview on the horizon, be smart about it and it is bound to pay off, not to mention a better experience for the interviewer as well, more fun and less stress for everyone.

Images by Caro Wallis and louisvolant

Related posts:

1. The Best Way To Interview A Developer
2. How To Answer A Programming Interview Question And Look Good Doing It
3. When A ‘Mount Fuji’ Question Is Not Really A ‘Mount Fuji’ Question (Are You As Smart As You Think You Are)

For a few years now, I've been meaning to read Peter Norvig's old book, "Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp", but every time I started I'd inevitably get lost in the code due to my poor Lisp skills. For some reason I just couldn't absorb the introductory Lisp chapters at the beginning of the book. So a little while ago I decided to "begin at the beginning" and slowly started making my way through Peter Seibel's "Practical Common Lisp".

Inevitably, one of the first things I learned about was the "format" function. Format, is essentially the Lisp equivalent of printf, so you kinda need it to produce the old "Hello World". Just like printf and its ilk, format supports string interpolation via embedded directives. For example if you wanted to print two strings side by side but separate them by a specific number of spaces you could do something like this:

CL-USER> (format t "~a~40t~a~%" "abc" "123")
abc                                     123
NIL

One of the most interesting format directives is ~r which will take an integer and produce its English representation e.g.:

CL-USER> (format nil "~r" 123456)
"one hundred twenty-three thousand four hundred fifty-six"

I found this little gem in one of the footnotes, the lesson here being – always read the footnotes. Anyway, I don't know about you, but I thought that was pretty awesome, which immediately got me thinking about how hard it would be to implement a stand-alone integer to English translation function. I would have loved to try my hand at doing this in Lisp, but I don't think I am sufficiently Jedi for that as yet (I will however give it a go as soon as I am ready, you will not want to miss that :)), so instead I decided to have a go at implementing it in Ruby.

A Totally Unrelated Musical Trivia Interlude

Speaking of Jedi, I've recently been a little obsessed with the "Good Morning" song from "Singing In The Rain", you know the one I mean. I blame "Family Guy" for this, it all started after I watched the episode where they perform this song in one of their postmodern flashes of randomness. Anyway, it's just such a nice and happy song, it's kinda quaint how 1:30 used to be considered "late" in those days and I dig the whole synchronized tap dancing thing that they do (just imagine how much they had to practice to get it right).

Now, here is the trivia, the girl in the song/movie is a 20 year old Debbie Reynolds (did you know that before "Singing In The Rain" she didn't even know how to dance) who went on to marry singer Eddie Fisher. A few years later she gave birth to a daughter named Carrie (i.e. Carrie Fisher) who, in turn, went on to play Princess Leia in "Star Wars". That's how all of this relates to Jedi, and you thought I was going off on a random tangent – now you know better :). Time to get back to some Ruby code.

A Ruby Based Integer To English Converter

It turns out writing it was somewhat harder than I expected because the English language is a little insane when it comes to naming numbers. Everything was going well at the start; it was obvious that we need some kind of lookup table to convert digits to words. The lookup table must contain all the uniquely named numbers that we are likely to encounter.

• all number between 1 and 10 (e.g. one, two, five etc.)
• all number between 11 and 20 (e.g. eleven, twelve, sixteen etc.)
• all multiples of 10 between 20 and 100 (e.g. thirty, forty etc.)
• all uniquely named powers of 2 over 100 (e.g. hundred, thousand, million, billion etc.)

Here is a cut-down version:

{
1 => "one",
2 => "two",
3 => "three",
...
19 => "nineteen",
20 => "twenty",
...
90 => "ninety",
100 => "hundred",
1000 => "thousand",
1000000 => "million",
...
}

We don't really think about it, since we are so used to it, but that is actually a lot more unique numbers than strictly necessary. You can easily identify all possible numbers using just 1 through 9 as well as all the named powers of 10, such as ten, hundred, thousand etc (we'll explore this thought further shortly). Doing it this way would be pretty logical, instead the English speaking world decided that we needed nine special words to represent numbers between 11 and 19 as well as eight more similar, but still unique, words for the multiples of 10 between 20 and 100. As much as we take it for granted this causes all sorts of pain when we try to implement out integer to words converter.

Consider this, we're given an integer several digits long, let's say 12.

• to get a word representation we start looking at the digits of the integer in reverse order (we have to start with the least significant digit first):
  • digits = 21
• we use the look-up table to find the word that represents the first digit and add it to an accumulator (which is a list that will contain all the words in the English representation of our integer):
  • digits = 21, accumulator = [two]

But as soon as we move on to the second digit, we're already in trouble. If this digit is a one, we know we have a number between 11 and 19, so we have to do the following:

• backtrack the previous digit from the accumulator:
  • digits = 21, accumulator = []
• get the current digit along with the previous digit and reverse them to get our actual number:
  • digits = 12, accumulator = []
• do a lookup to get the new word representation and put the new representation in the accumulator:
  • digits = 12, accumulator = [twelve]

The story is similar if the second digit is 2 through 9, we still have to backtrack, then we need to do a lookup on the second digit multiplied by 10 (i.e. 20, 30 etc), combine the result with the word representation of the previous digit and put that back in the accumulator. So if the number is 20, we need to look up 20, combine that with 5 and get twenty five which ends up in the accumulator.

When the number is big enough, this patters comes up again and again every few digits. For example, numbers such as 11000, 23000, 134000 need to be represented as eleven thousand, twenty three thousand and one hundred and thirty four thousand (see what I mean). Luckily it is a pattern so we can handle all occurrences of it as a special case, but it's a pattern that need not be. And talking about patterns that need not be, what is our obsession with the word hundred:

• three hundred and fifty
• one hundred and twenty thousand three hundred and fifty
• one hundred and twenty five million three hundred and twenty thousand five hundred and six

We have the word hundred appearing 3 times in that last one, we're used to it and it feels comfortable, but is it strictly necessary? We have to handle that one as a special case as well. Needless to say, the code ends up being long and ugly, you can have a look at the full source here, but the main chunk of it is something along the following lines:

  def convert(number)
    return "zero" if number == 0
    word_representation_accumulator = []
    number_digits_reversed = number.to_s.reverse
    digit_count = 0
    number_digits_reversed.chars.each_with_index do |digit, index|
      digit_as_number = Integer(digit)
      skip_zero(digit_as_number) do
        if digit_count == 0
          word_representation_accumulator << "#{NTW[digit_as_number]}"
        elsif ten_to_twenty?(digit_as_number, digit_count)
          backtrack word_representation_accumulator
          actual_number = Integer("#{digit}#{number_digits_reversed[index - 1]}")
          multiplier = (digit_count > 1 ? 10**(digit_count - 1) : nil)
          word_representation = "#{NTW[actual_number]}"
          word_representation += " #{NTW[multiplier]}" if multiplier
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        elsif twenty_to_one_hundred?(digit_count)
          backtrack word_representation_accumulator
          multiplier = (digit_count > 1 ? 10**(digit_count - 1) : nil)
          lookup_number = digit_as_number * 10
          word_representation = "#{NTW[lookup_number]}"
          word_representation += " #{NTW[Integer(number_digits_reversed[index - 1])]}"
          word_representation += " #{NTW[multiplier]}" if multiplier
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        elsif digit_count == 2 || digit_count % 3 == 2
          multiplier = 10**2
          word_representation = "#{NTW[digit_as_number]} #{NTW[multiplier]}"
          word_representation += " and" if word_representation_accumulator.size != 0
          word_representation_accumulator << word_representation
        else
          multiplier = 10**digit_count
          word_representation = "#{NTW[digit_as_number]} #{NTW[multiplier]}"
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        end
      end
      digit_count += 1
    end
    word_representation_accumulator.reverse.join(" ")
  end

You can have a go at running it, but don't forget, I only took the lookup table up to trillions, so if you want to try numbers bigger than that you will need to add more named powers of ten (such as quadrillion, quintillion etc.) to the table. Here is some sample output:

315119 - three hundred and fifteen thousand one hundred and nineteen
1000001 - one million and one
1315119 - one million three hundred and fifteen thousand one hundred and nineteen
11315119 - eleven million three hundred and fifteen thousand one hundred and nineteen

Using Code To Derive The English That Should Have Been

Even though my code was producing reasonable output, I wasn't entirely happy, the arbitrary nature of the English language made my code uglier than it could have been. Since I've taken liberties with the English language before I decided this was a good time to do it again. What if we were to remove all the extraneous words that English had for numbers. Surely, the numbers 1 through 9 are more than sufficient? This would be the simplest possible case e.g.:

135 - one three five
3619 - three six one nine

Unfortunately it just doesn't cut it. Firstly we would have to introduce 0 as a non-silent number e.g.:

609 - six zero nine

Currently, zero is completely silent in all numbers unless it is by itself e.g.:

609 - six hundred and nine (see, zero is silent)

But even if this wasn't an issue, it turns out we actually need the named powers of ten to make English representations of integers meaningful. One five six two three, tells us almost nothing, but fifteen thousand six hundred and twenty three gives us a lot of information instantly. Even when we haven't processed the number fully, we know straight away that it is approximately 15 thousand and a few hundred. The bigger the number gets, the more pronounced this "estimation" effect is. So, we need numbers one through nine as well as named powers of 10. This allows us to cut our lookup table down to the following:

  NTW = {
  1 => "one",
  2 => "two",
  3 => "three",
  4 => "four",
  5 => "five",
  6 => "six",
  7 => "seven",
  8 => "eight",
  9 => "nine",
  10 => "ten",
  100 => "hundred",
  1000 => "thousand",
  1000000 => "million",
  1000000000 => "billion",
  1000000000000 => "trillion"
  }

We can use this table to write code that is much more intuitive than our previous attempt. Infact, we don't even need to know exactly what we're trying to achieve, instead we let the code guide us to the "correct" solution. We're using code to derive the requirements for the real world which is the opposite of the usual scenario. The full implementation I came up with is in this gist, but here is the main bit:

  def convert(number)
    return "zero" if number == 0
    word_representation_accumulator = []
    number_digits_reversed = number.to_s.reverse
    digit_count = 0
    number_digits_reversed.chars.each_with_index do |digit, index|
      digit_as_number = Integer(digit)
      skip_zero(digit_as_number) do
        multiplier = 10**digit_count
        word_representation = "#{NTW[digit_as_number]}"
        word_representation += " #{NTW[multiplier]}" if multiplier > 1 && NTW[multiplier]
        word_representation_accumulator << word_representation
      end
      digit_count += 1
    end
    word_representation_accumulator.reverse.join(" ")
  end

You have to admit, it's much shorter and nicer looking and here is some of the output produced:

0 - zero
1 - one
3 - three
5 - five
11 - one ten one
15 - one ten five
25 - two ten five
71 - seven ten one
40 - four ten
100 - one hundred
101 - one hundred one
112 - one hundred one ten two
123 - one hundred two ten three
457 - four hundred five ten seven
999 - nine hundred nine ten nine
1000 - one thousand
1001 - one thousand one
1010 - one thousand one ten
1011 - one thousand one ten one
2117 - two thousand one hundred one ten seven
3001 - three thousand one
13101 - one three thousand one hundred one
14001 - one four thousand one
16000 - one six thousand
25119 - two five thousand one hundred one ten nine
65009 - six five thousand nine
315119 - three one five thousand one hundred one ten nine
1000001 - one million one
1315119 - one million three one five thousand one hundred one ten nine
11315119 - one one million three one five thousand one hundred one ten nine
74315119 - seven four million three one five thousand one hundred one ten nine
174315119 - one seven four million three one five thousand one hundred one ten nine
1174315119 - one billion one seven four million three one five thousand one hundred one ten nine
15174315119 - one five billion one seven four million three one five thousand one hundred one ten nine
35174315119 - three five billion one seven four million three one five thousand one hundred one ten nine
935174315119 - nine three five billion one seven four million three one five thousand one hundred one ten nine
2935174315119 - two trillion nine three five billion one seven four million three one five thousand one hundred one ten nine

As you can see, all the named powers of ten are now treated in exactly the same way i.e.:

• 10 is ten to the power of 1
• 100 is ten to the power of 2
• etc.

So 101 is one hundred one and 11 is one ten one, 203 is two hundred three, while 23 is two ten three – logical isn't it? There is no longer any need for any specially named numbers between 10 and 100 since we can represent all of them just as efficiently with this notation; this means no more special cases for numbers under 100. The other one we had was all the extra usages of the word hundred. We simply eliminate them all together (except for when we are talking about numbers between 100 and 1000), three one five thousand conveys the same amount of information as three hundred and fifteen thousand – the word hundred is totally redundant. Now, every named power of 10 appears only once in the English representation of the integer which allows us to still retain the ability to "estimate" the magnitude instantly without any extraneous information:

one million three one five thousand one hundred one ten nine

Short, consistent and to the point. It does seem a little awkward at first, but after a few minutes it starts to grow on you – after all, it is much more logical than the system we have now. There you go, deriving "better" English through some Ruby code. Not only do we get superior language but it is also easier, faster and less error prone to code it – FTW brothers, FTW :)!!!

Image by plindberg

Related posts:

1. Tweaking English For Fun And Profit … Facilitating Poetry
2. Here Are Some Words That Rhyme With Orange!
3. Timing Ruby Code – It Is Easy With Benchmark

One of my friends always asks that question when interviewing developers. Apparently it’s quite ambiguous and many people misunderstand – which is curious since I thought it was rather straight forward, but that’s not what this story is about.

When he first told me about this question my brain immediately went ahead and tried to solve it, as your brain probably did as soon as you read the title of this post, if you’re a developer :). After thinking about it for a couple of minutes I said that people should get "extra points" if their function uses bit hackery to solve the problem. I later realised that the most interesting thing about this was how I arrived at that conclusion.

The First Thing I Thought Of Was…

Something along the lines of the following:

def power_of_2?(number)
 return false if number == 0
 while(number % 2 == 0)
   number = number / 2
 end
 return false if number > 1
 true
end

Of course it didn’t spring forth out of my head fully formed like that, but the general gist was the same. This code solves the problem and, as you can see it is an iterative solution. The first programming language I learned was Java, the second was C, so you might say I was weaned on the “iterative approach”. So, whenever I am presented with a new problem, my mind always gropes for the iterative solution first. You might say I find it the most “natural” way to solve a problem.

The Second Thing I Though Of Was…

Something that looked like this:

def power_of_2?(number)
 return true if number == 1
 return false if number == 0 || number % 2 != 0
 power_of_2?(number / 2)
end

Once again, it solves the problem, but this time recursively. Since those early days of Java and C, I’ve played around with a whole bunch of languages, some just as imperative, but others were functional or had functional capabilities. In such languages, recursion is the norm or at least a lot more prevalent. I find that I really like recursive solutions, it is often a very elegant way to get around some ugly code. Even though it is not the first stop my brain makes when it comes to solving programming problems, I find that these days I almost always consider if there might be a recursive way to approach a problem. I don’t yet always instinctively feel if a problem has a recursive answer, but in many cases (like this one) it is fairly simple. As long as you can divide the initial problem into two smaller parts which are “equivalent” to the original problem, you can solve it recursively (like when you split a tree you get two smaller trees).

I do wonder if programmers who were “weaned” on functional languages would go for the recursive solution first and if they find one do they bother to consider an iterative one at all? If you’re such a developer, please share how you think.

The Next Thing I Thought Of Wasn’t Code

It is only recently that I have started to give bit hacking the attention it deserves. It always used to seem like it wasn’t worth the trouble, but since I’ve learned a bit more about Bloom Filters (I’ll write it up one of these days, hopefully make it a bit easier to grok) and finally got my hands on a copy of “Programming Pearls”, I’ve become a bit of a convert. So, whenever I hear “power of 2” or anything similar these days, I always think that there is surely some bit hacking to be done :), which is exactly what my brain latched on to after the iterative and recursive approaches.

Consider that any number that is a power of 2 has exactly one bit set in its binary representation e.g.:

2    =  00000010
4    =  00000100
8    =  00001000
16   =  00010000
256  = 100000000

If we subtract 1 from any of these numbers we get the following:

2 - 1 = 1 = 00000001
4 - 1 = 3 = 00000011
8 - 1 = 7 = 00000111

Every bit that was less significant than the original interesting bit (the one that was set), is now set while the original bit is unset. If we now do a bitwise and (& operator) on the original number and the number which results when 1 is subtracted, we always get zero:

2 & 1 = 00000010 & 00000001 = 0
8 & 7 = 00001000 & 00000111 = 0

This will only happen if a number is a power of two. Therefore we can write the following code:

def power_of_2?(number)
 number != 0 && number & (number - 1) == 0
end

This is apparently a pretty well known way to determine if a number is a power of 2. In the olden days when computing resources were scarce, every programmer probably knew about this shortcut and others like it, these days – not so much. But, you have to admit it is by far the cleanest solution of the three, even the need to treat zero separately makes it only marginally less elegant. Definitely a handy thing to remember (it does still come up occasionally in the real world).

I do wonder though, is anyone’s brain sufficiently indoctrinated into bit hackery that they would jump to this solution first without even considering an iterative or a recursive one? Anyone?

If Someone Ever Actually Asks You This In An Interview…

The first thing to do would be to write (or at least mention) some tests. They don’t have to be proper unit tests in this case (although for more complex questions it may be warranted), but you will never go wrong if you show that you’re aware of testing. In this case something along the lines of this is probably fine:

puts "fail 2" if !power_of_2? 2
puts "fail 4" if !power_of_2? 4
puts "fail 1024" if !power_of_2? 1024
puts "fail 1" if !power_of_2? 1
puts "fail 1025" if power_of_2? 1025
puts "fail 0" if power_of_2? 0
puts "fail 3" if power_of_2? 3

0,1,2 and 3 are the cases where our function is likeliest to break the rest are included for completeness. The other thing that may be worth mentioning is the fact that the behaviour of the function for negative integers or floats is undefined, you can of course handle those cases, but it adds extra complexity and I think simply showing that you’re aware of them is enough.

After this you can go ahead and write your function, remember – bit hackery means extra points (as far as I am concerned anyway :)).

Image by .m for matthijs

Related posts:

1. Writing A More Ruby-ish Array Intersection Function And Sorting Structs
2. How To Write A Simple Web Crawler In Ruby
3. Are You Using The Full Power Of Spring When Injecting Your Dependencies?