POTW 20091022

From CSLabsWiki

Problem Statement

It is your first day of work at Acme Corp, the world-renowned widget company. You have been hired as a software developer in their widgetOS department. Your first task is to implement a function to reverse a C-string in place, however, widgetOS is known for being about as frugal with memory as a good Vermonter is with maple syrup. Below is the skeleton of your function:

void reverse(char * string);

The input string will be a C-string (meaning it is an array characters ending with a '\0' character) and will contain only alphabetic, numeric, and whitespace characters ([a-z][A-Z][0-9]\s\t\r\n).

You must use as little memory as possible (run-time is your secondary concern) and keep in mind of memory usage of any other functions that you call.

Submission and Grading

There will be two winners: the first person to submit a correct answer, and the "best" answer as determined by the problem poser.

You should submit the function, a main function showing it working, a makefile or the compiler arguments to compile your code, and a short write-up describing the memory usage of your function. You should use C or C++. Please submit your solution by emailing it to the problem poser.

Requests for Clarification

Please make all requests for clarification here in the form of:

Q: Question

Submissions

Sam Payson

• Submitted: 10/23/09 0316
• Works: Yes
• Compile with: gcc -Wall problem.c -o reverse
• Writeup: This program uses 4 bytes of memory (on a system with 32-bit pointers) in

addition to the memory used by the string itself.

• Code:

#include <stdio.h>

void reverse(char * string)
{
	char * p = string;
	while (*p != 0x0)
		++p;
	--p;
	while (p != string && p > string)
	{
		*string ^= *p;
		*p ^= *string;
		*string ^= *p;
		--p;
		++string;
	}
}

int main(int argc, char * argv[])
{
	if (argc != 2)
	{
		printf("usage: reverse [string]\n");
		return 1;
	}
	reverse(argv[1]);
	printf("%s\n", argv[1]);
	return 0;
}

Tim Kopp

• Submitted: 10/29/09 1237
• Works: Yes
• Compile with: g++ -o potw potw20091028.cpp
• Writeup:

My algorithm uses memory for:

2 character pointers
2 integers
1 character

My gut tells me there's a way to use less, but I couldn't think of one.

• Code:

/*
 * Filename: potw20091022.cpp
 * Author: Tim Kopp
 * Description: Reverse a c-string, memory use trumps runtime.
 * Last Modified: 10/29/2009
 */

#include <iostream>
#include <cstring>
using namespace std;

void reverse(char * string);

int main()
{
  const char* tmp = "Hello COSI!";
  char* string = new char[11];
  strcpy(string,tmp);


  cout << "String: " << string << endl;
  reverse(string);
  cout << "Reversed: " << string << endl;
  return 0;
}

void reverse(char * string)
{
  char * pf;
  pf = string;
  char * pb;
  pb = string;
  char tmp;
  int count=-1;

  while(*pf != '\0')
    {
      pf++;
      count++;
    }
  pf--;

  for(int i=0; i < count/2+1; ++i)
    {
      tmp = *pb;
      *pb=*pf;
      *pf=tmp;
      pf--;
      pb++;
    }
  return;
}