Re: A critique of test-first...

• Previous message: Thomas Lotze: "Re: Choosing a language for an OO design"
• In reply to: Jeff Grigg: "Re: A critique of test-first..."
• Next in thread: CTips: "Re: A critique of test-first..."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Mon, 22 Nov 2004 08:42:57 -0500

Jeff Grigg wrote:

> Not long ago (relatively speaking ;-) I was given a short coding
> assignment to complete for an interview. (I and others thought it was
> silly to give a coding test to people of our level; but that's another
> issue. ;-) The task was to write a small utility to display random
> "Magic Eight Ball" answers, selected from a user-configurable set,
> with user-defined probabilities for each. I wrote mine using Test
> Driven Development techniques. The client said that this was the best
> implementation they had ever seen. While they found serious design
> limitations and bugs in all other entries, the only criticism they
> could level against my implementation was that I had (quite
> intentionally) used a simple interpretation in a place where the
> requirements were vague, instead of putting in something complicated.
> Test Driven Development gives me the confidence to know that if the
> customer wants me to add something complicated, I can easily do so --
> with very high confidence that I won't break anything else. And if I
> had guessed wrong in putting in features that were not asked for, that
> could have been bad too.
>
> See "JeffGrigg-Magic8Ball.zip" in
> http://groups.yahoo.com/group/extremeprogramming/files/

You need to be a member to get in to see those files. Any chance you
could put the somewhere accessible?

Anyway, let me take a whack at this problem. You're going to have to
- read in the user file and build the table
- select a random entry
- print it
The interface isn't spec'd so I'll assume that every time the program is
run it randomly selects one message and dumps it.

The input format isn't spec'd so I'll assume that it looks like
<prob as a real number>
message
can be multi-line

# this is a comment - note the empty line that denotes end of message
# multiple empty lines are also legal
# comments can occur only between messages, and have a # in col 0

Ok, to print out the random-entry, we'll put the messages together as a
list. Each message will have the cummulative probability. Hmmm..ok, so
we'll store them as integers by premultiplying the probabilities by
        prob*RAND_MAX/sum_of_probs
so the structure looks like:
        struct message {
          struct message * msg_next;
          double msg_prob;
          unsigned msg_cumm;
          char * msg_str;
        };
To find a random message get a number from rand() and find the entry
whose cummulative probability is >= the number, and whose previous entry
is < number.

[We'll have to print an error if prob*RAND_MAX/sum_of_probs returns 0]
[For efficiency we can build an index into this table, probably by using
an N entry array to point to the entry containing i*RAND_MAX/N]

Since we're using random numbers, for debug, we'll have a flag to set
the initial seed. Since this is stand-alone, no rand_r() needed.

During parsing, we'll have to worry about unbounded user input, since
we're allowing multi-line messages. Use a sparse/dense array of chars.
[That's what I call a structure where its an array of pointers to arrays
that gets filled in on demand.
        #define SCAN_L1_SIZE 256
        #define SCAN_L2_SIZE 4096
        char * scan[SCAN_L1_SIZE];
        
        void
        check_scan(
                char * scan[],
                unsigned n
                )
        {
          unsigned i = n/SCAN_L2_SIZE;
          assert( n < SCAN_L1_SIZE*SCAN_L2_SIZE );
          if( scan[i] == 0 ) {
             scan[i] = (char *)malloc(SCAN_L2_SIZE);
            assert( scan[i] ); /* substitute with error msg */
          }
        }
        
        #define scan_at(_scan, _at) \
                (_scan[(_at)/SCAN_L2_SIZE][(_at)%SCAN_L2_SIZE])

]

To verify that that something is a float, I'll use strtod(scan, &tail),
and then check to see that the tail != scan and contains only isspace()
characters.

The scan routine for a record will be:
   do {
     get_line();
   } while( is_empty_line() || is_comment_line() )
   if( end_of_file() ) {
     return; /* no record */
   }
   if( get_float() == error ) {
     /* error & exit? */
   }
   do {
      get_line()
      add_to_temporary_sparse_dense_array()
    } while( !is_empty_line() ); /* end-of-file => empty line */
    if( is_empty_temp() ){
      /* error & exit */
    }
    build_record()

I don't think there is anything more left in the design. I'd probably
have finished coding and testing it in less time than it took to key in
this message and debug the English :)

• Previous message: Thomas Lotze: "Re: Choosing a language for an OO design"
• In reply to: Jeff Grigg: "Re: A critique of test-first..."
• Next in thread: CTips: "Re: A critique of test-first..."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]