Scrambling a String - Lab


The Problem

Scrambling a string is a useful procedure for many reasons, including entertainment (i.e., a newspaper puzzle) or for security (to send a secret message).

Below is an example of a string and its scrambled form:

Original stringScrambled version
dogatemyemaillogtaedeymaim

An easy way to achieve this scrambling, although not a very good one for security purposes, is to swap pairs of characters in the string until a reasonable scramble is reached. For example, we could have achieved the above scramble with the following steps:

  1. dogatemyemail (swap 'd' and 'm')
  2. mogatedyemail (swap 'a' and 't')
  3. mogtaedyemail (swap 'y' and 'e')
  4. mogtaedeymail (swap 'm' and 'l')
  5. logtaedeymaim (done!)


The Program

We'd like a program that allows the user to scramble a string in this fashion. Since a character may occur more than once in a string, swaps will instead be specified by 2 numeric positions.

A run of this program might look like:

% scramble
Enter a string to scramble (enter no spaces and no more
than 80 characters).

String? articulate

Now enter pairs of numbers representing positions to swap
to create the scrambled version (e.g., "1 3").  Positions are
numbered between 1 and 10 for this string.  Enter "0 0" when
you are done.

Swap? 1 2
New scrambled version: raticulate

Swap? 2 3
New scrambled version: rtaiculate

Swap? 0 8
Positions must be between 1 and 10!

Swap? 10 7
New scrambled version: rtaicueatl

Swap? 0 0

The string: articulate
was scrambled to: rtaicueatl

Note that, to the user, positions in the string start with 1.

The file scramble.cpp contains the core of such a string-scrambling program. Note the additional header needed (i.e., string.h) for string functions (like strlen()).

Representation

The String

The string that this program will read in and use for scrambling will be stored in a fixed-size array of characters, e.g.:

And thus, has been declared in the program as:

char str[MAX_STR_LENGTH+1];


Note that we must allow for one extra character, the nul character (\0). The nul character signals the end of the string, since the string may not use the entire space in the array. Besides, library functions or objects that deal with strings will either put it in (e.g., when reading a string from the user) or expect it to be there (e.g., in a string being printed).

Because the user of the program will view the first position in the string as 1 (i.e., one):

positions given by the user will have to be translated to zero-based indices (i.e., array indices start with 0).

A Scramble Map

We could just scramble the original string as swaps are made, however, we want to retain both the original and the scrambled version. We could this by copying the original string and scrambling that copy, but we will use another method.

This alternate method will use the original string and a map that tells us how the positions have been permuted. So, accessing the string via the map will allow us to view the string in scrambled form. Initially, the map will refer to the string in unscrambled form...

As positions are swapped (e.g., ), these swaps are made in the map rather than the string. As a result, the string remains the same, but when it is accessed via the map ( ), it will change as these swaps are made.

Since this map is an array containing pointers to elements in the string, map's elements must be of type pointer to character (char *). Thus, the map array is declared as:

char *map[MAX_STR_LENGTH];
You can read that as "an array with MAX_STR_LENGTH elements, where each element is a pointer to a character."


Your Task

Parts of the program need to be completed:

  1. void InitializeMap(char *map[MAX_STR_LENGTH],
                       char str[MAX_STR_LENGTH+1],
                       int length)
    

    This function sets up the map so that it refers to the string in its initial unscrambled form.

  2. void ScrambleMap(char *map[MAX_STR_LENGTH],
                     int length)
    

    This functions performs all the swaps that produce the scramble. Pairs of positions to swaps are prompted for and read in from the user until "0 0" is entered. Rather than changing the string, the map is changed.

  3. void PrintScrambled(char *map[MAX_STR_LENGTH],
                        int length)
    

    This function prints out the string using the scrambled order given by the map. Output should go to standard output.

  4. Error Checking - The program should do whatever basic error checking is necessary, such as making sure that swaps don't involve positions outside the string.
When you are done, compile the completed program, and run it a few times to test it.


Questions

In order to demonstrate an understanding of this problem and program, you should be able to answer the following questions:


BU CAS CS - Scrambling a String - Lab
Copyright © 1993-2000 by Robert I. Pitts <rip at bu dot edu>. All Rights Reserved.