[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. A feeble encyption system

For this assignment, you are to implement a simple text scrambler. The input is a sequence of upper-case characters 'A' through 'Z', supplied on stdin terminated by a newline. The scrambler works by applying a repeatedly applying a simple scrambling step.

2. The basic scrambling step

Imagine that the input sequence is written on cards, one character per card, with the first character at the front of the deck. A scrambling step consists of (a) removing the front card from the deck; (b) moving the k following cards from the front to the back of the deck, one at a time, where k is 1 if the top card was A, 2 for B, 3 for C, etc. up to 26 for Z; (c) replacing the original front card removed in step (a) on the back of the deck.

For example, if the input is ABCDEFG, one scrambling step removes A, moves B (one card) the the end, and re-appends A, giving CDEFGBA. Applying the scrambling step a second time removes C, moves DEF (three cards) to the end, and re-appends C, giving GBADEFC.

If the number of cards to move is more than the number of cards in the deck, some may be moved more than once. An extreme example is that scrambling ZA moves A from the front to the back of a very short deck 26 times, leaving AZ after Z is re-appended at the end. For a more realistic example, scrambling ZOOLOGIST once gives LOGISTOOZ.

Strings of length 0 or 1 are not affected by the scrambling operation.

3. Your task

You are to write a program scramble that implements both scrambling and its inverse "unscrambling" operation (which you will need to figure out how to do). Your scramble program should take as input a line consisting solely of capital letters terminated by a newline, and apply the basic scrambling step a number of times specified by argv[1]. The result of doing this scrambling should be written to stdout, again terminated by a newline. For example:

$ echo ZOOLOGIST | ./scramble 10000
LZTIOOSOG
$

With a negative argument -N, scramble should perform the inverse operation N times. So the pipe "scramble 999 | scramble -999" should copy its input to its output intact. Calling scramble with an argument of zero should likewise pass the input to the output unmodified.

4. Details

Your program is not required to deal with non-standard inputs. You may assume that the only inputs it receives consist of a single line of only capital letters. However, you should design it to deal with arbitrarily long lines.

5. Submitting your program

Submit your program as usual using the /c/cs223/bin/submit script. You may either submit a single file scramble.c or multiple files together with a Makefile that generates scramble when called with make scramble.

6. Sample solution

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <assert.h>
   5 
   6 /* read a line of text from stdin
   7  * and return it (without terminating newline) as a freshly-malloc'd block.
   8  * Caller is responsible for freeing this block.
   9  * Returns 0 on error or EOF.
  10  * (copied from hw2 sample solutions) */
  11 char *
  12 getline(void)
  13 {
  14     char *line;		/* line buffer */
  15     int n;		/* characters read */
  16     int size; 		/* size of line buffer */
  17     int c;
  18 
  19     size = 1;
  20     line = malloc(size);
  21     if(line == 0) return 0;
  22     
  23     n = 0;
  24 
  25     while((c = getchar()) != '\n' && c != EOF) {
  26 	while(n >= size - 1) {
  27 	    size *= 2;
  28 	    line = realloc(line, size);
  29 	    if(line == 0) return 0;
  30 	}
  31 	line[n++] = c;
  32     }
  33 
  34     if(c == EOF && n == 0) {
  35 	/* got nothing */
  36 	free(line);
  37 	return 0;
  38     } else {
  39 	line[n++] = '\0';
  40 	return line;
  41     }
  42 }
  43 
  44 /* reverse a malloc'd null-terminated string */
  45 /* returns a new malloc'd string and frees its argument */
  46 char *
  47 rev(char *s)
  48 {
  49     char *s2;
  50 
  51     int i;
  52     int len;
  53    
  54     len = strlen(s);
  55 
  56     s2 = malloc(len+1);
  57     assert(s2 != 0);
  58 
  59     for(i = 0; i < len; i++) {
  60 	s2[i] = s[len-i-1];
  61     }
  62 
  63     s2[len] = '\0';
  64 
  65     free(s);
  66 
  67     return s2;
  68 }
  69 
  70     
  71 
  72 /* various constants for scramble */
  73 #define BASE_CHARACTER ('A')
  74 #define MAX_CHARACTER  ('Z')
  75 #define SPARE_ROOM     (MAX_CHARACTER - BASE_CHARACTER + 2)
  76 
  77 /* this must be at least twice len + SPARE_ROOM */
  78 /* to avoid overlaps in memcpy */
  79 #define BufSize(len)   (2*(len)+1024)
  80 
  81 /* scrambler */
  82 /* first argument is a malloc'd null-terminated string */
  83 /*  This string will be freed by this routine. */
  84 /* second argument is number of times to apply the scrambling operation */
  85 /* return value is a new malloc'd null-terminated string */
  86 char *
  87 scramble(char *input, int n)
  88 {
  89     /* basic idea: we'll allocate a buffer somewhat bigger
  90      * than the input, roll the scrambled string along the
  91      * buffer, and move it back to the start if it gets too
  92      * close to the end */
  93     int len;		/* length of input */
  94     int buflen;		/* length of buffer */
  95     char *buf;		/* buffer */
  96 
  97     char *top;		/* first character in string */
  98     char *bottom;	/* first position after string */
  99 
 100     char card;		/* top of deck character */
 101     int count;		/* how many characters to move */
 102 
 103     int i;		/* how many times we've scrambled */
 104 
 105     assert(input != 0);
 106 
 107     /* set up buffer and pointers */
 108     len = strlen(input);
 109 
 110     /* special case: 1 or 0 characters have no effect */
 111     if(len <= 1) return input;
 112 
 113     /* otherwise build the buffer */
 114     buflen = BufSize(len);
 115     buf = realloc(input, buflen);
 116     assert(buf != 0);
 117 
 118     top = buf;
 119     bottom = top + len;
 120     
 121     for(i = 0; i < n; i++) {
 122 	/* make sure there is enough room */
 123 	if((buf + buflen) - bottom < SPARE_ROOM) {
 124 	    /* shift back to start */
 125 	    memcpy(buf, top, len);
 126 	    top = buf;
 127 	    bottom = top + len;
 128 	}
 129 
 130 	/* grab top card and compute count */
 131 	card = *top++;
 132 
 133 	/* take remainder to avoid recopying short strings */
 134 	assert(BASE_CHARACTER <= card);
 135 	assert(card <= MAX_CHARACTER);
 136 	count = (card - BASE_CHARACTER + 1) % (len - 1);
 137 
 138 	/* using memcpy here is slightly faster than doing it by hand */
 139 	memcpy(bottom, top, count);
 140 	top += count;
 141 	bottom += count;
 142 
 143 	/* restore former top card */
 144 	*bottom++ = card;
 145 
 146 	assert(bottom - top == len);
 147     }
 148 
 149     /* copy to base of buffer again */
 150     /* note we use memmove because we aren't sure of no overlap */
 151     memmove(buf, top, len);
 152 
 153     /* tack on the missing null terminator */
 154     buf[len] = '\0';
 155 
 156     /* shrink and return */
 157     return realloc(buf, len+1);
 158 }
 159 
 160 int
 161 main(int argc, char **argv)
 162 {
 163     char *s;
 164     int n;
 165 
 166     if(argc != 2) {
 167 	fprintf(stderr, "Usage: %s scramble-count\n", argv[0]);
 168 	exit(1);
 169     }
 170 
 171     n = atoi(argv[1]);
 172 
 173     s = getline();
 174 
 175     if(n < 0) {
 176 	s = rev(scramble(rev(s), -n));
 177     } else {
 178 	s = scramble(s, n);
 179     }
 180 
 181     puts(s);
 182 
 183     free(s);
 184 
 185     return 0;
 186 }
scramble.c

2014-06-17 11:58