Week 8 Laboratory
We have created some scripts that can automatically run your program against some tests. To run these tests you can execute the dry run program with an argument that corresponds to the lab and week, i.e. lab08 for this week. It expects to find all the programs to be submitted as part of this lab in the current directory. You can use dry run as follows:
prompt$ ~cs1921/bin/dryrun lab08
or specific tests (e.g. test #2) as follows:
prompt$ ~cs1921/bin/dryrun lab08 2
Exercises
Write a program called rotate.c that takes a string command-line argument, rotates the characters in the string by a single place, and prints the result. The direction of the rotation should be controlled by the optional switch -r for a right rotation, and -l for a left rotation. The usage syntax is the following:
./rotate [-r|-l] string
where string is the sequence of characters to be rotated.
if the switch is omitted, then a right rotation is assumed
if there is just one argument, it is assumed to be the string to be rotated
if there are no arguments at all on the command line, or too many, then a usage message is printed (see below)
Examples of its use are:
prompt$ ./rotate -r cows3
3cows
prompt$ ./rotate orangepurplepink
korangepurplepin
prompt$ ./rotate -r orangepurplepink
korangepurplepin
prompt$ ./rotate -l orangepurplepink
rangepurplepinko
prompt$ ./rotate -r 12
21
prompt$ ./rotate -l 12
21
prompt$ ./rotate A
A
prompt$ ./rotate -q abcdef
Usage: ./rotate [-r|-l] string
prompt$ ./rotate
Usage: ./rotate [-r|-l] string
If there is a command-line switch but no string (i.e. ./rotate -l or ./rotate -r then the switch is treated as a string). Note, do not use linked lists in this exercise. It is an exercise in command-line processing.
Modify the program from the previous exercise and place each character in the string in a node of a linked list and rotate the linked list by re-linking the nodes. Call the new program llrotate1.c. You should do the following in this exercise:
rotate left and right as in the previous exercise (use the same command-line interface)
you must build a linked list containing the characters of the string in the original order before you rotate the string
rotate the string by re-linking only
you may only change the link but not the data in a node
you should create functions that carry out left and right rotations
the output format differs slightly from the previous exercise:
'arrows' are placed between characters to emphasise the linked list structure (see examples below)
the string should be printed before and after rotation
you should free the nodes in the linked list before program termination
The same testcases apply, but the output will be different if the command-line arguments are correct:
prompt$ ./llrotate1 -r cows3
c->o->w->s->3
3->c->o->w->s
prompt$ ./llrotate1 orangepurplepink
o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k
k->o->r->a->n->g->e->p->u->r->p->l->e->p->i->n
prompt$ ./llrotate1 -r orangepurplepink
o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k
k->o->r->a->n->g->e->p->u->r->p->l->e->p->i->n
prompt$ ./llrotate1 -l orangepurplepink
o->r->a->n->g->e->p->u->r->p->l->e->p->i->n->k
r->a->n->g->e->p->u->r->p->l->e->p->i->n->k->o
prompt$ ./llrotate1 -r 12
1->2
2->1
prompt$ ./llrotate1 -l 12
1->2
2->1
prompt$ ./llrotate1 A
A
A
Executions resulting in a usage message are the same as in the previous exercise (with the name of the executable different of course).
Modify the program in the previous exercise to use a data-copy strategy: rotate the string by copying data from node to node: the addresses of the nodes should not change. Call the new program llrotate2.c. You should pay attention to:
you should only copy data between list nodes (do not do any re-linking of the list nodes)
a function that carries out a rotation should be of type void as it must not change the location of the head
do not make any new lists or nodes!
This program should run identically to the program in the previous exercise, so all the above testcases apply.
There are 2 parts to this exercise. In the first part you will generate random strings of letters: in the second part you will insert these letters into a linked list and remove duplicates. The programs from both parts should be submitted.
Write a program called randword.c that generates a random word (consisting of just lower-case letters). When executed, the first command-line argument is the length of the word, and the second argument is the seed used by the random number generator (i.e. by random()). If there are not exactly 2 numerical command-line arguments then a usage message is output. Consider the following testcases:
Testcase 1: the execution
prompt$ ./randword 10 1
nwlrbbmqbh
seeds the random-number generator with 1 and generates a random word of length 10.
Testcase 2: a different seed results in another word
prompt$ ./randword 10 4334
hzykhhffgg
Testcase 3: similarly
prompt$ ./randword 10 4747
ephhbtttto
Testcase 4: also
prompt$ ./randword 10 8708
oosyfyekpp
Testcase 5: here is a testcase for a longer word:
prompt$ ./randword 50 73861
vvvvvhpliidmeowljxvmpahskmbhptskophmwxzghdsmroxcos
Testcase 6: if there are no arguments then we get
prompt$ ./randword
Usage: ./randword wordlength randomseed
Testcase 7: a non-numerical argument results in
prompt$ ./randword a 123
Usage: ./randword wordlength randomseed
Testcase 8: too many arguments results in
prompt$ ./randword 10 123 1
Usage: ./randword wordlength randomseed
Note it is important in the exercises above that you call the random number generator as specified in lectures, otherwise the outputs will not match. If you use a different method to generate random numbers, the testcases 1 to 5 will 'fail', but your program could still be perfectly correct.
Modify the random-word program above, calling the new program llrandword.c, to use a linked list to store the random word, one letter in each node in the list. As well, we want the linked list to be cleaned, which means we want to remove all duplicate letters in the linked list, where a letter that appears in 2 consecutive nodes is a duplicate letter. Note:
you must first insert all the letters in a linked list before you remove duplicate letters
The output of the program should be the original linked list, followed by the cleaned linked list. The same testcases as above may be used here, but the output will look different if the command-line arguments are correct:
Testcase 1
prompt$ ./llrandword 10 1
n->w->l->r->b->b->m->q->b->h
n->w->l->r->b->m->q->b->h
Notice the duplicate letter b has been removed.
Testcase 2
prompt$ ./llrandword 10 4334
h->z->y->k->h->h->f->f->g->g
h->z->y->k->h->f->g
Testcase 3
prompt$ ./llrandword 10 4747
e->p->h->h->b->t->t->t->t->o
e->p->h->b->t->o
Testcase 4
prompt$ ./llrandword 10 8708
o->o->s->y->f->y->e->k->p->p
o->s->y->f->y->e->k->p
Testcase 5
prompt$ ./llrandword 50 73861
v->v->v->v->v->h->p->l->i->i->d->m->e->o->w->l->j->x->v->m->p->a->h->s->k->m->b->h->p->t->s->k->o->p->h->m->w->x->z->g->h->d->s->m->r->o->x->c->o->s
v->h->p->l->i->d->m->e->o->w->l->j->x->v->m->p->a->h->s->k->m->b->h->p->t->s->k->o->p->h->m->w->x->z->g->h->d->s->m->r->o->x->c->o->s
Testcase 6, 7 and 8 above are the same as above (with the name of the executable different of course).
Submit your work using:
give cs1921 lab08 add3rotate.c llrotate1.c llrotate2.c randword.c llrandword.c