[SUMMARY] Programmer Ping-Pong (#150)

R

Ruby Quiz

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:

#!/usr/bin/env ruby -wKU

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

Rick DeNatale

As of James Koppel's first response, the code has gone through 15 rounds of
revision, not counting forks.

Should that be either last or latest? As far as I know, I was the
first respondent.
 
J

James Gray

Should that be either last or latest? As far as I know, I was the
first respondent.

Note the possessive: "James Koppel's first response."

James Edward Gray II
 
P

Paul Irofti

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.

I loved this quiz, I had a lot of work to do this week so I missed out
on the ending but I'd definitely love to see more quizzes like this.
 
J

James Gray

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.

The holiday and an unexpected illness are slowing me down folks. Give
me one more week to recover and I promise to get the quiz back on its
feet.

James Edward Gray II
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top