reverse a string with 0 terminator in one pass

Discussion in 'C++' started by dbtouch, Mar 3, 2009.

  1. dbtouch

    dbtouch Guest

    Hi, C++ programmers

    I have been thinking solution for this problem: to reverse a string
    with 0 terminator in one pass without using auxillary memory. My
    initial thought is to use recursion, but I have not succeeded finding
    an answer. Notice that if you use strlen, it will be considered as one
    pass. Could you give me some clues?

    dbtouch
    dbtouch, Mar 3, 2009
    #1
    1. Advertising

  2. dbtouch

    red floyd Guest

    dbtouch wrote:
    > Hi, C++ programmers
    >
    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory. My
    > initial thought is to use recursion, but I have not succeeded finding
    > an answer. Notice that if you use strlen, it will be considered as one
    > pass. Could you give me some clues?


    You can find a good solution here:

    http://www.parashift.com/c -faq-lite/how-to-post.html#faq-5.2
    red floyd, Mar 3, 2009
    #2
    1. Advertising

  3. dbtouch

    Guest

    On Mar 3, 1:07 pm, dbtouch <> wrote:
    > Hi, C++ programmers
    >
    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory. My
    > initial thought is to use recursion, but I have not succeeded finding
    > an answer. Notice that if you use strlen, it will be considered as one
    > pass. Could you give me some clues?
    >
    > dbtouch


    Sounds easy. How much is the job worth?

    Joe C
    , Mar 3, 2009
    #3
  4. dbtouch

    dbtouch Guest

    Hi, Jeff

    This is my answer. I was given a clue that: "Why are you doing a swap
    when the stack reverses everything for you? You can make a helper
    function to help you." Any suggestion?

    Thanks,

    dbtouch

    int reverse(char*& line) {
    char tmp;
    if (line==NULL)
    return 0;
    char* first=line;
    char* last=first+1;

    if (*last==0) {
    return 1;
    }
    tmp=*first;
    int len=reverse(last);
    for (int i=0; i<len; i++) {
    *first=*last;
    first++;
    last++;
    }
    *first=tmp;
    return len+1;
    }



    On Mar 3, 1:17 pm, Jeff Schwab <> wrote:
    > dbtouch wrote:
    > > I have been thinking solution for this problem: to reverse a string
    > > with 0 terminator in one pass without using auxillary memory. My
    > > initial thought is to use recursion, but I have not succeeded finding
    > > an answer. Notice that if you use strlen, it will be considered as one
    > > pass. Could you give me some clues?

    >
    > Do you count the unwinding of the recursion as a second pass?
    dbtouch, Mar 3, 2009
    #4
  5. Hi,

    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory. My
    > initial thought is to use recursion, but I have not succeeded finding
    > an answer. Notice that if you use strlen, it will be considered as one
    > pass. Could you give me some clues?


    Is there a good reason why you necessarily need to have only one pass? Since
    a second pass like strlen() does not increase the complexity, I'd expect
    that the more complex algorithm takes away any performance boost.

    Note that after having used strlen() you only need n/2 steps:

    void strreverse(char* buf) {
    int len = strlen(buf);

    for( i = 0; i <= len/2; i++ ) {
    char tmp = buf;
    buf = buf[len-i];
    buf[len-1] = tmp;
    }
    }

    As you see this only takes 1,5 passes.

    Christof
    Christof Donat, Mar 3, 2009
    #5
  6. dbtouch

    dbtouch Guest

    Hi, Christof

    Yours is two passes.

    dbtouch

    On Mar 3, 4:08 pm, Christof Donat <> wrote:
    > Hi,
    >
    > > I have been thinking solution for this problem: to reverse a string
    > > with 0 terminator in one pass without using auxillary memory. My
    > > initial thought is to use recursion, but I have not succeeded finding
    > > an answer. Notice that if you use strlen, it will be considered as one
    > > pass. Could you give me some clues?

    >
    > Is there a good reason why you necessarily need to have only one pass? Since
    > a second pass like strlen() does not increase the complexity, I'd expect
    > that the more complex algorithm takes away any performance boost.
    >
    > Note that after having used strlen() you only need n/2 steps:
    >
    > void strreverse(char* buf) {
    >         int len = strlen(buf);
    >
    >         for( i = 0; i <= len/2; i++ ) {
    >                 char tmp = buf;
    >                 buf = buf[len-i];
    >                 buf[len-1] = tmp;
    >         }
    >
    > }
    >
    > As you see this only takes 1,5 passes.
    >
    > Christof
    dbtouch, Mar 3, 2009
    #6
  7. dbtouch

    dbtouch Guest

    Hi, Jeff

    My answer works but not as what is expected.

    dbtouch

    On Mar 3, 3:52 pm, Jeff Schwab <> wrote:
    > dbtouch wrote:
    >
    >  > On Mar 3, 1:17 pm, Jeff Schwab <> wrote:
    >
    >  >> dbtouch wrote:
    >
    >  >>> I have been thinking solution for this problem: to reverse a
    >  >>> string with 0 terminator in one pass without using auxillary
    >  >>> memory. My initial thought is to use recursion, but I have not
    >  >>> succeeded finding an answer. Notice that if you use strlen, it
    >  >>> will be considered as one pass.
    >
    >  > This is my answer. I was given a clue that: "Why are you doing a
    >  > swap when the stack reverses everything for you?  You can make a
    >  > helper function to help you." Any suggestion?
    >
    >  >   int reverse(char*& line) {
    >
    > Why pass the pointer by reference?
    >
    >  >           char tmp;
    >  >           if (line==NULL)
    >  >                   return 0;
    >  >           char* first=line;
    >  >           char* last=first+1;
    >  >
    >  >           if (*last==0) {
    >  >                   return 1;
    >  >           }
    >
    > I'm afraid you've already got a problem here.  Suppose reverse were
    > passed an empty string, i.e. "", an array whose only element is '\0'.
    > The pointer, last, is already past the end of the array when you
    > dereference it.  Consider making the empty string your base case, rather
    > than a string of size 1.
    >
    >  >           tmp=*first;
    >  >           int len=reverse(last);
    >  >           for (int i=0; i<len; i++) {
    >  >                   *first=*last;
    >  >                   first++;
    >  >                   last++;
    >  >           }
    >
    > Full disclosure:  I have not written a solution to this problem.  I am
    > nevertheless going to suggest that you should not need any loops to
    > traverse the strings, since the recursion is already doing the traversal.
    >
    >  >           *first=tmp;
    >  >           return len+1;
    >  >   }
    dbtouch, Mar 3, 2009
    #7
  8. dbtouch

    Sana Guest

    On Mar 3, 3:33 pm, dbtouch <> wrote:
    > Hi, Jeff
    >
    > This is my answer. I was given a clue that: "Why are you doing a swap
    > when the stack reverses everything for you?  You can make a helper
    > function to help you."
    >


    Great clue right there. It implies some sort of recursion. So, what
    does reversing implies?
    Set the value of element in position [strlen(string) - i - 1] with the
    value of the element in the position i
    hmm, how do we get the length of the string without using strlen? we
    call recursively our helper function, each time with an incremented
    index into the string until we reach the end of the string. Once we
    are there, we return the length (the index of the element with the
    value '\0'). Upon returning we now know the length of the string.

    // what index do we start with?
    int processString(int index, char* string)
    {
    // you need to do store something in a variable here

    if (string[index] == '\0')
    return index; // the length of the string

    // not at the end of the string - call same function recursively
    with an incremented index
    int stringLength = processString(index + 1, string);

    // here you have the index and the length
    // see how you can use them to set the element [len - i - 1]
    // you will need the value stored in the variable at the begining
    of the function

    return stringLength;
    }

    HTH

    --
    sana
    Sana, Mar 3, 2009
    #8
  9. dbtouch wrote:
    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory. My
    > initial thought is to use recursion, but I have not succeeded finding
    > an answer.


    If you use recursion, you *are* using auxiliary memory. Granted, the
    auxiliary memory will be in allocated in the stack rather than the heap,
    but that's only a rather minor technical difference.

    And if we are talking about efficiency, the recursion will use way
    more memory than an iterative solution using an auxiliary block of
    memory allocated on the heap of the size of the string. The recursive
    solution will probably also be slower.

    Also a recursive solution will consist of two passes: One from the
    beginning of the string to the end, and then another from the end to the
    beginning (when unwinding the recursion), even if the latter pass is a
    bit hidden at first sight.

    I don't even think the problem is solvable strictly in one single pass
    even if you are allowed to use additional memory freely.
    Juha Nieminen, Mar 3, 2009
    #9
  10. dbtouch

    Guest

    On Mar 3, 3:33 pm, dbtouch <> wrote:
    > Hi, Jeff
    >
    > This is my answer. I was given a clue that: "Why are you doing a swap
    > when the stack reverses everything for you?  You can make a helper
    > function to help you." Any suggestion?
    >
    > Thanks,
    >
    > dbtouch
    >
    >         int reverse(char*& line) {
    >                 char tmp;
    >                 if (line==NULL)
    >                         return 0;
    >                 char* first=line;
    >                 char* last=first+1;
    >
    >                 if (*last==0) {
    >                         return 1;
    >                 }
    >                 tmp=*first;
    >                 int len=reverse(last);
    >                 for (int i=0; i<len; i++) {
    >                         *first=*last;
    >                         first++;
    >                         last++;
    >                 }
    >                 *first=tmp;
    >                 return len+1;
    >         }
    >


    Oh, you are using temporaries. I thought that would be "auxiliary
    memory". You can reverse the string without using any temporary data
    at all. (which is a much more fun problem)
    Joe C
    , Mar 4, 2009
    #10
  11. wrote:
    > Oh, you are using temporaries. I thought that would be "auxiliary
    > memory". You can reverse the string without using any temporary data
    > at all. (which is a much more fun problem)


    Do you mean it's possible to reverse the string without using
    recursion and without allocating O(n) memory and which traverses the
    string only once?

    Or are you not counting the recursion stack as "auxiliary memory"? Why
    not? What's the difference? In fact, the recursion stack will allocate
    significantly *more* memory than an iterative solution which temporarily
    allocates an auxiliary string from the heap.
    Juha Nieminen, Mar 4, 2009
    #11
  12. dbtouch wrote:
    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory. My
    > initial thought is to use recursion, but I have not succeeded finding
    > an answer.


    A _defining_ property of algorithmic recursion is non-constant auxiliary
    memory requirement. If recursion uses "no auxiliary memory" (or constant
    amount of auxiliary memory) then it is a "fake" recursion - a completely
    unnecessary forced application of syntactic recursion (language
    recursion) when there's really no actual recursion in the algorithm.

    In other words, under the more-or-less strict interpretation of the
    terms you used in the statement of your problem, it has no solution. You
    need to clarify what is really needed.

    --
    Best regards,
    Andrey Tarasevich
    Andrey Tarasevich, Mar 4, 2009
    #12
  13. dbtouch

    Guest

    On 3 maalis, 20:07, dbtouch <> wrote:
    > I have been thinking solution for this problem: to reverse a string
    > with 0 terminator in one pass without using auxillary memory.


    Is this ok?

    #include <string>
    #include <iostream>

    int main(int argc, char *argv[])
    {
    char str[]="Reverse string.";
    std::string dest;

    int p=0;
    while (str[p]!=0)
    {
    dest.insert(dest.begin(), str[p]);
    p++;
    }
    dest.push_back(0);

    std::cout << dest;

    system("PAUSE");
    return EXIT_SUCCESS;
    }
    , Mar 4, 2009
    #13
  14. Hi,

    > Yours is two passes.


    I'm Impressed, you found out. If you had read my text, you would have found
    out as well without looking at the code. I guess what you whant is something
    like this:

    int strreverse_helper(char* str, int i) {
    int l = i;
    if( str[i+1] !== 0 )
    l = strreverse_helper(str,i+1);
    if( i > l/2 ) {
    char tmp = str;
    str = str[l-i];
    str[l-i] = tmp;
    }
    return l;
    }

    void strreverse(char* str) {
    strreverse_helper(str,0);
    }

    but that has exactly the same complexity and uses more memory on the stack.
    It just looks like one pass, because it divides the two passes in small
    steps which are then interleaved.

    Christof
    Christof Donat, Mar 4, 2009
    #14
  15. dbtouch

    James Kanze Guest

    On Mar 3, 7:17 pm, Jeff Schwab <> wrote:
    > dbtouch wrote:
    > > I have been thinking solution for this problem: to reverse a string
    > > with 0 terminator in one pass without using auxillary memory. My
    > > initial thought is to use recursion, but I have not succeeded finding
    > > an answer. Notice that if you use strlen, it will be considered as one
    > > pass. Could you give me some clues?


    > Do you count the unwinding of the recursion as a second pass?


    Do you count the memory used on the stack for recursion as
    auxillary memory? It will certainly be more than the length of
    the string.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Mar 4, 2009
    #15
  16. Hi,

    >> if( str[i+1] !== 0 )

    >
    > Two problems here:
    > 1) It's undefined behavior if str is "".


    Yes. I didn't mean to publish perfect code here, but a sketch of an
    algorithm.

    > 2) There's no !== operator. Just write if (str[i+1]).


    Sorry, I had too much PHP and JavaScript lately :-(
    Christof Donat, Mar 4, 2009
    #16
  17. dbtouch

    James Kanze Guest

    On Mar 4, 12:40 am, Juha Nieminen <> wrote:
    > dbtouch wrote:
    > > I have been thinking solution for this problem: to reverse a string
    > > with 0 terminator in one pass without using auxillary memory. My
    > > initial thought is to use recursion, but I have not succeeded finding
    > > an answer.


    > I don't even think the problem is solvable strictly in one
    > single pass even if you are allowed to use additional memory
    > freely.


    Sure it is:

    void
    reverse( char* source )
    {
    std::size_t cap = 32 ;
    char* result
    = static_cast< char* >( std::malloc( cap + 1 ) ) ;
    assert( result != NULL ) ;
    *result = 0 ;
    for ( std::size_t i = 0 ; source[ i ] != '\0' ; ++ i ) {
    if ( cap <= i ) {
    cap += cap / 2 ;
    result = static_cast< char* >(
    realloc( result, cap + 1 ) ) ;
    assert( result != NULL ) ;
    }
    std::memmove( result + 1, result, i + 1 ) ;
    result[ 0 ] = source[ i ] ;
    }
    std::strcpy( result, source ) ;
    std::free( result ) ;
    }

    Obviously, it's not the most efficient solution in the world.
    But artificial constraints (only one pass) can artificially
    increase runtime. (Of course, you really have two passes
    anyway. The first, generating the reversed string, and the
    second, copying the results back into the original.)

    Of course, if all that counts is what's in your own code:

    void
    reverse( char* source )
    {
    std::string tmp( source ) ;
    std::reverse( tmp.begin(), tmp.end() ) ;
    std::strcpy( source, tmp.c_str() ) ;
    }

    Which is probably more efficient than my code, above, but I'm
    willing to bet that there's a call to strlen hidden somewhere in
    the constructor of std::string that I use.

    The whole question is, of course, silly. If you're doing any
    string manipulation, you won't loose the size to begin with.
    And if you know the size, you don't need strlen to recalculate
    it, and std::reverse can be used immediately.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Mar 4, 2009
    #17
  18. James Kanze <> writes:

    > On Mar 4, 12:40 am, Juha Nieminen <> wrote:
    >> dbtouch wrote:
    >> > I have been thinking solution for this problem: to reverse a string
    >> > with 0 terminator in one pass without using auxillary memory. My
    >> > initial thought is to use recursion, but I have not succeeded finding
    >> > an answer.

    >
    >> I don't even think the problem is solvable strictly in one
    >> single pass even if you are allowed to use additional memory
    >> freely.

    >
    > Sure it is:
    >
    > void
    > reverse( char* source )
    > {
    > std::size_t cap = 32 ;
    > char* result
    > = static_cast< char* >( std::malloc( cap + 1 ) ) ;
    > assert( result != NULL ) ;
    > *result = 0 ;
    > for ( std::size_t i = 0 ; source[ i ] != '\0' ; ++ i ) {
    > if ( cap <= i ) {
    > cap += cap / 2 ;
    > result = static_cast< char* >(
    > realloc( result, cap + 1 ) ) ;
    > assert( result != NULL ) ;
    > }
    > std::memmove( result + 1, result, i + 1 ) ;
    > result[ 0 ] = source[ i ] ;
    > }
    > std::strcpy( result, source ) ;
    > std::free( result ) ;
    > }


    You are cheating. It all depends on the definition of pass.

    We could agree that one pass is accessing each elements of a vector
    once (let's say one read and one write to each element of a vector).

    The stack is itself to be considered a vector, pushing is writting,
    poping is reading. Hiding a pass inside a function doesn't remove it.

    In your reverse you have three passes at least:
    - malloc may initialize the allocated memory block, 1/2 pass,
    - for loop, 1/2 pass (just reading source),
    - memmove, 1 pass,
    - strcpy, 1 pass.


    The most efficient way to implement it is to scan for the null byte
    (1/2 pass) and to do the reversing (1 pass), for a total of 1.5
    "passes".


    > std::string tmp( source ) ; 1 pass
    > std::reverse( tmp.begin(), tmp.end() ) ; 1 pass
    > std::strcpy( source, tmp.c_str() ) ; 1 pass

    -----------------------------------------------------------


    > Which is probably more efficient than my code, above, but I'm
    > willing to bet that there's a call to strlen hidden somewhere in
    > the constructor of std::string that I use.


    You doubt it?


    > The whole question is, of course, silly.


    Indeed.


    --
    __Pascal Bourguignon__
    Pascal J. Bourguignon, Mar 4, 2009
    #18
  19. On Mar 4, 2:59 pm, (Pascal J. Bourguignon)
    wrote:
    > We could agree that one pass is accessing each elements of a vector
    > once (let's say one read and one write to each element of a vector).
    >
    > The stack is itself to be considered a vector, pushing is writing,
    > popping is reading.  Hiding a pass inside a function doesn't remove it.


    int reverse(char* s, int index = 0)
    {
    char c = s[index];
    if (c == '\0')
    return 0;

    int pos = reverse(s, index + 1);
    s[pos] = c;
    return pos + 1;
    }

    N x string read
    N x stack push
    N x stack pop
    N x string write

    All in one recursive pass using N stacked reverse() instances of
    auxiliary memory.

    I don't think it can be done in a single read-write traversal without
    auxiliary memory.

    And yes, this is a very silly exercise..
    Gert-Jan de Vos, Mar 4, 2009
    #19
  20. wrote:
    > On 3 maalis, 20:07, dbtouch <> wrote:
    >> without using auxillary memory.

    >
    > Is this ok?
    >
    > std::string dest;


    What do you think that 'dest' is if not auxiliary memory?
    Juha Nieminen, Mar 4, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Hirschfield

    Help: asyncore/asynchat and terminator string

    David Hirschfield, Jan 16, 2007, in forum: Python
    Replies:
    0
    Views:
    311
    David Hirschfield
    Jan 16, 2007
  2. TP
    Replies:
    4
    Views:
    143
    Tad McClellan
    Feb 14, 2004
  3. TP
    Replies:
    1
    Views:
    137
    Bob Walton
    Feb 11, 2004
  4. Replies:
    3
    Views:
    162
    Joe Smith
    Jul 17, 2005
  5. Trudge

    Can't find string terminator ...

    Trudge, Oct 23, 2006, in forum: Perl Misc
    Replies:
    21
    Views:
    1,251
    Henry Law
    Oct 26, 2006
Loading...

Share This Page