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:

[(http://feeds.feedburner.com/softwaretechandmore)]

Iteration 2:

[(http://feeds.feedburner.com/softwaretechandmore), [-3], [1, -3]]

Iteration 3:

[(http://feeds.feedburner.com/softwaretechandmore), [-3], [1, -3], [2], [1, 2], [-3, 2], [1, -3, 2]]

Iteration 4:

[(http://feeds.feedburner.com/softwaretechandmore), [-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:

[] + (http://feeds.feedburner.com/softwaretechandmore)

Iteration 2:

(http://feeds.feedburner.com/softwaretechandmore) + [-3], [1, -3]

Iteration 3:

(http://feeds.feedburner.com/softwaretechandmore), [-3], [1, -3] + [2], [1, 2], [-3, 2], [1, -3, 2]

Iteration 4:

(http://feeds.feedburner.com/softwaretechandmore), [-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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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 (__). All we need to do now is pick out the ones that we’re after.

1
2
3
4
5
6
7
8

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

def initialize_first_row
    @matrix(http://feeds.feedburner.com/softwaretechandmore).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(http://feeds.feedburner.com/softwaretechandmore)[0]] == @matrix[0][i] # the only sum we can have is the first number itself
        @matrix(http://feeds.feedburner.com/softwaretechandmore)[i] = "T";
      end
    end
    @matrix
  end

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9

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

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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**:

```ruby
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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:

```ruby
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:

```ruby
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:

```ruby
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:

```ruby
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

“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