Page 1 of 4 123 ... LastLast
Results 1 to 10 of 39

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

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

    Default C/C++ Test - Category Looping & Optimising - Level Medium

    You are given a text input like

    Code:
    6
    ABBCCD
    The first line has a number which displays the number of characters in the second line. Any given positive number from 1 to 128 can be the first line

    The srtring in the second line has the same behaviour as in the previous problem. Find the position which this string has if it was in an ordered set, where AAAAAA is numbered 1. So what number does the string in the second line has?

    In addtion the time taken to calculate this number must be displayed, so write the code as efficient as possible. Progam by any means necessary. Unorthodox! I will post a starting off of the program, nothing much
    Last edited by crosswire; Apr 22, 2005 at 11:13 AM. Reason: limited the range of first number
    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

  2. #2
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    Shouldn't the first line be 6?
    Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
    Bold 9700 - OS6.0.0.448

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

    Default

    Yes. I also limited the range of it too

    Code:
    #include "stdafx.h"
    #include <time.h>
    #include <string.h>
    
    void main(int argc, char* argv[])
    {
    	//Time declarations
    	time_t	start, finish;
    	double	elapsed_time;
    
    	//Input declarations
    	FILE *	stream;
    	stream	=	fopen( "input.txt", "r" );
    
    	//Getting the first number
    	int		N;
    	fscanf(stream, "%d", &N);
    
    	//Getting the test string
    	char	S[129];
    	fscanf(stream, "%s", &S);
    
    	time( &start );
    	//code start here
    
    
    	//code
    	//code
    	//code
    	//code
    
    
    	//code end here
    	time( &finish );
    
    	elapsed_time = difftime( finish, start );
    	printf( "\nProgram takes %6.0f seconds.\n", elapsed_time );
    
    
    }
    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

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

    Default

    @nigelt

    You can use a state class for your loop counters, and let N counters be defined in the state, The counters follow the same pattern as if N loops had them Use any means you think necassary.

    Code:
    100
    AAAAAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDEEEEEEEEEEEE
    will give a result of
    Position = 2403193
    Program takes 4 seconds.
    Press any key to continue
    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

  5. #5
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    OK.....will attempt this when I get back. Looks pretty challenging.
    Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
    Bold 9700 - OS6.0.0.448

  6. #6
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    It was a real challenge. Spent a good while on it.
    String found at position 2403193
    1.000 seconds.

    Sorry for the lack of comments.

    Code:
    //written by Nigel Thomas 22/4/2005
    //Compiler: Microsoft Visual C++ 6.0 
    
    #include <stdio.h>
    #include <string.h>
    #include <time.h>
    
    void loop(char[]);
    FILE *ptr;
    int num,check,count=1;
    void main(){
    
    	time_t start,finish;
    	double total_time;
    	
    	int a=0,b=0;
    	int x,y=0;
    
    	char data[129],temp[129],base[129];
    
    	if( (ptr=fopen("input.dat","r"))==NULL)
    		printf("Error opening file");
    
    	else{
    		fscanf(ptr, "%d %s", &num, data);
    		fclose(ptr);
    	
    	
    	        time(&start);
    
    	        temp[num]='\0';
    	        base[num]='\0';
    	        check=num-1;
    
    	        for(x=0;x<num;x++){
    		
    		       temp[x]='A';
    		       base[x]='E';
    	
    	         }
    	
    	         while(strcmp(temp,base)!=0){ 
    
    		        for(y=temp[num-1];y<'E';y++){
    			    if(strcmp(temp,data)==0)
    				break;
    			    count++;
    			   temp[num-1]++;
    			
    		
    		        }
    		        if(strcmp(temp,data)==0)
    				break;
    		       loop(temp);
    	
    
    	          }
    	         printf("%s ",temp);
    	         printf("\nString found at position %d ",count);
    
    	         time(&finish);
    
    	         total_time=difftime(finish, start);
    	         printf("\n%.3f seconds\n",total_time);
            }
    }
    
    void loop(char temp[]){
    	int y;
    	static int h=2;
    	if(temp[check]=='E' && temp[num-1]=='E'){
    		check--;
    		temp[check]++;	
    		for(y=check;y<=num-1;y++){
    			temp[y] = temp[check];
    		}
    	
    	}
    	else if(temp[num-1]=='E' && temp[check]!='E' && check<(num-2)){
    		if(temp[check+1] != 'E'){
    			check=num-h;
    			temp[check]++;
    			for(y=check;y<=num-1;y++){
    				temp[y] = temp[check];
    			}
    		}
    		else{
    			temp[check]++;
    			for(y=check;y<=num-1;y++){
    				temp[y] = temp[check];
    			}
    		}
    	}
    	else if(temp[num-1]=='E' && temp[check]!='E'){
    		temp[check]++;
    		for(y=check;y<=num-1;y++){
    			temp[y] = temp[check];
    		}
    	}
    	else temp[check]++;
    	count++;
    
    
    }
    Last edited by nigelt; Apr 23, 2005 at 09:53 AM. Reason: corrected bracket position for first if else condition
    Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
    Bold 9700 - OS6.0.0.448

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

    Thumbs up

    Wow

    That was good. On my machine the code gives me 0 sec to calculate. And you finished it in one day and I know that it less than that amount of time you spent on it.

    I hope that I can understand your implementation and that we could discuss it.
    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. #8
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    OK, after I watched a movie I took a look at it through the debugger and I think I understood it.

    Because of the short time that it takes, I am inspired to write more optimised code.

    What is even extremely fascinating is that you followed the instructions to the tee, which is harder to do than to write whatever code you wanted. The latter was the freedom that I wanted to see, but it was my mistake for not laying out the problem better. I give you all the props for your implementation.

    My perspective on the problem: If N is known to be fixed, say N=3, then a loop in a loop in a loop would do the job. But when N can be any number you can use an array of counters, where the first counter in the array represents the innermost loop, and the last counter in the array represent the outer most loop, basically. You can use that to set up variable amount of loops when the loops have a common stopping condition. Your (nigelt's) use of the loop() function is an implementation of this. temp that is passed to the loop function represents the state of all the counters of up to 128 loops!!! The next part of the problem is to increment the counters in the pattern of the selection, eg when counter 6 reaches 'E' then counter 6 = 'B' and counters 7 to 128 = 'E' or whatever value. This was done by the loop function.
    Eg
    counter
    0 0 0 0 0 0
    0 0 0 0 0 1
    0 0 0 0 0 2
    0 0 0 0 0 3
    0 0 0 0 0 4
    0 0 0 0 0 5
    0 0 0 0 1 0

    and so on.

    This problem is indeed difficult and you are good to have completed it. You decoded the pattern and implemented a correct and efficient loop. I hope that you got experience that you could use later. Remember for varying loops that you can use a state array. There are many kinds of such varying depth loops, but I do not encounter them often. I hope you understand what I am saying because I cannot think of any other example at this time other than in this problem.
    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

  9. #9
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    Thanks. I'll definitely be saving this challenge and the solution for future reference! Figuring out how to increment the temp string correctly took me a couple hours well.
    I think I understand what you're saying about the state array. I'll read up on it. Maybe if you post your solution I'll understand it better. Does anyone else have another method of solving this?
    Last edited by nigelt; Apr 23, 2005 at 10:26 AM.
    Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
    Bold 9700 - OS6.0.0.448

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

    Default

    I used a class xary_number which saves the state of the counters. However, it does this in numeric form, and not in letters. Eg ABC would have counter values of 012.
    A xary number that has base 5 is used. This number could be incremented by 1, or it can go to the next possible selection, ie from 114 to 122. It can also be used to sleep a loop because it saves the state of the loop and then awake the loop when ready.

    The principle is that this type of number represents the state of any arbituary number of loops. A for loop then traverses the counters in this number and so doing control all the loops that are present. This for loop increments counters that needs to be incremented and zeroes those that need to be zeroed and so on; this for loop applies the counter pattern for a fixed number of loops to a larger amount of loops. This was what you end up implementing to get the variable amount of loops. OK the problem corny still, but you did it and you did it correctly. It is a bigger achievement than what it looks like.

    I made up the problem as far as I know, so I do not think it is in a book .

    My code is similar to yours, but it is not as fast because of poor looping technique

    Code:
    // Complier VC6.0
    
    
    
    #include <time.h>
    #include <string.h>
    #include <stdio.h>
    
    
    
    
    /*
    An xary number is a number which has the base x
    Eg Binary numbers, x = 2
    xary numbers can have any base and any lenght
    */
    
    
    #include <memory.h>
    
    class    xary_number
    {
    private:
        bool    xary_number_is_zero;
        bool    xary_number_is_max;
        bool    xary_number_is_init;
        int     max_digit_val;  //eg for decimal number, max digit val is 9
    
        int *   digit;          //All digits in the binary number, eg decimal 3457224024
        int     xary;           //The base of the number eg binary, octal, etc for now only boolean
        int     lengthneeded;   //The number of digits in the number, eg 256 digit hexal, 11 digit hexal
    
    public:
        xary_number(int x = 2, int l = 256)
        {
            xary_number_is_init    =    false;
            init_xary_number(x, l);
        };
        ~xary_number()
        {
            delete []    digit;
        };
    
        void init_xary_number(int x = 2, int l = 256)
        {
            //Initialize number
            xary             =    x;
            lengthneeded     =    l;
    
            max_digit_val    =    x - 1;//1 for binary
    
            //create the space for our digits
            if(xary_number_is_init)
                delete [] digit;
            digit    =    new int[lengthneeded];
    
            //Zero the digits
            memset(digit, 0x00, lengthneeded*sizeof(int));
    
            //Initialize some miscellaneous states
            xary_number_is_zero    =    true;
            xary_number_is_max     =    false;
            xary_number_is_init    =    true;
        }
    
        bool goto_next_selection()    //follows the pattern 000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, 113, 122, 123, 133, 222, 223, 233, 333 for a 4ary number
        {
            for(int i = 0; i < lengthneeded; i++)
            {
                if(digit[i] == max_digit_val)
                {
                    digit[i]    =    0;
                    continue;
                }
                else
                {
                    digit[i]++;
                    //all previous digit equal this digit
                    for(; i > 0; i--)
                    {
                        digit[i-1]    =    digit[i];
                    }
                    break;
                }
            }
    
            //Sets the miscellaneous state to zero if the number overflows to zero
            set_if_zero();
    
            //Returns the miscellaneous state
            return    is_zero();
        }
    
        //Sets xary_number_is_zero to zero if the number has all digits at zero.
        void set_if_zero()
        {
            for(int i = 0; i < lengthneeded; i++)
            {
                if(digit[i] != 0)
                {
                    xary_number_is_zero    =    false;
                    return;
                }
            }
            xary_number_is_zero    =    true;
            return;
        }
    
        bool is_zero() const
        {
            return    xary_number_is_zero;
        }
    
    
        //Get a display string of the xary number
        //If display charcters are given they\n will replace the digit characters
        //The lenght of the display string should be 1 greater than the lenght of the xary_number
        //The number of display characters should be the same as the base of the xary number
        void get_display_string(char * display_string, const char * display_characters) const
        {
            for(int i = 0; i < lengthneeded; i++)
            {
                //Print the highest digit in the first position of the string
                display_string[i]    =    display_characters[digit[lengthneeded-i-1]];
            }
            display_string[i]    =    0x00;
        }
    };
    
    
    
    
    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;
        }
    
        //Getting the first number
        int        N;
        fscanf(stream, "%d", &N);
    
        //Getting the test string
        char    S[129];
        fscanf(stream, "%s", &S);
    
        fclose(stream);
    
    
        time( &start );
        //code start here
    
        const char    display_chs[]    =    "ABCDE";
    
        xary_number        sel;
        int                selcount    =    0;
    
        sel.init_xary_number(strlen(display_chs), N);
    
        char        display_str[256];
    
        while(true)
        {
            //selcount is the position counter
            selcount++;
    
            //sel has the state of all the counters, and get_display_string prints its state in text form, eg 0012 to AABC
            sel.get_display_string(display_str, display_chs);
    
            //display str is the text format of the counters; checking it with the base string
            if(!(strcmp(display_str, S)))
                break;
    
            //go from AAA to AAB...AAE to ABB
            if(sel.goto_next_selection())
                break;
        }
    
        printf("selcount = %d", selcount);
        //code end here
    
        time( &finish );
    
        elapsed_time = difftime( finish, start );
        printf( "\nProgram takes %6.0f seconds.\n", elapsed_time );
    
    
        return    1;
    
    }
    Last edited by crosswire; Apr 23, 2005 at 02:31 PM.
    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
  •