Friday Puzzle #1

1 09 2011

Here’s a programming challenge for the weekend.

The Easy Part

Write a function in C++ that reverses a regular zero-terminated string without using extra array. For example, …

char *pString = “Hello”;

ReverseString( pString );

After executing ReverseString, the contents of pString should be “olleH”.

The Hard Part:

Write a function in C++ that takes a regular zero-terminated string and an integer, and rotates the string as much to left as the integer specifies.  To rotate a string means to move the given number of characters from front to back, and shifting all other characters to the left accordingly.  Again, no extra array must be used.  For example, after executing …

char *pString = “Hello”;

RotateString( pString,2 );

… the pBuffer should contain “lloHe”.  In other words, the first two characters “He” have been moved to the end while the remaining characters “llo” have been shifted towards the front.

The hard part is indeed quite hard but there is actually an extremely elegant solution which may arise to you if you warm up with the easy part.  If you wish to participate, post your solution as a comment to this article.  I will edit the body of this article closer to the end of the weekend (perhaps some time Sunday evening Finnish time) to give my solution, or as soon as I see someone post an even more elegant solution.

Advertisements

Actions

Information

3 responses

2 09 2011
maah

On a side note: In APL language this is solved by rotate array operator |. So the first one |pString and the second one 2|pString (if I remember it correctly – it has been a while since I wrote in that language). ;-)

2 09 2011
rlankine

Does |pString indeed reverse the string (“olleH”) or just rotate by one (“elloH”)?

5 09 2011
maah

It rotates the whole string if there is no left argument. Ops, did not remember correctly the original rotate/mirror character, it should be looking like a Phi (o with | on top of it). See: http://www.pyr.fi/apl/texts/APLopas.PDF p. 10.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: