ADC #1 Results

This is a discussion on ADC #1 Results within the Contests Board forums, part of the Community Boards category; This will be a long and involved thread because I'm going to give both the final results as well as ...

  1. #1
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796

    ADC #1 Results

    This will be a long and involved thread because I'm going to give both the final results as well as my reviews instead of zipping it all together. Saves everyone a download...you're welcome.

    Here are the final scores, with 40 being the highest (normal) score. There was one truly exceptional entry that I scored at 42.

    BEGINNER LEVEL
    --------------
    Speedy5 - 21
    XSquared - 40
    vasanth - 29
    ygfperson - 32
    Wledge - 40
    KertSurge - 26
    PJYelton - 38
    Hammer - 40

    Winner: XSquared!


    INTERMEDIATE LEVEL
    ------------------
    Speedy5 - 20
    JaWib - 33
    XSquared - 40
    ygfperson - 37
    Lucifuri0us - 38
    Wledge - 42

    Winner: Wledge!


    ADVANCED LEVEL
    --------------
    Speedy5 - 33
    Sean345 - 22
    FillYourBrain - 19
    Hammer - 37
    KurtSerge - 18
    XSquared - 32
    vasanth - 31
    ygfperson - 29
    Lucifuri0us - 33
    Wledge - 25
    PJYelton - 29

    Winner: Hammer!

    It may take me some time to get all of the reviews posted, so be patient.
    Last edited by Prelude; 08-05-2003 at 08:32 AM.
    My best code is written with the delete key.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Speedy5
    -------

    Beginner Level
    --------------

    Code Review: Speed was a factor in this assignment, so virtually any use of character arrays would be unacceptable. I have a few bones to pick with Speedy5's digRev function:
    Code:
    int digRev(int value)
    {
    	// note: 11 digits is enough for any 32-bit or less
    	//       integeral number
    
    	char digits[11];
    	int len = 0, base = 1;
    
    	while (value != 0)
    	{
    		digits[len++] = value % 10;
    		value /= 10;
    	}
    
    	while (len-- > 0)
    	{
    		value += base * digits[len];
    		base *= 10;
    	}
    
    	return value;
    }
    The assignment required that a long double be returned because INT_MAX or INT_MIN would overflow when the digits were reversed. A longer type is needed if the requirements of the assignment are to be properly met.

    11 digits is certainly enough for any 32 bit value. However, 32 bits cannot hold the largest 32 bit value reversed. Also, what happens if the int type is longer than 32 bits on a different machine? Of course, if int and long double are both 64 bits you have a problem, but we'll ignore that for now. :-)

    Concerning speed, Speedy's function was nearly double that of my test solution. The elegance of his solution (excluding performance) was acceptable, and portability is also acceptable (it can handle 32 bit or less). All three categories will suffer by two points because the function is not correct within the cases required.

    Correctness: 7 (Works well as long as int doesn't overflow or underflow)
    Speed: 5 (Could be faster with little effort and no loss of clarity)
    Elegance: 4 (Did more work than it needed to)
    Portability: 5 (Unwarranted assumptions)

    Intermediate Level
    ------------------

    Summary: It seems as if Speedy solved the wrong problem. That's okay since I was not 100% clear in what the task was, but it still effects the scoring.

    Code Review: Speedy's algorithm finds the shortest third stick out of eight possible sticks, not the shortest length of the longest stick:
    Code:
    int shortestThirdSide(int *sides)
    {
    	int i, j, num, min = 0;
    	bool first = true;
    
    	for (i = 0; i < 7; i++)
    	{
    		for (j = i + 1; j < 8; j++)
    		{
    			num = sides[i] + sides[j] + 1;
    			if ((num < min) || (first == true))
    			{
    				min = num;
    				first = false;
    			}
    		}
    	}
    
    	return min;
    }
    Scores:

    Correctness: 0 (Solution to the wrong problem)
    Speed: 5 (Doesn't fare well with the correct solution)
    Elegance: 5 (Striking resemblance to bubble sort)
    Portability: 10 (Definitely portable)

    Advanced Level
    --------------

    Summary: Excellent solution. Speedy5's function is almost identical to mine. However, it suffers in the speed category as Speedy's function averaged about 60ms for 100000 calls while my test function averaged half that for the same number of calls.

    Code Review: Speedy used a lookup table and two loops, one to fill the table and one to walk each char in the string in order to see which is the first nonrepeated character. All in all a good function:
    Code:
    char findFirstNonRepeat(char *str)
    {
    	char freq[256] = { 0 };
    	char *ch;
    
    	for (ch = str; *ch != NULL; ch++)
    		freq[*ch]++;
    
    	for (ch = str; *ch != NULL; ch++)
    	{
    		if (freq[*ch] == 1)
    			return *ch;
    	}
    
    	return NULL;
    }
    I have two nitpicks about this code. While C++ may give the macro NULL a value of 0, this function should run as C too. C allows NULL to be (void*)0, which is really not a good thing to use in place of '\0'. I removed one elegance point for that because it can potentially break the program depending on compiler and system.

    Next, Speedy assumed that a char is 8 bits. This is true in many places, but not everywhere.

    Scores:

    Correctness - 10 (Works well, the first entry to do so)
    Speed: 7 (Hot foot, but not flaming)
    Elegance: 9 (Well thought out and implemented)
    Portability: 7 (Unwarranted assumptions)
    My best code is written with the delete key.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Sean345
    -------

    Advanced
    ---------

    Summary: A nice function. It does what is needed in a more than reasonable time using a lookup table. The only problem is that it only handles letters from the ASCII character set. The task requirements clearly stated "character", not "letter". When run as is, this function is slightly faster than my implementation, but only just. When modified to handle any character it runs slower than any of the other entries (at the time of grading).

    Code Review: There are a few places in this code that caused me to look twice to make sure I was seeing it, but most of them I let slide. Here is the function:
    Code:
    #include <ctype.h>
    
    /*	Returns the first character that is not repeated in the string.
    	If non are found, 0 is returned. */
    char findFirstNonRepeat ( char *s )
    {
    	char *Location = s;  /* Current Location in String s */
    	unsigned int Letters[26] = {0}; /* Amount each letter is repeated */
    
    	/* Loop through string and determine how man times each letter is used */
    	while(Location[0]!='\0'){
    		if(isalpha(Location[0])==0){ /* Ignore non-alpha characters */
    			Location++;
    			continue;
    		}
    		Letters[toupper(Location[0])-'A']++;
    		Location++;
    	}
    
    	/* Loop again through string and determine first non repeating charecter */
    	Location = s;
    	while(Location[0]!='\0'){
    		if(Letters[toupper(Location[0])-'A']==1){
    			return Location[0];
    		}
    		Location++;
    	}
    	return 0; /* Return 0 if no non repeating characters were found */
    }
    One of the bad parts of this function is

    unsigned int Letters[26] = {0};

    The assumption that only 26 characters will be encountered causes the function to lose quite a bit of flexibility. I did wonder about this use of a pointer

    while(Location[0]!='\0'){

    Generally, an array index (even when based off of a pointer) uses array notation, but a pointer to a certain position in an array uses pointer notation. Both work, but the latter reads easier. This is an idiosyncracy that I let slide.

    Letters[toupper(Location[0])-'A']++;

    This and similar lookups is what kills portability. Since the letters in any given character set are not required to be consecutive (and not all are), this calculation will give unexpected results on character sets such as EBCDIC. Other than this, the logic is the same as my implementation.

    Scores:

    Correctness - 8 (It works well and quickly, but only in certain cases)
    Speed: 5 (Fast as written, but when meeting requirements it is very slow)
    Elegance: 7 (Good logic, code could be better)
    Portability: 2 (Assumes string contents and character set)
    My best code is written with the delete key.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    JaWiB
    -----

    Intermediate
    ------------

    Summary: I won't go into the details of the solution because it's well known. JaWiB was the first contestant to make the connection. The only reason his code failed to produce the correct output was incorrect starting values and too many loop iterations.

    Code Review: Here is JaWiB's take on the task:
    Code:
    int LongShort(int shortest,int sticks)
    {
        int first=shortest;
        int second=shortest+1;
        int third=0;
         for (int x=0;x<sticks;x++)
              {
              third=first+second;
              first=second;
              second = third;
              }
         return third;
    }
    It may look familiar, and it is. This is a naive implementation of the Fibonacci sequence. The output of this function with arguments of 1 and 8 is 89. The correct output should have been 21, here's why: Triangle inequality states that to be unable to make a triangle with three sticks of any length, one stick has to be at least as long as the sum of the other two. So starting with 1 to make it easier, the longest has to be at least the sum of the next two, and so on. The only problem with JaWiB's code is that first and second should be shortest from the beginning, and the loop should start at 2 instead of 0 since two of the sticks are already known.

    Score:

    Correctness: 7 (Very close!)
    Speed: 10 (Nice and quick)
    Elegance: 6 (Most first year CS majors learn this algorithm)
    Portability: 10
    My best code is written with the delete key.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    FillYourBrain
    -------------

    Advanced
    ---------

    Summary: FYB had an interesting algorithm that surprised me when I first read it. My first reaction was "Beautiful! What a superb solution!". I was expecting either nested loops (O(n^2) complexity), or some variant of a lookup table (O(n) complexity). FYB's backward walking algorithm caught me completely off guard, and probably would have won had it worked.

    Code Review: I have several nitpicks concerning FYB's function. Here is the function itself:
    Code:
    #include <memory.h>
    char findFirstNonRepeat ( char *s )
         {
         char ret;
         char *ptr = s;
         char table[256]; // I know, I know  The ascii set isn't this big.
         memset(table,0,256); //memset isn't too "high level" is it?
    
         for(; *ptr; ptr++); //find the end
    
         for(;ptr >= s; ptr--) //walk backwards
              {
              if(++table[*ptr] == 1) // is it first time for this one?
                   ret = *ptr; //this is now the earliest one.
              }
         return ret;
         }
    First and foremost is the header memory.h, which doesn't exist according to either the C or C++ standard. No doubt it's inclusion was for memset, which lives in the standard header string.h. This hurts portability.

    char table[256]; // I know, I know The ascii set isn't this big.

    This is correct since I didn't specify ASCII, not letters of the alphabet. I said characters, which could be any positive integer value that fits into a char. This is good except for the fact that FYB hardcoded 256 as the array size. A char is not always an octet, you can't assume 8 bits.

    memset(table,0,256); //memset isn't too "high level" is it?

    Use of memset is a good thing, but once again the literal 256 is used. Here is a sample run of this function using one of the strings I gave as an example in the task description, "google".

    After the "find the end" loop, ptr points to the nul character at the end of the string:
    Code:
    \0 ret = '\0'
    e  ret = 'e'
    l  ret = 'l'
    g  ret = 'g'
    o  ret = 'o'
    o  ret not changed
    g  ret not changed
    As you can see, ret is not the first nonrepeating character. While the idea is clever, it doesn't work as written. This just goes to show that even if something seems simple, it may not be.

    Scores:

    Correctness - 3 (Works some of the time, but not always)
    Speed: 5 (Half as fast as my comparison function)
    Elegance: 4 (Clever, creative, would score better if it worked)
    Portability: 7 (Nonexistant header and unwarranted assumptions)
    My best code is written with the delete key.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Hammer
    ------

    Beginner
    --------

    Summary: Hammer used the divide and conquer () algorithm that most everyone seemed to prefer for this task. The only real difference is that he took into account the sign as well. This wasn't a requirement, but it's still a nice gesture.

    Code Review: No comments, nice work.
    Code:
    long double digRev ( int val )
    {
      long double ret = 0;
      int signbit = (val < 0) ? 1: 0;
      
      while (val)
      {
        int v = (val % 10);
        ret = ret * 10.0 + v;
        val /= 10;
      }
    
      return (signbit)?-ret:ret;
    }
    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 10
    Portability: 10


    Advanced
    --------

    Summary: Hammer submitted two different functions, one that performs the expected table lookup seen in most of the other entries, and one that makes use of a forward walk and table save. The second is excellent, and when given the same table optimizations as my test function, blew it away. For the sake of this contest, I'll take only the best of the two. Sadly, I can't grade it based on the changes I made.

    Code Review: Here is the function:
    Code:
    char FindFirstNonRepeat(char *s)
    {
      char  *ptr = s, *wrkptr;
      int   table[256] = { 0 };
    
      while (*ptr != '\0')
      {
        if (table[*ptr] == 1)
        {
          ptr++;
          continue;
        }
    
        for (wrkptr = ptr + 1; 
             *wrkptr != *ptr && *wrkptr != '\0'; 
             wrkptr++)
             ;
        if (*wrkptr == '\0')
        {
          return(*ptr);
        }
    
        table[*ptr] = 1;
        ptr++;
      }
    
      return('\0');
    }
    All in all, I only have one problem with the above function. The same problem that every entry seems to have, the assumption that char is 8 bits.

    Scores:

    Correctness - 10 (Works perfectly)
    Speed: 8 (Fast without optimization, blazing with)
    Elegance: 10 (Work of art)
    Portability: 9 (One unwarranted assumption)
    My best code is written with the delete key.

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    KurtSerge
    ---------

    Beginner
    --------

    Summary: Not a bad idea. Kurt used the standard (and nonstandard) library to reverse an integer. However, by using atol, the function fails to meet the requirement of handling all extremes of an int. Also, because of sprintf, strrev, and atol, this function is painfully slow. On the up side, it's very easy to figure out what's going on. The readability factor is way up there.

    Code Review:
    Code:
    long double digRev(int val)  {
    
    	// Variables
    	char Buffer[11];
    
    	// Make sure val is valid
    	if(val < INT_MIN || val > INT_MAX)
    	return 0;
    
    	// Put val in a buffer and reverse the buffer
    	sprintf(Buffer, "%d", val);
    	strrev(Buffer);
    
    	// return long double of Buffer
    	return atol(Buffer);
    }
    Once again the commenting is a little excessive, but for such a small function I can let that go. The buffer size makes an assumption about the representation of an int, and the test is pretty much worthless since an int will always have a value somewhere between INT_MIN and INT_MAX. Though the test does forget about INT_MIN and INT_MAX themselves.

    strrev is not a standard library function, so I'll count off portability points for that. However, since that function is present in my "standard" library, the function worked as planned. I won't count off points for correctness.

    Finally, atol converts the string argument to a long integer, not a long double. No function in the standard library works with long double, the largest is double. So this task pretty much requires that you do it yourself. Kudos for the nice try though.

    Scores:

    Correctness: 7
    Speed: 2
    Elegance: 9 (Using the library is a good thing)
    Portability: 8 (strrev. But it's easily written for compilers that don't have it)

    Advanced
    --------

    Summary: Kurt used three nested loops and a buffer to remove repeated characters. The algorithm is sound: it copies the string (allowing for literals) and correctly handles indices. Of course, the dynamic allocation, nested loops, and expensive deletion of internal characters from the buffer causes severe performance problems when compared with faster entries. It also fails to meet the O(n) requirement.

    Code Review: I have only four problems with this code, first is the overcommenting:
    Code:
    char findFirstNonRepeat(char * s)  {
        
        // Variables
        char FirstNonRepeat;
        char * Buffer = new char[6];
        int counter = 1;
        
        // Set Buffer equal to s (so we dont screw up s)
        Buffer[strlen(s)] = NULL;
        for(int i = 0;  i < strlen(s);  i++)
            Buffer[i] = s[i];
        
        // Finds the non repeat
        while(1)  {
            // Get the letter to check
            FirstNonRepeat = Buffer[0];
            
            while(1)  {
                // If we reach the end of the string, then we found the non repeat
                if(Buffer[counter] == NULL)
                    return FirstNonRepeat;
                
                // If we can't find a double, than this is our non-double
                if(Buffer[counter] != Buffer[0] && counter == strlen(Buffer) - 1)
                    return FirstNonRepeat;
                
                // If the first letter is the same as the counter letter,
                // than delete all of that letter (because it repeats)
                if( Buffer[counter] == Buffer[0])  {
                    // Temporary, used to find repeats
                    // counter2 is used to replace Buffer with the new string
                    FirstNonRepeat = Buffer[0];
                    int counter2 = 0;
                    
                    // Put anything that is not the repeating letter at the beginning of the buffer,
                    // and reposition the NULL terminator since the string is smaller now
                    for(i = 0;  i < strlen(Buffer);  i++)  {
                        
                        if(Buffer[i] != FirstNonRepeat)  {
                            Buffer[counter2] = Buffer[i];
                            counter2++;
                        }
                        
                        if(i >= strlen(Buffer) - 1)  {
                            Buffer[counter2] = NULL;
                            break;
                        }
                    }
                    
                    break;
                }
                
                // Increment
                counter++;
            } //<-- End of 2nd while(1)
            
            // reset
            counter = 1;
        } //<-- End of 1st while(1)
        
        // Free Buffer
        delete[] Buffer;
        
        // Error (no repeats)
        return (char)0;
    }
    Next is the assumption that the string will only be 5 characters long (allow one extra for the terminating nul). This alone means that the test cases are broken (google is 6 characters, add one extra for the nul character). Next is the assumption that NULL can be used in anything but a pointer expression. Most likely it's true for C++, but you can't count on that. Lastly, the use of strlen as a loop condition is horrible for performance. Even code that doesn't care about speed should avoid calling strlen only as many times as absolutely required and saving it in a variable.

    Scores:

    Correctness: 3 (new char[strlen(s) + 1]; burn it into your memory)
    Speed: 2
    Elegance: 4 (Not a bad algorithm, but it could be much better)
    Portability: 9 (The only problem is your use of NULL)
    My best code is written with the delete key.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    XSquared
    --------

    Beginner
    --------

    Summary: Almost an exact match for my test function. Nicely done.

    Code Review:
    Code:
    long double digRev( int val ) 
    {
      long double newNum = 0;
      
      while( val != 0 ) {
    
        newNum *= 10;
        newNum += ( val % 10 );
        val /= 10;
        
      }
    
      return newNum;
    }
    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 10
    Portability: 10

    Intermediate
    ------------

    Summary: XSquared made the connection and solved the problem. Well done! I modified it to run as a function for easier testing. The original was a main function.

    Code Review:
    Code:
    int stickLen( void ) 
    {
      
      int sticks[ 8 ];
      int i;
      
      sticks[ 0 ] = 1;
      sticks[ 1 ] = 1;
      
      for( i = 2; i < 8; i++ ) {
        
        sticks[ i ] = sticks[ i - 1 ] + sticks[ i - 2 ];
        
      }
      
      return sticks[ 7 ];
    }
    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 10 (Hard coded values, but I can let that slide)
    Portability: 10


    Advanced
    --------

    Summary: Works well, doesn't match up to the speed of other entries and not even close to the test function, but still a nice piece of work.

    Code Review:
    Code:
    char findFirstNonRepeat( char *s ) 
    {
      int charCounts[ 256 ] = { 0 };
      int i = 0;
      
      while( *s != '\0' ) {
        
        charCounts[ (*s) ]++;
        i++;
        s++;
        
      }
    
      s -= i;
      
      while( *s != '\0' ) {
        
        if( 1 == charCounts[ (*s) ] ) return *s;
        *s++;
        
        
      }
      
      return '\0';
      
    }
    The first problem is the same with everyone's entry. Assuming that a char can hold 256 values. Aside from that the code is correct and easy to follow.

    Scores:

    Correctness: 10 (Works great)
    Speed: 5 (Nothing extraordinary)
    Elegance: 8 (Well written)
    Portability: 9 (One unwarranted assumption)
    My best code is written with the delete key.

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    vasanth
    -------

    Beginner
    --------

    Summary: This function has the right idea, but doesn't take it quite far enough.

    Code Review:
    Code:
    // Long comments removed
    long double digRev ( int val )
    {
    	int final=0;
    	int temp=val;
    
    	while(val>0.0)
    	{
    	val=val/10;
    	val=val*10;
    	final=(final*10)+(temp-val);
    	val=val/10;
    	temp=val;
    	}
    
    return final;
    }
    This function worked fine for the example case of 12345, but failed to meet the requirement of properly handling INT_MAX and INT_MIN.

    Scores:

    Correctness: 6 (Mostly correct, fails to handle extremes though)
    Speed: 5 (Not bad, about average)
    Elegance: 8 (Iffy. The use of three variables where two will do chaffes some)
    Portability: 10 (The code itself is portable)


    Advanced
    --------

    Summary: This function was blazing in my tests and came up with the right answers but...it failed to meet the O(n) requirement. Walking a string with a loop and another loop nested inside it that walks the string is O(n^2).

    Code Review:
    Code:
    char findFirstNonRepeat ( char *s )
    {
        char ch=' ';
        int flag=0;
        int i=0;
        int j=0;
        
        while(s[i]!='\0')
        {
            ch=s[i];
            j=0;
            flag=1;
            
            while(s[j]!='\0')
            {
                if(j==i)
                    j++;
                
                if(s[j]==ch)
                {
                    flag=0;
                    break;
                }
                j++;
            }
            
            if(flag==1)
                break;	
            i++;
        }
        
        return ch;
    }
    This is the obvious solution, but it's implemented well. I docked a few elegance points for the excessive and needless commenting. As an example:

    flag=1; // flag is set to 1

    I'm quite sure 99.9% of your audience would be able to figure out that flag is set to 1 without the comment.

    Scores:

    Correctness: 5 (Works, but failed to meet requirements)
    Speed: 10
    Elegance: 6 (Not the most elegant solution, but kudos nonetheless)
    Portability: 10 (No problems here)
    My best code is written with the delete key.

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    ygfperson
    ---------

    Beginner
    --------

    Summary: ygf used basically the same algorithm that I did, and the speed was virtually a dead match in several profiling tests. However, the use of long instead of long double resulted in incorrect output at the positive and negative extremes. The function is supposed to work correctly for INT_MAX, INT_MIN and everything in between.

    Code Review: Aside from using long when I clearly gave a function prototype that had long double, this code is good.
    Code:
    long digRev (long input) {
      long output = 0;
      while (input) {
        output *= 10;
        output += input % 10;
        input /= 10;
      }
      return output;
    }
    Scores:

    Correctness: 7 (Works well except for extremes)
    Speed: 10 (Nice and toasty)
    Elegance: 9
    Portability: 6 (2 byte ints and 4 byte longs are okay, but 4 byte ints and longs are not)


    Intermediate
    ------------

    Summary: ygf went with the simplest solution, nonrecursive with three variables holding the smallest, current, and largest values. While this isn't the most elegant of solutions, it produces the correct answer, and certainly is fast. My timer scaffolding is far less accurate than my profiler (that chose to break right as I was testing this function), but the differences weren't so close that another 0 or two added to my number of iterations wouldn't fix.

    Code Review: You've probably seen this one too many times if you've taken a programming course.
    Code:
    int stickLen(int x) {
      //longest cannot be more or equal to the two lesser ones
      //no three can make a triangle
      //1 + 1 = 2
      //1 + 2 = 3
      //2 + 3 = 5
      //use largest two to determine next largest because smaller ones may fail test
      int i, shortest, cur_largest, largest;
      if (x < 3) return -1;
      for (i=2, shortest = 1, cur_largest = 1, largest = 2; i < x; ++i) {
        largest = shortest + cur_largest;
        shortest = cur_largest;
        cur_largest = largest;
      }
      return largest;
    }
    Scores:

    Correctness: 10
    Speed: 10 (Faster than mine usually gets a 10)
    Elegance: 7 (Most first year CS majors know this algorithm by heart)
    Portability: 10 (No complaints here)


    Advanced
    --------

    Summary: ygf went with (in my opinion) an overly complex algorithm that uses two maps and bit flags to mark first time and repeat values. The algorithm is indeed O(n), but it suffers because of the two arrays. A successful algorithm can get away with just one.

    Code Review: As with every other entry at the time of this review, ygf assumed that the largest char value is 256. He did however, take into account that no printable character is signed and used unsigned char. The use of macros as named constants is a breath of fresh air, thank you for that. Here is the code:
    Code:
    #define REPEAT_BIT 0x01
    #define FIRST_BIT 0x02
    
    char findFirstNonRepeat (char *s) {
      unsigned char bits_int[256], map[256];
      int i,value;
      memset(bits_int,0,256);
      for (value=0;*s != '\0';++s) {
        if (!(bits_int[*s] & REPEAT_BIT))
          if (bits_int[*s] & FIRST_BIT)
            bits_int[*s] |= REPEAT_BIT;
          else {
            bits_int[*s] |= FIRST_BIT;
            map[value++] = *s;
          }
      }
    
      for (i=0;i < value; ++i) {
        if (!(bits_int[map[i]] & REPEAT_BIT))
          return map[i];      
      }
    }
    One distinct flaw is what to return if there is no nonrepeating character.

    Scores:

    Correctness: 9 (Works in all but one case)
    Speed: 5 (Half as fast as the test function)
    Elegance: 6 (Nifty algo, but too complex)
    Portability: 9 (One unwarranted assumption)
    My best code is written with the delete key.

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Lucifuri0us
    -----------

    Intermediate
    ------------

    Summary: Connection made. He even called it fib. The algorithm is the simple one that everyone learns first, which basically means it blew my test function out of the water in speed.

    Code Review: Same ol' same ol'
    Code:
    int fib(int n)
    {
      int n1 = 1, n2 = 1, count, total = 0;
    
      if (n == 1 || n == 2)
        return 1;
    
      for (count = 3; count <= n; count++) {
        total = n1 + n2;
        n1 = n2;
        n2 = total;
      }
    
      return total;
    }
    Even breaking out lint was no help. This code is solid.

    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 8 (Vanilla algorithm, fast, but not a wower)
    Portability: 10


    Advanced
    --------

    Summary: Two entries were submitted for this task, one was the "obvious" solution (taken from a comment in the code), the other was not so obvious, but for good reason. I chose the obvious solution because the not so obvious solution was dreadfully slow. Both produced correct output.

    Code Review: The usual frequency lookup table was used in this solution:
    Code:
    char findFirstNonRepeat(char *s)
    {
      int freq[256] = {0};
      char *p = s;
    
      /* build frequency table */
      while (*p) {
        freq[*p++]++;
      }
    
      /* find first char with freq of 1 */
      while (*s) {
        if (freq[*s] == 1)
          return *s;
        s++;
      }
      return '\0';
    }
    All in all I have no real problem except for the assumption of 256 that *everyone* made up to this review.

    Scores:

    Correctness: 10
    Speed: 5 (Half as fast as the test function)
    Elegance: 9 (Well done, but not mindblowing)
    Portability: 9 (One unwarranted assumption)
    My best code is written with the delete key.

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Wledge
    ------

    Beginner
    --------

    Summary: Same algorithm as my solution, it more or less matches speeds as well.

    Code Review: One of the only entries to actually work for all of my test cases.
    Code:
    long double digRev(int dig)
    {
    	long double res = 0.0;
    	while(dig)
    	{
    		res *= 10.0;
    		res += dig % 10;
    		dig /= 10;
    	}
    	return res;
    }
    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 10
    Portability: 10


    Intermediate
    ------------

    Summary: Sneaky, brilliant, only works for 8 sticks though. Of course, since I didn't specify otherwise, Wledge is most likely the winner. I had to up the maximum possible score to display how wonderful this solution is (that and another entry has a perfect score that I didn't want to change).

    Code Review: I laughed so hard my husband looked at me funny for about an hour when I saw this:
    Code:
    /*
     *  ----Algorithm----
     *	int stickLen(int nrOfSticks)
     *	{
     *		int stickLength[3] = {1,1,2};
     *		for(int i = 3;i < nrOfSticks;i++)
     *		{
     *			stickLength[0] = stickLength[1];
     *			stickLength[1] = stickLength[2];
     *			stickLength[2] = stickLength[0] + stickLength[1];
     *		}
     *		return stickLength[2];
     *	}
     */
    int stickLen(void)
    {
    	return 8 + 13;/*  Write a program to 'calculate'... */
    }
    Genius. Sheer genius. It's a trick of course, but there aren't any rules against it.

    Scores:

    Correctness: 10
    Speed: 11
    Elegance: 11
    Portability: 10


    Advanced
    --------

    Summary: Wledge's was another entry that assumed letter when I meant any printable character. The function works, but even by using an array of 26 instead of 256 (a deciding factor in speed for another entry), this function is still half as fast as the test function when run with scaffolding (my profiler refused to work for no apparent reason). The algorithm is an interesting (read as "weird/overly complex") one that uses indexing and arithmetic tricks to get the desired output.

    Code Review: Aside from being an oddity (no offense intended), this code has several flaws.
    Code:
    char findFirstNonRepeat (char *s )
    {
    	long abc[26] = {0};
    	long count = 0,diffChars = 0;
    	int index;
    	char *p = s;
    
    	for(long pos = 1;*s;++s,++pos)
    	{
    		if(isalpha(*s))
    		{
    			index = tolower(*s) - 'a';
    			if(!abc[index])
    			{
    				abc[index] = pos;
    				++diffChars;
    			}
    			else if(abc[index] > 0)
    			{
    				abc[index] = -1;
    				if(++count == 26)
    					return 0;
    			}
    		}
    	}
    
    	if(diffChars == count)
    		return 0;
    
    	long min = LONG_MAX;
    	for(int i = 0;i < 26;++i)
    		if(abc[i] > 0 && abc[i] < min && (1 == (min = abc[i])))
    			break;
    
    	return *(p + min - 1);
    }
    First is the assumption that only 26 characters are valid. When I say character, I mean everything, not just the alphabet subset. Next is the assumption that subtracting 'a' from the value will give a correct index. This is true with ASCII, but not other character sets I can think of. Aside from that, there's no real portability problem.

    Scores:

    Correctness: 10 (It works nicely)
    Speed: 5 (Half as fast as the test function, which used a considerably larger array)
    Elegance: 3 (Elegant wouldn't be my first choice of words, the function is too confusing)
    Portability: 7 (What if I didn't use ASCII?)
    My best code is written with the delete key.

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    PJYelton
    --------

    Beginner
    --------

    Summary: Connection made. PJ used the obvious iterative solution. Nicely done too.

    Code review: I have no problems with the code.
    Code:
    int shortestLength(int numSticks)
    {
    	int first=1;
    	int second=1;
    	for (int x=3; x<=numSticks; x++)
    	{	
    		int temp=second;
    		second+=first;
    		first=temp;
    	}
    
    	return second;
    }
    Scores:

    Correctness: 10
    Speed: 10
    Elegance: 8 (Vanilla algorithm, fast, but not a wower)
    Portability: 10


    Advanced
    --------

    Summary: PJ used a lookup table. Pretty much the same deal as everyone else, though I remind everyone that even the smallest modification can be of huge difference in performance. Because of this trait in the advanced task, PJ's is quite a bit slower than most of the other entries even though the algorithm is exactly the same.

    Code Review:
    Code:
    char findFirstNonRepeat ( char *s )
    {
    	int numOfChar[255];
    	int x=0;
    	
    	for (x=0; x<255; x++)
    		numOfChar[x]=0;
    
    	for (x=0; s[x]!='\0'; x++)
    		numOfChar[s[x]]++;
    
    	for (x=0; s[x]!='\0'; x++)
    	{
    		if (numOfChar[s[x]]==1)
    			return s[x];
    	}
    
    	return -1;
    }
    One problem I have is that PJ missed one character, 256, not 255. Even then it's still an assumption about the representation of a char. Ignoring the hardcoded 255's, the algorithm is sound.

    Scores:

    Correctness: 10
    Speed: 3
    Elegance: 7
    Portability: 9 (One unwarranted assumption)
    My best code is written with the delete key.

  14. #14
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Here were my test functions:

    Beginner
    --------
    Code:
    long double digRev ( int val )
    {
        long double ret = 0;
    
        while ( val != 0 ) {
            ret = ( val % 10 ) + ret * 10;
            val /= 10;
        }
    
        return ret;
    }
    Intermediate
    ------------
    Code:
    int nthFib ( int n )
    {
        static char fibList[8];
    
        fibList[0] = 1;
        fibList[1] = 1;
    
        for ( int i = n - 1, t = 0, e = 1; i > 1; i--, t++, e++ )
            fibList[e + 1] = fibList[t] + fibList[e];
    
        return fibList[n - 1];
    }
    Advanced
    --------
    Code:
    char findFirstNonRepeat ( char *str )
    {
        static unsigned char htable[UCHAR_MAX + 1];
        char *pstr;
    
        memset(htable, 0, UCHAR_MAX);
    
        for ( pstr = str; *pstr != '\0'; ++pstr )
            htable[*pstr]++;
    
        for ( pstr = str; *pstr != '\0'; ++pstr )
        {
            if ( htable[*pstr] == 1 )
                return *pstr;
        }
    
        return 0;
    }
    My best code is written with the delete key.

  15. #15
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    you know what stinks? a variety of my function would have worked. I should have spent more time testing it. CRAP!!!!
    Code:
    #include <string.h>
    char findFirstNonRepeat ( char *s )
         {
         char ret;
         char *ptr = s;
         char table[256]; // I know, I know  The ascii set isn't this big.
         memset(table,0,256); //memset isn't too "high level" is it?
    
         for(; *ptr; ptr++) //find the end and add up the freq
              table[*ptr]++;
    
         for(;ptr >= s; ptr--) //walk backwards
              {
              if(table[*ptr] == 1) // is it first time for this one?
                   ret = *ptr; //this is now the earliest one.
              }
         return ret;
         }
    and by the sound of the review, I would have won very nicely. Oh well. Prelude, would you mind looking at the above and verifying that?

    edit: oh man, it looks like you did the same exact algorithm except you walked forward! never mind.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 72hour GDC Results
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 07-05-2004, 11:46 PM
  2. ADC #4 Results
    By Prelude in forum Contests Board
    Replies: 9
    Last Post: 08-28-2003, 01:38 PM
  3. ADC #3 Results
    By Prelude in forum Contests Board
    Replies: 19
    Last Post: 08-18-2003, 11:25 PM
  4. ADC #2 Results
    By Prelude in forum Contests Board
    Replies: 20
    Last Post: 08-11-2003, 06:59 AM
  5. Same seed for srand yields different results
    By codegirl in forum C++ Programming
    Replies: 3
    Last Post: 06-23-2003, 02:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21