Thread: Array Comparison and Modification

  1. #46
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by laserlight View Post
    Okay, looking through this thread again, I see that other than your solution in post #19, which is admittedly more complicated than necessary, your solutions use an extra array when this can be done in-place. Why not try for a simpler in-place solution? It seems that you are close. You could re-read Adak's post #9, but note that "move all the higher numbers, down by one index" is an unnecessary step.
    An in-place solution would surely reduce space complexity and as this would be a divide and conquer method, time complexity may improve. A good proposition indeed.Working out now .

  2. #47
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by std10093 View Post
    It seems ok

    I would throw away k and use i in lines 42 to 49.
    Like this
    Code:
     i = MAXVALUE;
     while(i!=0)
        {
            if(newArray[i]==lastVal)
            {
                readCounter--;
            }
            i--;
        }
    Another thing I would change is this
    Code:
    while(i!=MAXVALUE)
        {
            newArray[i]=lastVal;
            i++;
        }
    to this (since we know how many loops are going to be done, we should use for loop. Using while loop is not wrong. )
    Code:
    for( i = 0 ; i < MAXVALUE i++)
    {
            newArray[i]=lastVal;
    }
    As a result, I would change also the part that I used i instead of k.
    Code:
     i = MAXVALUE;
     while(i!=0)
        {
            if(newArray[i]==lastVal)
            {
                readCounter--;
            }
            i--;
        }
    to this
    Code:
     i = MAXVALUE;
     for( i = MAXVALUE ; i > 0 ; i--)
    {
            if(newArray[i]==lastVal)
            {
                readCounter--;
            }
    }

    I run it without changing your code and I got
    Code:
    Macintosh-c8bcc88e5669-9:~ usi$ ./px
    Please enter 10 numbers.
    1
    1
    1
    1
    14
    5
    6
    7
    3
    4
    1  14  5  6  7  3  4  1693429850  
    The number of steps: 6.
    The new array length is 8.
    Also when you print the new array length put a newline to the printf
    Wow ! I will change and try to fix the bug .

    EDIT:
    for( i = 0 ; i < MAXVALUEi++)

    { newArray[i]=lastVal; }
    You missed a semicolon there .
    Last edited by Debojyoti Das; 12-22-2012 at 10:00 AM.

  3. #48
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I will help a bit
    What does this line do?
    Code:
    lastVal=arrSeries[MAXVALUE];
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #49
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Debojyoti Das
    An in-place solution would surely reduce space complexity
    Of course

    Quote Originally Posted by Debojyoti Das
    and as this would be a divide and conquer method
    You don't need to use a divide and conquer strategy here.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #50
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Edited. Returns correct results for me . Added a newline character as well .

    Code:
    #include <stdio.h>#include <stdlib.h>
    #define MAXVALUE 10
    int compact (int[], int);
    int main()
    {
        int arrSeries[MAXVALUE], i=0, newArrayLength;
        int arrLength = MAXVALUE;
        printf("Please enter %d numbers.\n", MAXVALUE);
        while(i != MAXVALUE)
        {
            scanf("%d", &arrSeries[i]);
            i++;
        }
        newArrayLength=compact(arrSeries, arrLength);
        printf("The new array length is %d.\n", newArrayLength);
        getchar();
        return 0;
    }
    int compact(int arrSeries[], int arrLength)
    {
        int i=0, j= 0, counter=0, newArray[MAXVALUE], lastVal, readCounter=MAXVALUE;
        lastVal=arrSeries[(MAXVALUE-1)];
        lastVal++;
        for( i = 0 ; i < MAXVALUE; i++)
            {
                newArray[i]=lastVal;
            }
        newArray[0]=arrSeries[0];
        for(i = 0; i != arrLength; i++)
            {
                if(newArray[j] != arrSeries[i])
                {
                    newArray[++j] = arrSeries[i];
                }
            }
        i=MAXVALUE;
        for( i = MAXVALUE ; i > 0 ; i--)
            {
                if(newArray[i]==lastVal)
                {
                    readCounter--;
                }
            }
        while(counter <= readCounter)
            {
                printf("%d  ", newArray[counter]);
                counter++;
            }
        printf("\nThe number of steps: %d.\n", j);
        return ++readCounter;
    }

    Please enter 10 numbers.1
    1
    1
    1
    14
    5
    6
    7
    3
    4
    1 14 5 6 7 3 4
    The number of steps: 6.
    The new array length is 7.
    Process returned 0 (0x0) execution time : 21.715 s
    Press any key to continue.

    Last edited by Debojyoti Das; 12-22-2012 at 10:09 AM.

  6. #51
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by std10093 View Post
    I will help a bit
    What does this line do?
    Code:
    lastVal=arrSeries[MAXVALUE];
    Out of bounds . Silly me.

  7. #52
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Everybody has gone out of bounds The important thing is that you fixed it, doesn't that feel great?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  8. #53
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by laserlight View Post
    You don't need to use a divide and conquer strategy here.
    Not exactly divide and conquer but my approach will be to divide the partition into repeating sets and then put one instance for the same and keep the non-repeating sets as is. I think it might be faster than before.

  9. #54
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by std10093 View Post
    Everybody has gone out of bounds The important thing is that you fixed it, doesn't that feel great?
    It surely does ! Thanks .

  10. #55
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Good that you noticed the out of bounds access. Now, test your program with input:
    Code:
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

    EDIT:
    Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.
    Last edited by laserlight; 12-22-2012 at 10:21 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #56
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by laserlight View Post
    Good that you noticed the out of bounds access. Now, test your program with input:
    Code:
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

    EDIT:
    Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.
    Just to do replace the garbage values I guess. And in my version of the code I get the reduced range based on my lastVal thingy. I do recognize that other workarounds are possible and I will try another way in the method you cited for getting the reduced range.
    As off the data set you presented, it works perfectly for me:
    Please enter 10 numbers.2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    2 1
    The number of steps: 1.
    The new array length is 2.

    Process returned 0 (0x0) execution time : 5.382 s
    Press any key to continue.

    Last edited by Debojyoti Das; 12-22-2012 at 10:55 AM.

  12. #57
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Debojyoti Das
    Just to do replace the garbage values I guess.
    But all that you are doing is replacing the garbage values with other garbage values.

    Quote Originally Posted by Debojyoti Das
    And in my version of the code I get the reduced range based on my lastVal thingy.
    That is only because you did not recognise that j + 1 is your reduced range's length.

    Quote Originally Posted by Debojyoti Das
    As off the data set you presented, it works perfectly for me:
    Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #58
    Registered User
    Join Date
    Dec 2012
    Posts
    32
    Quote Originally Posted by laserlight View Post
    But all that you are doing is replacing the garbage values with other garbage values.


    That is only because you did not recognise that j + 1 is your reduced range's length.


    Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?
    Whoa..now I recognize it. Thanks for the take .

  14. #59
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You're welcome

    Now, as you figure out a simpler in-place algorithm, I'd like to return to the idea that functions should do one thing and do it well. For example, this was the program I wrote to test:
    Code:
    #include <stdio.h>
    
    size_t read_numbers(int numbers[], int max_size)
    {
        size_t i = 0;
        printf("Please enter up to %d integers (trigger EOF to stop early).\n", max_size);
        while (i < max_size && scanf("%d", &numbers[i]) == 1)
        {
            ++i;
        }
        return i;
    }
    
    void print_numbers(const int numbers[], size_t size)
    {
        size_t i;
        printf(">>> ");
        for (i = 0; i < size; ++i)
        {
            printf("%d ", numbers[i]);
        }
        printf("<<<\n");
    }
    
    size_t compact(int numbers[], size_t size)
    {
        size_t i, j;
        if (size <= 1)
        {
            return size;
        }
    
        /* omitted for instructional purposes */
    }
    
    int main(void)
    {
        int numbers[10];
        size_t size = read_numbers(numbers, sizeof(numbers) / sizeof(numbers[0]));
        size = compact(numbers, size);
        print_numbers(numbers, size);
        return 0;
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #60
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    Still working on this, I see. I was hoping that by the time you finished implementing the step-counting you would have realized how simply (and efficiently) you could complete the assignment with only a minor modification to your original program. Does this give you a hint?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Character Array Comparison
    By programit in forum C Programming
    Replies: 2
    Last Post: 01-31-2011, 12:30 PM
  2. Help on array comparison
    By sivapc in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2009, 09:54 AM
  3. Scanf confusion, 2 dimensional array modification
    By Leojeen in forum C Programming
    Replies: 23
    Last Post: 10-19-2008, 10:58 PM
  4. array comparison
    By cloudy in forum C Programming
    Replies: 2
    Last Post: 10-16-2004, 02:45 PM
  5. array comparison
    By battoujutsu in forum C Programming
    Replies: 12
    Last Post: 12-05-2003, 11:47 AM

Tags for this Thread