Week 08 Laboratory Sample Solutions

• working with strings
• arrays and structs

The following is a list of all the activities available to complete this week...

Worth 0.7 mark(s) in total:

• string_match

Worth 0.7 mark(s) in total:

• string_reverse
• swap_case
• substitution

Worth 0.4 mark(s) in total:

• punctuated_palindrome
• frequency_analysis

Problem sets are capped at 15 marks (there are 4 possible bonus marks from the three-dot exercises that can bring you up to a total of 15 if you missed out on any other marks in the one- or two-dot exercises).

Completing just the one and two-dot exercises every week can give you the full 15 marks needed in this component.

For more details, see the course outline.

Your job is to write a program called string_match.c which lets us count the number of times we see our "search term" in a list of strings.

TASK 1 Scan in the "search term"

TASK 2: Scan in strings from standard input until Ctrl-D is pressed.

TASK 3: Count the number of times the "search term" appear in the input.

Examples

dcc string_match.c -o string_match
./string_match
Enter the search term: same
Enter the list of strings:
same
sand
same
send
shade
same
shadow

There was 3 occurrence(s) of the search term in the input.
./string_match
Enter the search term: An ostrich's eye is bigger than its brain.
Enter the list of strings:
That is a cool fact.
I never knew that!
An ostrich's eye is bigger than its brain.
ostrich?
Why the random facts?

There was 1 occurrence(s) of the search term in the input.
./string_match
Enter the search term: 42 is the meaning of life, the universe, and everything
Enter the list of strings:
The ascii for * is 42
42 is the meaning of life, the universe, and everything!!!
42 = everything

There was 0 occurrence(s) of the search term in the input.

Assumptions/Restrictions/Clarifications

• You can assume that each string will be no longer than 128 characters long
• You may find the strcmp() function useful

1091 style string_match.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest string_match

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_string_match string_match.c
    

You must run give before Monday 17 March 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// string_match.c
// Searches for words in standard input until ctrl + d is pressed 
// that match any of the given search term
// Written by Sofia De Bellis, z5418801, on July 2023

#include <stdio.h>
#include <string.h>

#define MAX_WORD_LEN 128

int main(void) {
    printf("Enter the search term: ");
    char search_term[MAX_WORD_LEN];

    fgets(search_term, MAX_WORD_LEN, stdin);

    printf("Enter the list of strings:\n");

    int total = 0;

    char buf[MAX_WORD_LEN];
    while (fgets(buf, MAX_WORD_LEN, stdin) != NULL) {
        if (strcmp(buf, search_term) == 0) {
            total++;
        }
    }
    printf("There was %d occurrence(s) of the search term in the input.\n",
    total);

    return 0;
}

Download string_reverse.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/string_reverse/string_reverse.c .

Your task is to add code to this function in string_reverse.c:

// Takes a string in `buffer`, and reverses it in-place.
void string_reverse(char *buffer) {
    // YOUR CODE GOES HERE!
}

int main(int argc, char *argv[]) {

    // NOTE: THIS WON'T WORK:
    // char *str = "Hello!"
    // string_reverse(str)
    //
    // str only points to a string literal, which it is not legal to change.
    // If you attempt to modify it on Linux you will get a runtime error.
    // Instead, you need to create an array to store the string in, e.g.:
    //
    // char str[] = "Hello!"
    // string_reverse(str)

    char str[] = ".'neetneves' :egassem terces A";
    string_reverse(str);
    printf("%s\n", str);
    return 0;
}

Your string_reverse function will be called directly in marking. The main function is only to let you test your string_reverse function

Here is how string_reverse.c should behave after you add the correct code to the function string_reverse:

dcc string_reverse.c -o string_reverse
./string_reverse
A secret message: 'seventeen'.

1091 style string_reverse.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest string_reverse

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_string_reverse string_reverse.c
    

You must run give before Monday 17 March 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// gnirts a esreveR (Reverse a string)
// A sample solution.

#include <stdio.h>

void string_reverse(char *buffer);
int string_length(char *string);

int main(int argc, char *argv[]) {

    // NOTE: THIS WON'T WORK:
    // char *str = "Hello!"
    // string_reverse(str)
    //
    // str only points to a string literal, which it is not legal to change.
    // If you attempt to modify it on Linux you will get a runtime error.
    // Instead, you need to create an array to store the string in, e.g.:
    //
    // char str[] = "Hello!"
    // string_reverse(str)

    char str[] = ".'neetneves' :egassem terces A";
    string_reverse(str);
    printf("%s\n", str);
    return 0;
}

// Takes a string in `buffer`, and reverses it in-place.
void string_reverse(char *buffer) {
    int length = string_length(buffer);
    int i = 0;
    while (i < length/2) {

        // swap array elements
        char tmp = buffer[i];
        buffer[i] = buffer[length - i - 1];
        buffer[length - i - 1] = tmp;

        i = i + 1;
    }
}

// Takes a string and finds its length, excluding the null-terminator.
int string_length(char *string) {
    int i = 0;
    while (string[i] != '\0') {
        i = i + 1;
    }
    return i;
}

Download swap_case.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity swap_case

Your task is to add code to this function in swap_case.c:

int swap_case(int character) {
    // TODO: Write this function, which should:
    //  - return character in lower case if it is an upper case letter
    //  - return character in upper case if it is an lower case letter
    //  - return the character unchanged otherwise

    return 'x';
}

Edit the C program swap_case.c (linked above) which reads characters from its input and writes the same characters to its output with lower case letters converted to upper case and upper case letters converted to lower case.

Your program should stop only at the end of input.

which:

• returns the character in lowercase if it is an uppercase letter
• returns the character in uppercase if it is a lowercase letter
• returns the character unchanged otherwise

Note: Your program will not pass autotests if it does not contain this function.

Examples

dcc swap_case.c -o swap_case
./swap_case
Are you saying 'Boo' or 'Boo-Urns'?
aRE YOU SAYING 'bOO' OR 'bOO-uRNS'?
In this house, we obey the laws of thermodynamics!
iN THIS HOUSE, WE OBEY THE LAWS OF THERMODYNAMICS!
UPPER !@#$% lower
upper !@#$% LOWER

Assumptions/Restrictions/Clarifications

• You need only a single int variable. Don't use an array.
• Make sure you understand this example program which reads characters until end of input.
• Make sure you understand this example program which reads characters, printing them with lower case letters converted to uppercase.

1091 style swap_case.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest swap_case

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_swap_case swap_case.c
    

You must run give before Week 9 Monday 9:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

//  Written 3/3/2018 by Andrew Taylor (andrewt@unsw.edu.au)
//  Write stdin to stdout with upper case letters converted to lower case
// and lower case converted to upper case
//

#include <stdio.h>
#include <stdlib.h>

int swap_case(int character);

int main(int argc, char *argv[]) {
    int character = getchar();
    while (character != EOF) {
        int swapped_character = swap_case(character);
        putchar(swapped_character);
        character = getchar();
    }

    return 0;
}


int swap_case(int character) {
    if (character >= 'A' && character <= 'Z') {
        return 'a' + character - 'A';
    } else if (character >= 'a' && character <= 'z') {
        return 'A' + character - 'a';
    } else {
        return character;
    }
}

Write a C program substitution.c which reads characters from its input and writes the characters to its output encrypted with a Substitution cipher.

A Substitution cipher maps each letter to another letter.

The mapping will be given to your program via the command line as a command line argument (no spaces between any characters). This is all on one line. This input will contain 26 characters: an ordering of the letters 'a'..'z'.

Characters other than letters should not be encrypted.

Your program should stop only at the end of input.

Your program should contain at least one function other than main.

Examples

dcc substitution.c -o substitution
./substitution qwertyuiopasdfghjklzxcvbnm
Enter text:
I was scared of dentists and the dark
O vql leqktr gy rtfzolzl qfr zit rqka
I was scared of pretty girls and starting conversations
O vql leqktr gy hktzzn uoksl qfr lzqkzofu egfctklqzogfl

./substitution abcdefghijklmnopqrstuvwxyz
Enter text:
The identity cipher!!!
The identity cipher!!!

./substitution bcdefghijklmnopqrstuvwxyza
Enter text:
The Caesar cipher is a subset of the substitution cipher!
Uif Dbftbs djqifs jt b tvctfu pg uif tvctujuvujpo djqifs!

Your program will only be tested with an appropriate and valid mapping input for marking - but a good programmer would check the input is present and appropriate.

1091 style substitution.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest substitution

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_substitution substitution.c
    

You must run give before Monday 17 March 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// Substitution.c
//  Write stdin to stdout encrypted with a Substitution cipher
//  https://en.wikipedia.org/wiki/Substitution_cipher
//
//  The mapping will be supplied as a command-line argument containing 26 characters:
//  These will be an an ordering of the letters 'a'..'z'.
//
// Written 3/3/2018 by Andrew Taylor (andrewt@unsw.edu.au)
// and adapted for 23T2 by Sofia De Bellis, z5418801 on July 2023

#include <stdio.h>
#include <string.h>

#define ALPHABET_SIZE  26

int encrypt(char character, char mapping[ALPHABET_SIZE]);

int main(int argc, char *argv[]) {
    char mapping[ALPHABET_SIZE + 1];
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        mapping[i] = argv[1][i];
    }

    mapping[ALPHABET_SIZE] = '\0';
    

    // Error checking - not necessary in student solution or tested
    if (mapping[0] == '\0') {
        printf("Usage: ./substitution <mapping>\n");
        return 1;
    }

    if (strlen(mapping) != ALPHABET_SIZE) {
        printf("./substitution: mapping must contain %d letters\n", ALPHABET_SIZE);
        return 1;
    }

    printf("Enter text:\n");

    char character;
    while (scanf("%c", &character) == 1) {
        int encrypted_character = encrypt(character, mapping);
        printf("%c", encrypted_character);
    }

    return 0;
}

// encrypt letters with a substitution cipher with the specified mapping
int encrypt(char character, char mapping[ALPHABET_SIZE]) {
    if (character >= 'A' && character <= 'Z') {
        return mapping[character - 'A'] - 'a' + 'A';
    } else if (character >= 'a' && character <= 'z') {
        return mapping[character - 'a'];
    } else {
        return character;
    }
}

Characters which are not letters should be ignored .

Differences between upper case and lower case are ignored. For example:

./punctuated_palindrome
Enter a string: Do geese see God?
String is a palindrome
./punctuated_palindrome
Enter a string: Do ducks see God?
String is not a palindrome
./punctuated_palindrome
Enter a string: Madam, I'm Adam
String is a palindrome
./punctuated_palindrome
Enter a string: Madam, I'm Andrew
String is not a palindrome

You can assume lines contain at most 4096 characters.

1091 style punctuated_palindrome.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest punctuated_palindrome

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_punctuated_palindrome punctuated_palindrome.c
    

You must run give before Monday 17 March 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// Read a string and then print the letters one per line
// written by Andrew Taylor andrewt@cse.unsw.edu.au
// April 2018 as a COMP1511 lab exercise
//

#include <stdio.h>
#include <ctype.h>

#define MAXLINE 5000

int is_palindrome(char line[]);

int main(void) {
    char line[MAXLINE] = {0};
    printf("Enter a string: ");
    fgets(line, MAXLINE, stdin);

    if (is_palindrome(line)) {
        printf("String is a palindrome\n");
    } else{
        printf("String is not a palindrome\n");
    }

    return 0;
}

// return 1 is line is palindromic, 0 otherwise
// line is terminated by either '\n' or '\0'
// case and non-alphabetic characters are ignored
// an empty line is considered a palindrome
int is_palindrome(char line[]) {
    int right = 0;
    while (line[right] != '\0' && line[right] != '\n') {

        right = right + 1;
    }

    right = right - 1;

    int left = 0;
    while (left < right) {
        int left_char = tolower(line[left]);
        int right_char = tolower(line[right]);
        if (!isalpha(left_char)) {
            left = left + 1;
        } else if (!isalpha(right_char)) {
            right = right - 1;
        } else if (left_char != right_char) {
            return 0;
        } else {
            left = left + 1;
            right = right - 1;
        }
    }

    return 1;
}

Write a C program frequency_analysis.c which reads characters from its input until end of input.

It should then print the occurrence frequency for each of the 26 letters 'a'..'z'.

The frequency should be printed as a decimal value and an absolute number in exactly the format below.

Note upper and lower case letters are counted together.

Examples

dcc frequency_analysis.c -o frequency_analysis
./frequency_analysis
Hello and goodbye.

'a' 0.066667 1
'b' 0.066667 1
'c' 0.000000 0
'd' 0.133333 2
'e' 0.133333 2
'f' 0.000000 0
'g' 0.066667 1
'h' 0.066667 1
'i' 0.000000 0
'j' 0.000000 0
'k' 0.000000 0
'l' 0.133333 2
'm' 0.000000 0
'n' 0.066667 1
'o' 0.200000 3
'p' 0.000000 0
'q' 0.000000 0
'r' 0.000000 0
's' 0.000000 0
't' 0.000000 0
'u' 0.000000 0
'v' 0.000000 0
'w' 0.000000 0
'x' 0.000000 0
'y' 0.066667 1
'z' 0.000000 0
./frequency_analysis
Hey! Hey! Hey!
I don't like walking around this old and empty house
So hold my hand, I'll walk with you my dear

'a' 0.072289 6
'b' 0.000000 0
'c' 0.000000 0
'd' 0.084337 7
'e' 0.084337 7
'f' 0.000000 0
'g' 0.012048 1
'h' 0.096386 8
'i' 0.072289 6
'j' 0.000000 0
'k' 0.036145 3
'l' 0.084337 7
'm' 0.036145 3
'n' 0.060241 5
'o' 0.084337 7
'p' 0.012048 1
'q' 0.000000 0
'r' 0.024096 2
's' 0.036145 3
't' 0.048193 4
'u' 0.036145 3
'v' 0.000000 0
'w' 0.036145 3
'x' 0.000000 0
'y' 0.084337 7
'z' 0.000000 0

Hint: use an array to store counts of each letter.

Hint: make sure you understand this example program which counts integers from the range 0..99.

Manually Cracking a Substitution Cipher

This English text was encrypted with a substitution cipher.

Di jd, vdl'ht xtqa dh O qn
Vdl rdlwk O'ss wdkith htqromu omkd ok
O fhdwqwsv xdm'k
Styk kd nv dxm rtzoetj
Wlk kiqk'j kit royythtmet om dlh dfomodmj

Vdl'ht q ndlkiyls
Kiqk qndlmkj ydh qmdkith xtta dm nv dxm
Mdx O'n q mdzts nqrt htjdlhetyls
O jkqhk q eiqom xoki nv kidluik

Kqsa oj eitqf, nv rqhsomu
Xitm vdl'ht yttsomu houik qk idnt
O xqmmq nqat vdl ndzt xoki edmyortmet
O xqmmq wt xoki vdl qsdmt

What was the original text?

Oh so, you're weak or I am
You doubt I'll bother reading into it
I probably won't
Left to my own devices
But that's the difference in our opinions

You're a mouthful
That amounts for another week on my own
Now I'm a novel made resourceful
I start a chain with my thought

Talk is cheap, my darling
When you're feeling right at home
I wanna make you move with confidence
I wanna be with you alone

1091 style frequency_analysis.c
    

When you think your program is working, you can use autotest to run some simple automated tests:

1091 autotest frequency_analysis

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab08_frequency_analysis frequency_analysis.c
    

You must run give before Monday 17 March 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

//  Written 3/3/2018 by Andrew Taylor (andrewt@unsw.edu.au)
//  Read characters from stdin until of input then print the frequency of letters

#include <stdio.h>

#define NOT_A_LETTER   (-1)
#define ALPHABET_SIZE  26

int get_letter_frequencies(int letter_count[ALPHABET_SIZE]);
int letter_index(int character);
void print_frequencies(int letter_count[ALPHABET_SIZE], int n_letters_read);

int main(int argc, char *argv[]) {
    int letter_count[ALPHABET_SIZE] = {0};  // 1 array element for each English letter

    int n_letters_read = get_letter_frequencies(letter_count);
    print_frequencies(letter_count, n_letters_read);
    return 0;
}

// read  characters from stdin, and for uppercase and lower case letters updating
// accumulating count a letter_count in letter_frequencies
// number of uppercase and lower case letters read is returned

int get_letter_frequencies(int letter_count[ALPHABET_SIZE]) {
    char character;
    int n_letters_read = 0;
    while (scanf(" %c", &character) == 1) {
        int index =  letter_index(character);
        if (index != NOT_A_LETTER) {
            letter_count[index] = letter_count[index] + 1;
            n_letters_read = n_letters_read + 1;
        }
    }
    return n_letters_read;
}

// return position of letter in English  alphabet (0..25)
// for lower case and upper case letter
// return NOT_A_LETTER for other characters

int letter_index(int character) {
    if (character >= 'A' && character <= 'Z') {
        return character - 'A';
    } else if (character >= 'a' && character <= 'z') {
        return character - 'a';
    } else {
        return NOT_A_LETTER;
    }
}

void print_frequencies(int letter_count[ALPHABET_SIZE], int n_letters_read) {
    if (n_letters_read == 0) {
        return;
    }
    int i = 0;
    while (i < ALPHABET_SIZE) {
        printf("'%c' %lf %d\n", 'a'+i, letter_count[i]/(double)n_letters_read,  letter_count[i]);
        i = i + 1;
    }
}

You only need to do this if the exercise specifies a give command, otherwise - the exercise is not worth marks.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 9 Monday 9:00am to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1091 classrun -sturec