reverse a string with 0 terminator in one pass
dbtouch
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
Jeff Schwab
Do you count the unwinding of the recursion as a second pass?
red floyd
joe...@gmail.com
Sounds easy. How much is the job worth?
Joe C
dbtouch
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;
Andy Champ
Andy
Jeff Schwab
> On Mar 3, 1:17 pm, Jeff Schwab <j...@schwabcenter.com> 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;
> }
Christof Donat
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[i];
buf[i] = buf[len-i];
buf[len-1] = tmp;
}
}
As you see this only takes 1,5 passes.
Christof
dbtouch
Yours is two passes.
dbtouch
dbtouch
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
--
sana
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.
joe...@gmail.com
>
> 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.
--
Best regards,
Andrey Tarasevich
pau...@mbnet.fi
> 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
> 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[i];
str[i] = 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
Jeff Schwab
> int strreverse_helper(char* str, int i) {
> int l = i;
Why would someone ever call a variable l, right before using the literal
digit 1? It's especially hard to read on Usenet, since most clients
don't perform automatic syntax-highlighting.
> if( str[i+1] !== 0 )
Two problems here:
1) It's undefined behavior if str is "".
2) There's no !== operator. Just write if (str[i+1]).
> l = strreverse_helper(str,i+1);
> if( i > l/2 ) {
> char tmp = str[i];
> str[i] = 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.
You realize you're doing someone's homework, right?
Christof Donat
>> 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
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:james...@gmail.com
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
> 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.
Pascal J. Bourguignon
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__
Gert-Jan de Vos
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).
>
> 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
> On 3 maalis, 20:07, dbtouch <dbto...@gmail.com> wrote:
>> without using auxillary memory.
>
> Is this ok?
>
What do you think that 'dest' is if not auxiliary memory?
joe...@gmail.com
wrote:
> dbtouch wrote:
> 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.
I disagree. I think the solution is obvious. Here is an example of
reversing a string using no auxillary memory at all (no recursion, no
temporaries). I use the Null terminator location as my swap space.
In fact, I do have a loop temporary, but you could easily conceive
this could be eliminated using templates, and a compile time constant
size (this doesn't not violate any of the conditions set forth).
Also, this is only the half that works for even-length strings. I'll
leave the odd lengths as an exercise to the reader.
I only "walk" through the string one time
void reverse(char* input, int size) // size does not include the null
terminator
{
// Walk through the first half.
for(int i=0; i<size/2; ++i)
{
input[size-1] = input[i];
intput[i] = input[size-i-1];
}
// Walk through the rest
for(int i=size/2+1; i<size; ++i)
{
input[i] = input[i+1];
}
input[size] = "\0"; // restore the null terminator
}
int main()
{
char a[] = "Hello!";
reverse(a,6);
}
Joe Cook
joe...@gmail.com
> input[size] = "\0"; // restore the null terminator
Oops, make that '\0';
Also, there is a way to do this same algorithm without a compile time
constant, and also no loop variables, but it's a bit a longer to type
out...
joe Cook
Jeff Schwab
The OP specifically stated that getting the length (actually strlen, but
he clearly meant "getting the length") counted as a pass. If you start
with the length as a given, you're cheating.
joe...@gmail.com
Fine Fine, just change the "reverse" definition to a template
template<std::size_t size>
void reverse(char (&input)[size])
{
...
}
Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question. Next
we'll be asked to write a program telling us if a passed string is of
finite length.
Joe Cook
Jeff Schwab
> template<std::size_t size>
> void reverse(char (&input)[size])
> Using the compiler to tell you the size certainly can't be considered
> "a pass", or this is really getting to be a silly question.
The point was that you don't know the length ahead of time. He also
didn't have a character array, only a char*.
> Next
> we'll be asked to write a program telling us if a passed string is of
> finite length.
That's an easy one, unless you need the answer in finite time. :)
Sana
> wrote:
>
> > dbtouch wrote:
> > 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.
>
> I disagree. I think the solution is obvious. Here is an example of
> reversing a string using no auxillary memory at all (no recursion, no
> temporaries). I use the Null terminator location as my swap space.
> size (this doesn't not violate any of the conditions set forth)
I disagree. The presence of the compile time "size" variable violates
the initial conditions. The OP does not know the length of the string
at compile time. That is why he mentions "to reverse a string with 0
terminator in one pass without using auxillary memory" and "if you use
strlen, it will be considered as one pass" which implies that the
length of the string is given by the position of the '\0' character.
--
sana
Jeff Schwab
dbtouch
James Kanze
It's easier than that, it can be done in constant time:
bool
hasFiniteLength( char const* string )
{
return true ;
}
This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.
:-)
Pascal J. Bourguignon
> Using the compiler to tell you the size certainly can't be considered
> "a pass", or this is really getting to be a silly question.
Of course, it is considered a pass. The specifications didn't says
that passes computed in the programmer brain ("hello!",6), or by the
compiler were allowed, they said that only one pass was to be used.
Indeed, it is a silly question.
--
__Pascal Bourguignon__
Pascal J. Bourguignon
> On Mar 4, 8:51 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
>> joec...@gmail.com wrote:
>> > template<std::size_t size>
>> > void reverse(char (&input)[size])
>> > Using the compiler to tell you the size certainly can't be considered
>> > "a pass", or this is really getting to be a silly question.
>
>> The point was that you don't know the length ahead of time.
>> He also didn't have a character array, only a char*.
>
>> > Next we'll be asked to write a program telling us if a
>> > passed string is of finite length.
>
>> That's an easy one, unless you need the answer in finite time. :)
>
> It's easier than that, it can be done in constant time:
>
> bool
> hasFiniteLength( char const* string )
> {
> return true ;
> }
>
> This will fail, of course, the day machines start having
> infinite memory, but for the moment, we're safe.
Once again, it depends on how you define the length of string. For
char* strings, the length is the distance between strings and the
first null byte. If there is no null byte in the memory (improbable,
but possible), strlen could loop forever, unless it's specifically
programmed to detect loop over. In anycase, this could be considered
as an infinite length string.
--
__Pascal Bourguignon__
Jeff Schwab
How could that code be written in standard C++? If it covers the whole
address space, it eventually must dereference null.
Pascal J. Bourguignon
Good point! :-)
Using pointers, it cannot be done in standard C, or standard C++, but
it can be done on most implementations.
--
__Pascal Bourguignon__
James Kanze
wrote:
> James Kanze <james.ka...@gmail.com> writes:
> > On Mar 4, 8:51 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
> >> joec...@gmail.com wrote:
> >> > template<std::size_t size>
> >> > void reverse(char (&input)[size])
> >> > Using the compiler to tell you the size certainly can't
> >> > be considered "a pass", or this is really getting to be a
> >> > silly question.
> >> The point was that you don't know the length ahead of time.
> >> He also didn't have a character array, only a char*.
> >> > Next we'll be asked to write a program telling us if a
> >> > passed string is of finite length.
> >> That's an easy one, unless you need the answer in finite time. :)
> > It's easier than that, it can be done in constant time:
> > bool
> > hasFiniteLength( char const* string )
> > {
> > return true ;
> > }
> > This will fail, of course, the day machines start having
> > infinite memory, but for the moment, we're safe.
> Once again, it depends on how you define the length of string.
Or rather, how you define a string. In the C standard, a string
is a '\0' terminated sequence of characters. If the pointer you
pass doesn't point to a '\0' terminated sequence of characters,
you haven't fulfilled a very essential pre-condtion: pass a
string to the function. Most (all?) of the functions in the C
standard which takes such strings have undefined behavior if you
violate the pre-condition.
> For char* strings, the length is the distance between strings
> and the first null byte. If there is no null byte in the
> memory (improbable, but possible),
Then you haven't passed a string, and the behavior is undefined.
Returning true is a valid undefined behavior (as is crashing).
> strlen could loop forever, unless it's specifically programmed
> to detect loop over. In anycase, this could be considered as
> an infinite length string.
Not according to the C standard.
(And of course, there should be a lot of smileys on this and on
my comment to which Pascal is replying. It seemed obvious
enough to me that I was being facetious in my original posting,
but maybe not.)
James Kanze
Could you cite something in the standard to support that:-).
(Seriously, I've used implementations where you could increment
a pointer forever without ever encountering a null pointer. And
the architecture in question, the Intel 80x86, is still used,
widely enough that I wouldn't consider it exotic, even if it is
strange and ugly.)
Jeff Schwab
> On Mar 5, 2:16 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
>> Pascal J. Bourguignon wrote:
>>> For char* strings, the length is the distance
>>> between strings and the first null byte. If there is no
>>> null byte in the memory (improbable, but possible), strlen
>>> could loop forever
>> How could that code be written in standard C++? If it covers
>> the whole address space, it eventually must dereference null.
> I've used implementations where you could increment
> a pointer forever without ever encountering a null pointer. And
> the architecture in question, the Intel 80x86, is still used
Are you saying that repeatedly incrementing the lower 16 bits of a
pointer value never gets you into the next segment? Doesn't the
operation "increment a pointer" include incrementing the segment register?
Pete Becker
No, in general there's no guarantee that segment selectors designate
contiguous memory. In real mode they tile the memory space, but nobody
does that any more. <g>
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
James Kanze
> James Kanze wrote:
> > On Mar 5, 2:16 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
> >> Pascal J. Bourguignon wrote:
> >>> For char* strings, the length is the distance
> >>> between strings and the first null byte. If there is no
> >>> null byte in the memory (improbable, but possible), strlen
> >>> could loop forever
> >> How could that code be written in standard C++? If it covers
> >> the whole address space, it eventually must dereference null.
> > I've used implementations where you could increment
> > a pointer forever without ever encountering a null pointer. And
> > the architecture in question, the Intel 80x86, is still used
> Are you saying that repeatedly incrementing the lower 16 bits
> of a pointer value never gets you into the next segment?
Or the lower 32 bits on an 80386, with 48 bit pointers.
> Doesn't the operation "increment a pointer" include
> incrementing the segment register?
No. Why should it. You're only allowed to increment within a
single object (array), or to one past the end. Depending on the
compilation model, the maximum object size was designed to fit
into a single segment. Note that this also affects comparisons
for inequality. The compiler only compares the offset, not the
segment.
Jerry Coffin
3801dc...@l39g2000yqn.googlegroups.com>, dbt...@gmail.com says...
> 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
> pass. Could you give me some clues?
Precisely as stated, it's impossible. Recursion only hides the auxillary
memory; it doesn't really eliminate it (in fact, it normally increases
it since it requires storage not only for the items in the string
itself, but also for the same number of return addresses -- in a typical
case of 8-bit characters and 32-bit addresses, this will quintuple the
auxillary memory requirements).
As to saying it's impossible, the reason is simple: to avoid using
auxillary memory, each character must be swapped directly from its
source to its destination -- but with a zero-terminated string, the
destination can only be determined by traversing to the end of the
string.
--
Later,
Jerry.
The universe is a figment of its own imagination.