This is a non-traditional Ruby Quiz that changes the rules of the contest. Please read the entire message before playing along. We will be back to normal quizzes next time, for those that end up missing them.
The Game
Eric Hodel described Programmer Ping-Pong in his RubyConf 2007 presentation. I wasn't familiar with the concept before that and it sounds like fun, so let's all try it out together.
The rules are:
* This quiz does not have a no-spoiler period so you may
submit at anytime after reading this message
* I'll make the initial serve, starting the quiz off with
a single failing test
* Anyone can return the ball at anytime by doing exactly
two things, in order: make all tests pass including the
recently added failure and then add a new failing test
of your own
I want to see if we can build an entire library using just that process.
The Task
Let's build a pure Ruby binary AVL tree. An AVL tree is a self-balancing binary tree data structure where insertion, deletion, and lookup all take O(log n) time to execute. This is handy to have for many search problems that must run quickly. It can also be used to build constructs like an OrderedHash.
You can read more about AVL trees on Wikipedia:
There's also a handy document describing their rotations in detail:
What features our AVL tree will support will be decided by you as you write tests. Here are some suggestions of things we might try though, just to get you thinking:
* Support for custom Ruby objects as nodes of the tree
* The ability to customize the comparison code, perhaps with a block
* A String output visualizer, possibly for the inspect() method
* Any other great features you can think of to add
The Details
We will have two files: avl_tree.rb and test_avl_tree.rb. Please pass both files in each submission email you make for this quiz. Let's not complicate this with directory structures or zip files.
Please don't add any external dependencies, unless it's a standard library. We want everyone to be able to easily run this code and play along.
We are using Test::Unit instead of RSpec, or any other tool, for similar reasons.
Please keep your tests short. Under 10 lines is preferred, but don't go over 24.
Also try to test just one aspect of the implementation with each test. I did purposely say "aspect" and not "method." I do test more than one method in the serve and I can imagine other scenarios where it could be useful, like checking support for a handful of the standard Enumerator methods.
You can refactor any code as needed provided you do not change its function and all tests still pass after you do so.
Adds comments if you need to, but writing code that needs no comment would be even better.
Let's use some simple spacing conventions to keep all of us on the same page. Indent two space and do not use tabs. Break up long lines so they do not exceed 80 characters.
Finally, this quiz has the potential to be very chaotic. Take pity on your quizmaster who must track this process and on the rest of the community who may be bothered by a highly active thread. I suggest good email manners:
* Use your client's "Reply" feature and make sure you are replying to
the message that contains the test you made pass
* Trim any unneeded context from the reply, including the previous
version of the code since you will be including the current copy
of the whole thing
* Kindness to your fellow programmers trumps any listed guidelines
The Serve
The initial contents of avl_tree.rb are:
class AVLTree
end
The test file, test_avl_tree.rb, begins as:
require "test/unit"
require "avl_tree"
class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end
def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
@tree << 3
assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end
end
Quiz Summary
This quiz was definitely more about the process than what we produced. For the record though, I do feel what we produced was quite successful. We have built a full AVL Tree implementation in under a week. It may still have a bug or two we haven't eliminated, but it's certainly usable. Let me prove that to you.
Here is the start of an ordered Hash implementation I said would be possible with a working AVL tree. Unlike Ruby 1.9's built-in Hash ordering, this class orders pairs by their key instead of their insertion order:
require "avl_tree"
class KeyOrderedHash
Pair = Struct.new(:key, :value) do
def <=>(other)
key <=> other.key
end
end
include Enumerable
def initialize
@pairs = AVLTree.new
end
def [](key)
@pairs[Pair.new(key)].value
end
def []=(key, value)
@pairs << Pair.new(key, value)
end
def each
@pairs.each { |pair| yield pair.to_a }
end
end
if __FILE__ == $PROGRAM_NAME
require "pp"
names = KeyOrderedHash.new
%w[ Rob\ Biedenharn
Adam\ Shelly
James\ Koppel ].each_with_index do |name, i|
names[name] = i
end
pp names.to_a
# >> [["Adam Shelly", 1], ["James Koppel", 2], ["Rob Biedenharn", 0]]
end
Note how the pairs here come out in key order, instead of the insertion order shown by their values.
The process was also pretty successful. Some felt email was a poor medium to conduct this kind of experiment and they were probably right. Rob Biedenharn came to our rescue though with two simple tools for embedding and extracting the code from an email. Together these two tools were under 40 lines of code and they helped a lot. Nice problem solving, Rob.
We did see quite a bit of forking early on, but in the end a single branch of the code seemed to dominate. Solvers were good about incorporating the changes of others though, so I didn't really feel like this aspect affected the results much.
As of James Koppel's first response, the code has gone through 15 rounds of revision, not counting forks. In that time, we generated right around 500 lines of code including the tests. I was pretty impressed by all of that.
Obviously, the largest aspect of this quiz was the game of Test Driven Development. That too was interesting to watch unfold. Tests were edited, commented out, and reinstated all at various times during the exercise. This happens all the time in normal development of course, but it's different when you are doing these things to someone else's tests.
It's my opinion that the testing got off track a bit early on when we tried to do height testing before we really had a height to test. A few early height tests eventually caused this method to crop up inside AVLTree:
def height
(Math.log(@contents.size + 1) / Math.log(2)).round
end
# ...
While that does reflect accurate results for what we were trying to accomplish, it really doesn't have anything to do with our tree. It just proves that we figured out the math. This is one place where I feel the concept of only-do-what's-needed-to-pass-the-tests breaks down. This code just has to be rewritten at some point, so there's not much benefit to bypassing a test with it, in my opinion.
Another area where we had trouble with the tests was in trying to measure the speed of something. None of us could come up with a great way to test for whether and insert operation was O(n) or O(log n) or something else entirely. One poster suggested that test driving algorithms wasn't very effective and, while I'm not sure I fully agree with that, this is definitely one of the problem cases.
All in all though, the process was a big success and we produced great results. I encourage everyone to read through the quiz thread and see how our work evolved. Thanks for indulging me in my desires to try something a little different.
There will be no Ruby Quiz this week in celebration of the Christmas holiday. I wish you all a Merry Christmas and I'll talk to you again next week.
