Page 3 of 4 FirstFirst 1234 LastLast
Results 21 to 30 of 39

Thread: C/C++ Test - Category Looping & Optimising - Level Medium

  1. #21
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    I still think this is shorter and more efficient.


    Code:
    #include <time.h>
    #include <stdio.h>
    
    bool isEqual( char *code, char *value, int size );
    
    int main()
    {
    	//Time declarations
       time_t    start, finish;
       double    elapsed_time;
    
       //Input declarations
       FILE *    stream;
       stream    =    fopen( "input.txt", "r" );
       if( stream == NULL )
       {
       	printf("Error opening file");
          fclose(stream);
          return    0;
    	}
    
       int size;
       char value[129], digits[129] = "";
    
       //Getting the first number
       fscanf(stream, "%d", &size);
    
       //Getting the test string
       fscanf(stream, "%s", &value);
    
       fclose(stream);
    
       time( &start );
    
       // MY CODE HERE
       int count, iDigit = size;
    
       // set our base number to 1
    	while( iDigit ) digits[ --iDigit ] = 'A' ;
    
    	for( count = 1 ; !isEqual( value, digits, size ) ; count++ )
    	{
    		while( digits[ iDigit ]++ == 'E' ) iDigit++;
    		while( iDigit ) digits[ iDigit - 1 ] = digits[ iDigit-- ];
    	}
    
       // CODE ENDS
    
    	printf("selcount = %d", count);
       //code end here
    
       time( &finish );
    
       elapsed_time = difftime( finish, start );
       printf( "\nProgram takes %6.3f seconds.\n", elapsed_time );
    
       return    1;
    }
    
    bool isEqual( char *code, char *value, int size )
    {
       code+= size ;
       while( *--code == *value++ ) if( size-- == 0 ) return 1;
       return 0;
    }

  2. #22
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    I like how you did the isEqual code, it was sample

    I get a run time problem with it in VSNet 2002 - VC++7.0, though. I cannot get the release to work on windows XP, but I get the debug version to run. Something is wrong with my compiler, I need to upgrade. Or maybe I overlooked something...

    It seems pretty fast, I get 1 secs in debug. Too bad, I can't get it to run the release.

    One important thing, I adjusted the code to get it to run on XP.
    Code:
       int size;
       char	digitsWnull[130];		//A variable to store a leading null in front of digits
       digitsWnull[0]	=	0x00;	//leading null loaded
       char * const	digits	=	(char *)(digitsWnull + 1);
    The stoping condition that returns 1 in the isEquals code requires that the preceeding byte is null, so that preceeding byte of digits isEqual to the trail Null byte of value. Did you build on Linux? Did you change that code after the last test?
    Last edited by crosswire; Jul 14, 2005 at 08:22 AM.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  3. #23
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Lightbulb As far as looping is concerned

    strcmp uses too many iterations before finding that the numbers are different.
    checking the number from the least significant digit will result in finding a discrepancy much sooner.

    however the code you adjusted still has too many lines...

    try substituting

    Code:
    char digits[130] = ""; // alone here
    then substituting

    Code:
    scanf( input, "%s", &digits[1] ); // at the read part
    this should work fine.

    however I still dont see why it should check the null character, my logic was to ignore it by stopping when all the digits were checked.

    try using a pre-decrement in isEqual function of the original code...
    Code:
    while( *--code == *value++ ) if( --size == 0 ) return 1;
    I''m on XP with Borland C++

  4. #24
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default more optimizing

    thats as far as looping is concerned. i noticed that it is a numeric system and they all seem to have a pattern.i re-wrote the algorithm to use all logic for the computation. when done it should calculate the position without tracing all previousnumbers in O(n) time.Yes, linear time...

  5. #25
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    strcmp uses too many iterations before finding that the numbers are different.
    checking the number from the least significant digit will result in finding a discrepancy much sooner.
    True.


    BTW, this problem is not a good example of loop optimization, because it relies too much on such a comparison function.


    I tried the predecrement new code that you have and that work. I now got the release to run. It says "Program takes 0.329 seconds" . Pre-decrement, duh, why didn't Ithink about that!!!


    I used this code to time it
    Code:
    	start	=	clock();
    	////////////Stuff/////////////
    	finish	=	clock();
    
    	elapsed_time	=	(double)(finish - start) / CLOCKS_PER_SEC;
    	printf( "\nProgram takes %0.3f seconds.\n", elapsed_time );
    however I still dont see why it should check the null character, my logic was to ignore it by stopping when all the digits were checked.
    See this[CODE]while( *--code == *value++ ) if( size-- == 0 ) return 1;[CODE] that you had before, if size starts at 5, it returns 1 after running size = 5,4,3,2,1,0 which is one more run than necessary, but you corrected that already.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  6. #26
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    Quote Originally Posted by icymint3
    thats as far as looping is concerned. i noticed that it is a numeric system and they all seem to have a pattern.i re-wrote the algorithm to use all logic for the computation. when done it should calculate the position without tracing all previousnumbers in O(n) time.Yes, linear time...
    Now that would be sweet...

    ...I still think it is ...
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  7. #27
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    I think I figured out why the code did not run in release mode before. VS did some clean up in its optimisation, guessing that still, and it removed the null initialization (that I put in) since it was never used in the local space that it was created, hmmm. The compare function used it, I think, but the compiler was unaware that it did.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  8. #28
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    this is it.
    if you need an explanation ...beg.

    Code:
    #include <time.h>
    #include <stdio.h>
    //#include <conio>
    
    ////////////////////////////////////////////////////////////////////////////////
    // ANDREW HALL a.k.a Kodeci                                                   //
    // icymint3@yahoo.com | icymint3@gmail.com | alphanexxus@yahoo.com            //
    ////////////////////////////////////////////////////////////////////////////////
    
    int main()
    {
    	// Timing declarations
       clock_t start, finish;
       double elapsed_time;
    
       // Input declarations
       int size = 100;              // the length of the number
       char value[130] = "A"; // I have to make sure thre is a leading 'A'
       FILE * stream = fopen( "input.txt", "r" );
    
       // Get data
       fscanf(stream, "%d %s", &size, &value[1] );
    
       // Close the file
       fclose(stream);
    
       start = clock();
    
       // MY CODE HERE
       int count = 1, digitFrom, digitTo = -1, offsetTable[] = {1,1,1,1,1};
       const char *pDigit = value;
    
       // shorten the value to the first non 'A'
    	while( *++pDigit == 'A' ) size--;
    
       // jump to the least significant digit
       pDigit+= size;
    
       // calculate until most significant digit is 0... 'A'
    	for( digitFrom = *--pDigit - 'A'; digitTo ; digitFrom = digitTo )
    	{
    
          do
          {
          	// normalize digit in [A,E] to [0,4]... and move ptr to next digit
       		digitTo = *--pDigit - 'A';
    
          	// update the offset table before moving to the next level
    			for( int sigma = 5 ; sigma-- ; ) // print if you not sure whats goin on
          		offsetTable[ sigma - 1 ]+= offsetTable[ sigma ] ;
                
          }while( digitTo == digitFrom );
    
          // predict how much numbers would be jumped fo such a move
          count+= offsetTable[ digitTo ] - offsetTable[ digitFrom ];
    
          // Have a look at what is going on
          //gotoxy( 5,5);
          //cprintf("%d %d %s\n", count,offsetTable[ digitTo ] - offsetTable[ digitFrom ],pDigit);
          //getch();
    	}
       // CODE ENDS
    
       finish    =    clock();
    	printf("selcount = %d", count);
    
       elapsed_time = (double)(finish - start) / CLOCKS_PER_SEC;
       printf( "\nProgram takes %3.4f seconds.\n", elapsed_time );
    
       //getch();
       return 1;
    }

  9. #29
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    A direct approach, I am impressed . This is algorithmic genius.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  10. #30
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Thumbs up

    Credit when credit is due, so Respects due!


    And I beg for your explanation.

    However, despite the code being short and clear, I will not understand by explanation, I will have to debug it for myself
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •