Semergence

I’ve been a fan of Iron Chef America for a while. Fast paced and some very interesting dishes, it’s entertaining and even a bit educational (for the epicurean viewer).

Being a geek at heart, it leaves me wondering what it would take to create an Iron Coder competition. With the right “ingredients” it just might work.

First, we’d need a play-by-play announcer and a color commentator. On Iron Chef America, this single role is played by Alton Brown. We might be able to get away with a single person, but I often like the banter of two announcers. It is, of course, their job to explain what is going on and provide insight and entertainment during the battle.

There is, of course, the Secret Requirement. This brings us to the question of what type of code are the two Iron Coders creating? I come from a web application background, so this is my first assumption. You can’t pit an X-Box programmer against a Perl script kiddie. For now, let’s stick with building simple web applications. I don’t think we restrict to a particular technology. In fact, part of the fun would be to watch a Rails expert go head to head against a .NET expert.

As for the Secret Requirement, this can go one of two ways. Option A would be to mandate a large scope for the application. For instance, “Build a Time Card application!!!” The particulars are left up the Iron Coders. Perhaps there are a very small set of requirements handed down, like “user clocks in” and “user clocks out” and “manager pulls report of this week’s time”

Option B for Secret Requirement would mandate a very small requirement, such as “must use the visitor pattern and two factory pattern implementations!!!” This would let the Iron Coders build whatever they like, as long as they use the Secret Requirement. This more closely matches the original Iron Chef in intent, but how easy is it to create these small requirements? Do they provide enough constraint for the Iron Chefs?

I’m going to lean towards Option A, specifying a broad, yet simple, application domain. Leave the particulars up to the Iron Chefs.

Next up we have Judging. This is where it gets interesting, as need to decide how to choose a winner. In Iron Chef America, they judge the dishes with a point scale across three categories: Originality, Taste, Presentation. For Iron Coder, I’d propose the categories to be Originality, Accuracy, and Construction. Let me explain:

Originality would be the judge’s take on how original the Iron Coder implemented the Secret Requirement. The more interesting, unique, surprising the Coder’s web application, the more points here.

Accuracy is measuring the correctness of the application. This one is tough because there may not be that many formal specs, but given that Accuracy is a judging category, we might need them. In any case, Accuracy measures if the application functions properly. If any bugs or inconsistencies are encountered, points are lost here.

And finally Construction, which is measuring the quality and beauty of the code itself. This is a lot like porn: you know it when you see it. Is the code DRY? Does it use patterns appropriately? Does it follow good OO design? Is it a hack, or is it beautiful? If anything, this category is too broad. In any case, it’s very important and must be judged.

Logistics is something I worry about. Watching people write code isn’t exactly exciting, but I think this even should be live. I’d like to emulate a live studio audience, where viewers can chat along with the action. However, I don’t think the Iron Chef’s should be able to watch the chat (not sure how you’d accomplish that one) This is my biggest unknown. What’s a good screen sharing program? How do we deal with small font sizes? Are there any editors that provide a real-time link (SubEthaEdit comes to mind for collaborative editing)?

Finally, it has to be campy. This should be fun for Iron Coders and viewers alike. I think if we can figure out the logistics issues of actually broadcasting text editors, it could be a fun event.

Coding Horror: Size Is The Enemy

Java is like a variant of the game of Tetris in which none of the pieces can fill gaps created by the other pieces, so all you can do is pile them up endlessly.

If you’ve been reading Beautiful Code, and I hope you have, you should also read Donald Knuth’s Computer Programming as an Art. It actually makes you feel better about writing all that code and always trying to get it right.

The possibility of writing beautiful programs, even in assembly language, is what got me hooked on programming in the first place.

Well, thanks to the many people (here and here) that provided their versions of an erlang way to calculate combinations, I’ve really begun to open my mind to how to think functionally.

To help me understand what is going on, I’ve converted the basic idea into a Ruby version of calculation combinations. This uses recursion like the erlang versions do.

class Array
  def head_tail
    [self.first, self.tail]
  end

  def tail
    self[1,self.size-1]
  end
end

def combos(list)
  return [[]] if list.empty?
  h, t = list.head_tail
  t_combos = combos(t)
  t_combos.inject([]) {|memo, obj| memo << [h] + obj} + t_combos
end

c = combos([1,2,3,4])
require 'pp'
pp c

As you can see, I added a bit of erlangism to the Array class, by adding a method to get the head and tail of an array.

Let’s run through this.

On the first call to combos([1,2,3,4]) we jump over the first line (the exit in our recursion). We generate the head and tail, which in this case is 1 and [2,3,4] respectively. We immediately begin our recursion by saying, “Get me all the combinations for the tail, which is essentially everything but the head.” Then, for each of those combinations, we append the head (again, here it’s 1). Finally, we add all of the rest of the combinations and return the array of arrays.

Another way to explain it might be:

1. H = Remove an element from the list.
2. T = The rest of the list.
3. C = Calculate the combinations of T (recursion happens here).
4. C2 = For each combination in C, generate a new combination by appending H.
5. return C2 + C

If you recall, I wrote some Ruby code to calculate combinations of values in lists. I needed to create a list of all combinations of values, where each combination had between 0 and N number of values, where N is equal to length of the source list. (I’m not sure I’m explaining that correctly, but refer to my previous post for examples).

Here’s my first shot at how to do this in erlang. It look longer to find math:pow and how to convert a float to an integer in erlang than to write the actual code.

-module(s).
-export([combos/1]).

combos(L) -> combos(L, bit_masks(length(L))).

combos(L, [BH|BT]) ->
  [mask_list(L, BH)|combos(L, BT)];
combos(_, []) -> [].

mask_list([H|T], [BH|BT]) ->
  case (BH) of
    1 -> [H|mask_list(T, BT)] ;
    0 -> mask_list(T, BT)
  end;
mask_list([], []) -> [].

bit_masks(NumColumns) ->
  bit_masks(0, round(math:pow(2, NumColumns))-1, NumColumns).

bit_masks(Max, Max, NumColumns) ->
  [padl(NumColumns, bl(Max))];

bit_masks(X, Max, NumColumns) ->
  [padl(NumColumns, bl(X)) | bit_masks(X+1, Max, NumColumns)].

padl(N, L) when N =:= length(L) -> L ;
padl(N, L) when N > length(L) -> padl(N, [0|L]).

bl(N) -> bl(N, []).

bl(0, Accum) -> Accum;
bl(N, Accum) -> bl(N bsr 1, [(N band 1) | Accum]).

Brief explanation:

The bl function creates a “bit list”, given a number and an accumulator. So, bl(5,[]) will return [1,0,1].

The padl function pads the list, which is useful when you want to ensure that all combinations ultimately have the same length. So, padl(4, [0]) would return [0,0,0,0].

And then bit_masks creates a list of bit masks which we’ll use to create the combinations. For example, bit_masks(4) returns:

[[1,1,1,1],
 [1,1,1,0],
 [1,1,0,1],
 [1,1,0,0],
 [1,0,1,1],
 [1,0,1,0],
 [1,0,0,1],
 [1,0,0,0],
 [0,1,1,1],
 [0,1,1,0],
 [0,1,0,1],
 [0,1,0,0],
 [0,0,1,1],
 [0,0,1,0],
 [0,0,0,1],
 [0,0,0,0]]

And finally, to create the actual combinations, you will use combos. Example: combos([a,b,c,d]). This generates a result of:

[[],
 [d],
 [c],
 [c,d],
 [b],
 [b,d],
 [b,c],
 [b,c,d],
 [a],
 [a,d],
 [a,c],
 [a,c,d],
 [a,b],
 [a,b,d],
 [a,b,c],
 [a,b,c,d]]

So, is there a more erlang way to do this?

As I continue to tinker with Scala, I was wondering about the performance differences between an Array and List. This post will detail what I’ve found, but as always YMMV and I could be doing it all wrong. If there’s a better (in this case, better == faster) way to do this in Scala, please let me know.

My application performs a lot of collection iteration as it combines the values of two collections into a new collection by addition. For instance, I need to combine [1,2] and [3,4] into [4,6]. I wanted to find out if the collections should be an Array or List.

Intuition tells me that the Array will perform better, but this is Scala, and Lists reign supreme. So we’ll go head to head.

For each test, I wanted to write a function that combined the two collections using tail recursion.

Test One - Two Lists Into a Third

First up, I am adding two lists together while forming a third. One problem here is, due to the way the algorithm is structured, the resulting list is built backwards. So there’s a call to reverse at the end. (Question: How to rewrite this using normal List methods such as :: without having to call reverse at the end?)

  def add(x: List[Long], y: List[Long],
             agg: List[Long]): List[Long] = x match {
    case Nil => agg.reverse
    case x1 :: xs => y match {
      case y1 :: ys => add(xs, ys,  x1 + y1 :: agg)
    }
  }

To call it:

add(List(1,2), List(3,4), Nil)

Test Two - Two Arrays Into a List

Next up, I add two Arrays into a List. The guess here is that accessing the arrays by index will help speed it up.

  def add2(x: Array[Long], y: Array[Long], agg: List[Long],
               counter: Int): List[Long] = {
    if (counter == 0) agg
    else add2(x, y, x(counter-1) + y(counter-1) :: agg, counter-1)
  }

To call it:

add2(Array(1,2), Array(3,4), Nil, 2)

Test Three - Two Arrays Into a Third Array

This should be the fastest.

  def add3(x: Array[Long], y: Array[Long], agg: Array[Long],
               i: Int): Array[Long] = {
    if (i == x.length) agg
    else {
      agg(i) = x(i) + y(i)
      add3(x, y, agg, i+1)
    }
  }

To call it:

add3(Array(1,2), Array(3,4), new Array(2), 0)

Methodology

I ran each function 1 million times and captured the times with System.currentTimeMillis. I ran the entire test suite five times to generate an average. I am running Scala 2.5.1 on Java 1.6 on Windows XP. I have a Pentium 4 2.8GHz with 2GB RAM.

Results

The results are in, and sure enough, on average, the third option (pure Arrays) is the fastest.

* Test 1 - 1172 ms
* Test 2 - 781 ms
* Test 3 - 687 ms

So, for my purposes, using Arrays results in faster execution. However, if you are looking to do traditional functional programming, you should write your methods to create zero side effects. Using Arrays like this seems anti-functional programming.

I was looking for a way to create combinations of things in Ruby and I found an article by Uncle Bob detailing his attempt at writing a combination generator in Ruby. I modified it slightly to use an array of items, instead of simple indexes.

require 'pp'

def choose(n, k)
  return [[]] if n.nil? || n.empty? && k == 0
  return [] if n.nil? || n.empty? && k > 0
  return [[]] if n.size > 0 && k == 0
  c2 = n.clone
  c2.pop
  new_element = n.clone.pop
  choose(c2, k) + append_all(choose(c2, k-1), new_element)
end

def append_all(lists, element)
  lists.map { |l| l << element }
end

all = [:a, :b, :c, :d]

pp choose(all,3)

The above code prints out:

[[:a, :b, :c], [:a, :b, :d], [:a, :c, :d], [:b, :c, :d]]

If you don’t want these types of combinations, there is a Ruby library for calculating Permutations which will give you all the different permutations, or orderings, of a set of things.

ModelViewController.mp3 (audio/mpeg Object) should be on everyone’s playlist.