Programmer Ping-Pong (#150)

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 S.", 1], ["James K.", 2], ["Rob B.", 

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 K.'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 Q. this week in celebration of the Christmas
holiday. I
wish you all a Merry Christmas and I’ll talk to you again next week.

On 12/20/07, Ruby Q. [email protected] wrote:

As of James K.'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.

Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

On Dec 20, 2007, at 9:48 AM, Rick DeNatale wrote:

On 12/20/07, Ruby Q. [email protected] wrote:

As of James K.'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.

Note the possessive: “James K.'s first response.”

James Edward G. II

On 2007-12-20, Ruby Q. [email protected] wrote:

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.

On Dec 20, 2007, at 11:04 AM, James G. wrote:

James Edward G. II

Rick, Read it without the word “first” and then think of future-
proofing for another response (or two) from James K…

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

On Dec 20, 2007, at 7:36 AM, Ruby Q. wrote:

There will be no Ruby Q. 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 G. II

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs