TITLE: At Some Point, You Gotta Know Stuff
AUTHOR: Eugene Wallingford
DATE: April 22, 2010  8:36 PM
DESC: 
-----
BODY:
A couple of days ago, someone tweeted a link to
<A HREF="http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/">
   Are you one of the 10% of programmers who can write a binary search?</A>,
which revisits a passage by Jon Bentley from twenty-five
years ago.  Bentley observed back than that 90% of
professional programmers were unable to produce a
correct version of binary search, even with a couple of
hours to work.  I'm guessing that most people who read
Bentley's article put themselves in the elite 10%.

Mike Taylor, the blogger behind The Reinvigorated
Programmer, challenged his readers.  Write your best
version of binary search and report the results: is
it correct or not?  One of his conditions was that
you were not allowed to run tests and fix your code.
You had to make it run correctly the first time.

Writing a binary search is a great little exercise,
one I solve every time I teach a data structures
course and occasionally in courses like CS1,
algorithms, and any programming language- or
style-specific course.  So I picked up the gauntlet.

You can see my solution in a
<A HREF="http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/#comment-2222">
   comment on the entry</A>,
along with a sheepish admission: I inadvertently
cheated, because I didn't read the rules ahead of
time!  (My students are surely snickering.)  I
wrote my procedure in five minutes.  The first
test case I ran pointed out a bug in my stop
condition, <B><TT>(&gt;= lower upper)</TT></B>.
I thought for a minute or so, changed the condition
to <B><TT>(= lower (- upper 1))</TT></B>, and the
function passed all my tests.

In a sense, I cheated the intent of Bentley's
original challenge in another way.  One of the
errors he found in many professional developers'
solution was an overflow when computing the midpoint
of the array's range.  The solution that popped into
my mind immediately, <B><TT>(lower + upper)/2</TT></B>,
fails when <B><TT>lower + upper</TT></B> exceeds the
size of the variable used to store the intermediate
sum.  I wrote my solution in Scheme, which handle
bignums transparently.  My algorithm would fail in
any language that doesn't.  And to be honest, I did
not even consider the overflow issue; having last
read Bentley's article many years ago, I had
forgotten about that problem altogether!  This is
yet another good reason to re-read Bentley occasionally
-- and to use languages that do heavy lifting for you.

But.

One early commenter on Taylor's article said that the
no-tests rule took away some of my best tools and his
usual way of working.  Even if he could go back to
basics, working in an unfamiliar probably made him
less comfortable and less likely to produce a good
solution.  He concluded that, for this reason, a
challenge with a no-tests rule is not a good test of
whether someone is a good programmer.

As a programmer who prefers an agile style, I felt
the same way.  Running that first test, chosen to
encounter a specific possibility, did exactly what I
had designed it to do: expose a flaw in my code.  It
focused my attention on a problem area and caused me
to re-examine not only the stopping condition but
also the code that changed the values of
<B><TT>lower</TT></B> and <B><TT>upper</TT></B>.
After that test, I had better code and more confidence
that my code was correct.  I ran more tests designed
to examine all of the cases I knew of at the time.

As someone who prides himself in his programming-fu,
though, I appreciated the challenge of trying to
design a perfect piece of code in one go: pass or
fail.

This is a conundrum to me.  It is similar to a comment
that my students often make about the unrealistic
conditions of coding on an exam.  For most exams,
students are away from their keyboards, their IDEs,
their testing tools.  Those are big losses to them,
not only in the coding support they provide but also
in the psychological support they provide.

The instructor usually sees things differently.  Under
such conditions, students are also away from Google
and from the buddies who may or may not be writing
most of their code in the lab.  To the instructor,
This nakedness is a gain.  "Show me what you can do."

Collaboration,
<A HREF="http://scrapheap-challenge.com/">
   scrapheap programming</A>,
and search engines are all wonderful things for
software developers and other creators.  <EM>But at
some point, you gotta know stuff</EM>.  You
<EM>want</EM> to know stuff.  Otherwise you are doomed
to copy and paste, to having to look up the interface
to basic functions, and to being able to solve only
those problems Google has cached the answers to.
(The size of that set is growing at an alarming rate.)

So, I am of two minds.  I agree with the commenter
who expressed concern about the challenge rules.
(He posted good code, if I recall correctly.)  I also
think that it's useful to challenge ourselves regularly
to solve problems with nothing but our own two hands
and the cleverness we have developed through practice.
Resourcefulness is an important trait for a programmer
to possess, but so are cleverness and meticulousness.

Oh, and this was the favorite among the ones I read:

<BLOCKQUOTE><EM>
I fail.  ...  I bring shame to professional programmers
everywhere.
</EM></BLOCKQUOTE>

Fear not, fellow traveler.  However well we delude
ourselves about living in a
<A HREF="http://en.wikipedia.org/wiki/Lake_Wobegon">
   Garrison Keillor world</A>,
we are all in the same boat.
-----