reverse a string with 0 terminator in one pass

[dbtouch]

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

 

[red floyd]

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

 

[joecook]

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

 

[dbtouch]

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;
}

 

[Christof Donat]

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]

Hi, Christof

Yours is two passes.

dbtouch

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]

Hi, Jeff

My answer works but not as what is expected.

dbtouch

 

[Sana]

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

 

[Juha Nieminen]

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.

 

[joecook]

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

 

[Juha Nieminen]

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.

 

[Andrey Tarasevich]

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.

 

[paulkp]

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;
}

 

[Christof Donat]

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

 

[James Kanze]

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.

 

[Christof Donat]

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 :-(

 

[James Kanze]

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.

 

[Pascal J. Bourguignon]

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.

 

[Gert-Jan de Vos]

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..

 

[Juha Nieminen]

Is this ok?

std::string dest;

What do you think that 'dest' is if not auxiliary memory?