Solution To Friday Puzzle #1

4 09 2011

Not too many attempts to answer the puzzle were posted, but I hope you have pondered it anyway. Nevertheless, here’s my solution (hosted in Notepad.cc). What I consider particularly elegant in the solution of the Hard Part is the unusual opportunity to reuse the entire solution of the Easy Part:

ReverseString( pString + n );

ReverseString( pString );

ReverseString( pString + strlen(pString) – n );

For example, rotating the string “Hello, World!” by 3 steps generates the following intermediate strings:

  • “Hello, World!” >> reverse 3..n
  • “Hel!dlroW ,ol” >> reverse 0..n
  • “lo, World!leH” >> reverse n-3..n
  • “lo, World!Hel”

Isn’t that neat!

Advertisements

Actions

Information

One response

7 09 2011
yrpe

Elegant and O(n) to boot!
The more direct solution to the problem which avoids extra moves would be Rot(n, i):
0 -> i1, i -> i2, a[0] -> temp
while(i2) { a[i2] -> a[i1]; i2 -> i1; i2 + i -> i2; i2 mod n -> i2; }
temp -> a[i1];

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