COMP1511-Style Exercises

Back to Index

Here are a few indroductory C exercises for people coming into first year, to get an idea of what work in COMP1511 is like.

These are not endorsed by UNSW, and were made at the end of 2018, so may be slightly outdated. If you see any mistakes or have any suggestions for an improvement, please let me know :).

Autotests

Autotests are available, which should work on any UNIX-based system. Simply extract this ZIP into the folder where you're working, and mark the autotest script as executable:

$ chmod u+x autotest.sh

These will test your program against a number of sample inputs and outputs.

Warmup

Let's do a small printing exercise to get familiar with compiling and running C code.

Hello, World!

Write a program called hello.c which — when run — prints 'Hello, World!'.

$ ./hello
Hello, World!

The methods for compiling and running the code will be slightly different. If you're already setup to use the CSE computers, you can compile this with dcc. Otherwise, you can use gcc with a few arguments to make catching errors slightly easier, although dcc is recommended as soon as you can use it.

$ dcc -o hello hello.c
$ ./hello
Hello, World!

# On your own computer
$ gcc -Wall -Werror -fsanitize=address,leak -o hello hello.c
$ ./hello
Hello, World!

More Useful Programs

Now we'll get to write some more useful programs. Make sure you've taken a look at scanf, if statements, while loops and functions before attempting these.

Metres to Feet

Write a program that accepts a range of lengths, in metres, and then converts that range to feet (to 1 decimal place). Each step along the range should be 0.1 metres, note that the input may not be a whole number. Your program should work like so:

$ ./feetres
Range start: 1.5
Range end: 2

Metres  Feet
1.5     4.9
1.6     5.2
1.7     5.6
1.8     5.9
1.9     6.2
2.0     6.6

Your program may not show the last line — this is fine, although you may want to look into why that is. You can assume that all inputs are valid.

Autotests are available for this exercise by running ./autotest.sh feetres.

Optional Challenge: Instead of displaying feet to 1 decimal place, convert the metres to feet and inches, with inches to one decmial place. For example, 1.5 metres would be converted to 4' 11.1".

Solution
#include <stdio.h>
#include <math.h>

int main(void)
{
    double start;
    double end;

    printf("Range start: ");
    scanf("%lf", &start);

    printf("Range end: ");
    scanf("%lf", &end);

    double metres = start;
    
    printf("Metres\tFeet\n");
   
    // Why did I need to add 0.005?
    while (metres <= end + 0.005) {
        double feet = metres * 3.281;

        // Before challenge:
        // printf("%.1f\t%.1f\n", metres, feet);

        double remainder = feet - floor(feet);
        feet -= remainder;

        double inches = remainder * 12;

        printf("%.1f\t%.0f' %.1f\"\n", metres, feet, inches);

        metres += 0.1;
    }

    return 0;
}

Palindrome Numbers

Write a program that accepts two integers, and prints every integer in between which is a palindrome. Your program should work like so:

$ ./palindromes
Range start: 100
Range end: 230
101
111
121
131
141
151
161
171
181
191
202
212
222

The problem might seem quite large at first, so it helps to break it down. First, see if you can write a function which checks if one number is a palindrome. You might find C's integer divison and the modulo operator (%) helpful.

You can assume all your inputs are valid.

Autotests are available for this exercise by running ./autotest.sh palindromes

Solution
#include <stdio.h>

int reverse(int n)
{
    // Reverse the number numerically
    
    int r = 0;
    while (n != 0) {
        // "Shift" all the digits in r along, and add the leftmost digit from n
        r = r * 10 + n % 10;
        // Integer divide n by 10, knocking off the last digit
        n = n / 10;
    }

    return r;
}

int main(void)
{
    int start;
    int end;

    printf("Range start: ");
    scanf("%d", &start);

    printf("Range end: ");
    scanf("%d", &end);

    int n = start;
    while (n <= end) {
        if (n == reverse(n)) {
            printf("%d\n", n);
        }
        n++;
    }

    return 0;
}

Loose Change

Write a program which, given an amount of money, will output how many of each type of note and coin is required to make that amount of money using the fewest notes / coins possible. Your program should work like so:

$./change
Enter amount: 140.30
1   x Hundred dollar notes
0   x Fifty dollar notes
2   x Twenty dollar notes
0   x Ten dollar notes
0   x Five dollar notes
0   x Two dollar coins
0   x One dollar coins
0   x Fifty cent coins
1   x Twenty cent coins
1   x Ten cent coins
0   x Five cent coins

Your program need only work for Australian dollars, but you should think about how you can make your program easy to modify for another currency.

Autotests are available for this exercise by running ./autotest.sh change

Solution
#include <stdio.h>

#define N_DENOMINATIONS 12

int main(void)
{
    double amount;
    printf("Enter amount: ");
    scanf("%lf", &amount);

    int cents = amount * 100;

    int denominations[N_DENOMINATIONS] = { 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5 };
    char* names[N_DENOMINATIONS] = { "Two hundred dollar notes",
                                     "Hundred dollar notes",
                                     "Fifty dollar notes",
                                     "Twenty dollar notes",
                                     "Ten dollar notes",
                                     "Five dollar notes",
                                     "Two dollar coins",
                                     "One dollar coins",
                                     "Fifty cent coins",
                                     "Twenty cent coins",
                                     "Ten cent coins",
                                     "Five cent coins" };

    int count[N_DENOMINATIONS] = { 0 };

    int d = 0;
    while (d < N_DENOMINATIONS) {
        count[d] = cents / denominations[d];
        cents = cents % denominations[d];

        printf("%d\tx %s\n", count[d], names[d]);

        d++;
    }

    return 0;
}

Advanced Programs

These are some more advanced programs which attempt to solve a real practical problem with C. Make sure you've taken a look at structs and file handling before attempting these. These problems also make use of more advanced strategies like sorting and dynamic programming.

C Cinema

(Based off a suggestion from Julie, thanks Julie ♥)

You can download the starter files for this exercise, and unzip them manually or using the Linux command line:

$ unzip -n cinema.zip

You're given a series of animation files, which are text files. The first line contains the height of the frames, in lines, followed by the number of frames. The rest of the file consists of the frames themselves.

Your code should load each of the frames, and print them one after another. Some skeleton code which iterates through the frames, clears the screen and gives a delay is provided for you.

The name of the animation file to use is given as a command line argument, for example:

$ ./cinema rain.txt

You can press Ctrl + C to stop the animation at any time.

You can assume you will always be provided with a command line argument, and that it refers to a valid animation file with at least one frame with a height of at least one line and with lines containing no more than 64 characters.

Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

struct frame {
    char* text;
    struct frame* next;
};

void delay();

int main(int argc, char** argv)
{
    struct frame* start = NULL;
    struct frame* curr = NULL;

    FILE* f = fopen(argv[1], "r");
    char line[64];

    int height;
    int frames;

    fgets(line, 64, f);
    sscanf(line, "%d %d", &height, &frames);

    int i = 0;
    while (i < frames) {
        struct frame* new = malloc(sizeof(struct frame));
        new->text = malloc(64 * height);
        new->next = NULL;

        new->text[0] = '\0';

        int j = 0;
        while (j < height) {
            fgets(line, 64, f);
            strcat(new->text, line);

            j++;
        }

        if (start == NULL) {
            start = new;
            curr = new;
        } else {
            curr->next = new;
            curr = new;
        }

        i++;
    }

    curr->next = start;
    curr = start;

    while (1) {
        printf("\e[2J\e[H");

        printf("%s", curr->text);

        curr = curr->next;        

        delay();
    }

    return 0;
}

// Ignore me
void delay()
{
    struct timespec ts;
    ts.tv_sec = 0;
    ts.tv_nsec = 200 * 1000 * 1000;
    nanosleep(&ts, NULL);
}

Bee Hive Stats

You are given a file by a beekeeper, which contains statistics for her beehives. The file is formatted like so:

2 790 Pears
17 360 Oranges
20 860 Rose
19 1040 Wildflowers
...

The first column is the amount of honey produced in kg, the second column is the amount of bees in the hive, and the third column is the name of the plant the bees are feeding from.

Write a program that reads this file. Once the data has been read, the honey production per bee for each hive should be calculated, then the data for each hive should be sorted by that and printed. Your program should work like so:

$ ./bees
--- Hive #55 ---
Flower: Apples
Honey produced: 18 kg
Bee population: 110
Honey / bee: 0.164 kg
--- Hive #175 ---
Flower: Tomatoes
Honey produced: 14 kg
Bee population: 100
Honey / bee: 0.140 kg
...

The file will contain valid data for no more than 256 hives. Flower names will be no more than 32 characters long.

Autotests are available for this exercise by running ./autotest.sh bees

Optional challenge: Format the output using terminal colours.

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

struct hive {
    int number;
    int honey;
    int pop;
    double honey_per_bee;
    char flower[32];
};

int comp(const void* a, const void* b)
{
    struct hive* a_hive = (struct hive*) a;
    struct hive* b_hive = (struct hive*) b;

    return a_hive->honey_per_bee < b_hive->honey_per_bee;
}

int main(void)
{
    FILE* stats = fopen("bees.txt", "r");

    struct hive hives[256];
    int n_hives = 0;

    int honey; int pop; char flower[32];
    while (fscanf(stats, "%d %d %s", &honey, &pop, flower) > 0) {
        hives[n_hives].number = n_hives;
        hives[n_hives].honey = honey;
        hives[n_hives].pop = pop;
        hives[n_hives].honey_per_bee = honey/(pop*1.0);
        strcpy(hives[n_hives].flower, flower);

        n_hives++;
    }

    qsort(hives, n_hives, sizeof(struct hive), comp);

    int i = 0;
    while (i < n_hives) {
        /* Before challenge:
        printf("--- Hive #%d ---\n", hives[i].number);
        printf("Flower: %s\n", hives[i].flower);
        printf("Honey produced: %d kg\n", hives[i].honey);
        printf("Bee population: %d\n", hives[i].pop);
        printf("Honey / bee: %.3lf kg\n", hives[i].honey_per_bee); */
        
        printf("--- \e[92mHive #%d\e[0m ---\n", hives[i].number);
        printf("\e[95mFlower:\e[0m %s\n", hives[i].flower);
        printf("\e[93mHoney produced:\e[0m %d kg\n", hives[i].honey);
        printf("\e[96mBee population:\e[0m %d\n", hives[i].pop);
        printf("\e[94mHoney / bee:\e[0m %.3lf kg\n", hives[i].honey_per_bee);

        i++;
    }

    return 0;
}

Challenge: Find-a-Word Solver

You are given a file which contains a 2D grid of upper-case letters:

QHTLCAZALRVZQAV
IMFSTLSLCYPUOLY
YCWDFMEEFXLGQBK
ZPJBZLELHHUMXLP
LDTPOQDRDCEUCWY
XPEVJUQDUEATCMF
KVTGBGHLJTFDTMF
LFHBRONKMEAFAVH
REIURATIYPCVEEF
SNANHEBLLRDKRCH
GGEHNWWTQWOQQUT
TDFYWSRENNALPZC
MVLOBXVRGALBCBR
HSPROCKETSYQGEP
IKNCHZUSINJHNQF

Write a program which is able to find words in this grid, giving the position of the start of the word (with 0, 0 being the top-left) and the direction of the word, for example:

$ ./wordsearch
HEADACHE
HEADACHE found at (14, 9) goind up and left
NICK
NICK could not be found
PLANNERS
PLANNERS found at (12, 11) going left

Words can go in any direction. Words may not appear at all, as seen above. If a word appears more than once, then finding any occurence of the word is valid. Words may intersect each other. You can assume the words searched for and the words in the find-a-word will be all in upper case.

Autotests are available for this exercise by running ./autotest.sh wordsearch

Optional challenge: Write a program which can generate find-a-word puzzles.

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

#define MAX_SIZE 48

#define DIR_UP 1
#define DIR_RIGHT 2
#define DIR_DOWN 4
#define DIR_LEFT 8

int search(char** grid, int width, int height, char* word, int x, int y, int direction)
{
    if (*word == '\0') return 1;

    if (x == -1 || x == width || y == -1 || y == height) return 0;

    if (grid[y][x] != *word) return 0;

    if (direction & DIR_UP) y--;
    if (direction & DIR_DOWN) y++;

    if (direction & DIR_RIGHT) x++;
    if (direction & DIR_LEFT) x--;

    return search(grid, width, height, word + 1, x, y, direction);
}

int main(void)
{
    char** grid;
    int width;
    int height;

    grid = malloc(sizeof(char*) * MAX_SIZE);
    for (int i = 0; i < MAX_SIZE; i++) grid[i] = malloc(sizeof(char) * MAX_SIZE);

    FILE* puzzle = fopen("puzzle.txt", "r");

    int i = 0;
    while (fgets(grid[i], MAX_SIZE, puzzle)) i++;

    width = strlen(grid[0]);
    height = i;

    int directions[8] = { DIR_UP, 
                          DIR_UP | DIR_RIGHT,
                          DIR_RIGHT,
                          DIR_DOWN | DIR_RIGHT,
                          DIR_DOWN,
                          DIR_DOWN | DIR_LEFT,
                          DIR_LEFT,
                          DIR_LEFT | DIR_UP };
    char* direction_names[8] = { "up",
                                 "up and right",
                                 "right",
                                 "down and right",
                                 "down", 
                                 "down and left", 
                                 "left", 
                                 "up and left" };

    char word[MAX_SIZE];
    while (fgets(word, MAX_SIZE, stdin)) {
        *(strchr(word, '\n')) = '\0';

        int found = 0;
        int found_x, found_y, found_dir;
        for (int y = 0; !found && y < height; y++) {
            for (int x = 0; !found && x < width; x++) {
                if (word[0] == grid[y][x]) {
                    for (int i = 0; !found && i < 8; i++) {
                        if (search(grid, width, height, word, x, y, directions[i])) {
                            found = 1;

                            found_x = x;
                            found_y = y;
                            found_dir = i;
                        }
                    }
                }
            }
        }

        if (found) printf("%s found at (%d, %d) going %s!\n", word, found_x, found_y, direction_names[found_dir]);
        else printf("%s could not be found\n", word);
    }

    return 0;
}

Challenge: Chicken Wings Problem

The chicken wings problem is a famous problem which appeared on the internet, in which a shop sold chicken winds at many different price bands.

You will make a program which accepts as input many lines, which contain the number of wings and the price for that number of wings. The program then asks the user how many wings they want to buy, and advises them on the purchasing strategy which will cost the least amount of money. The program should work like so:

$ ./wings
Number of price bands: 4
1 2.00
3 4.50
5 5.50
10 7.50
Number of wings to buy: 22
Optimal strategy:
2x 10 wings for 7.50 each
2x 1 wings for 2.00 each
Total cost: 19.00

You can assume all inputs will be valid and that there will be no more than 64 price options.

You can assume there will always be a way to buy a single chicken wing. You can not assume that buying more wings will always give a better value.

Autotests are available for this exercise by running ./autotest.sh wings

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

struct price_band {
    int number;
    double price;
    double price_per_wing;
};

int comp(const void* a, const void* b)
{
    struct price_band* a_p = (struct price_band*) a;
    struct price_band* b_p = (struct price_band*) b;

    return a_p->price_per_wing > b_p->price_per_wing;
}

int memoisation_band[1024];
double memoisation_cost[1024];

double optimal_strategy(int n_wings, struct price_band* bands, int n_bands, int print)
{
    if (n_wings == 0) return 0.0;

    int min_band = -1;
    double min_cost = 0.0;

    if (memoisation_band[n_wings] == -1) {
        int i = 0;
        while (i < n_bands) {
            if (bands[i].number <= n_wings) {
                int num = n_wings / bands[i].number;
                double cost = (bands[i].price * num) + optimal_strategy(n_wings % bands[i].number, bands, n_bands, 0);

                if (cost < min_cost || min_band == -1) {
                    min_band = i;
                    min_cost = cost;
                }
            }

            i++;
        }

        memoisation_band[n_wings] = min_band;
        memoisation_cost[n_wings] = min_cost;
    } else {
        min_band = memoisation_band[n_wings];
        min_cost = memoisation_cost[n_wings];
    }
    
    int num = n_wings / bands[min_band].number;
    
    if (print) {
        printf("%d x %d wings at %.2lf each\n", num, bands[min_band].number, bands[min_band].price);
        optimal_strategy(n_wings % bands[min_band].number, bands, n_bands, 1);
    }

    return min_cost;
}

int main(void)
{
    struct price_band bands[64];

    int i = 0;
    while (i < 1024) {
        memoisation_band[i] = -1;
        memoisation_cost[i] = 0.0;
        i++;
    }
    
    int n_bands;
    printf("Number of price bands: ");
    scanf("%d", &n_bands);

    i = 0;
    int number;
    double price;
    while (i < n_bands) {
        scanf("%d %lf", &number, &price);
        bands[i].number = number;
        bands[i].price = price;
        bands[i].price_per_wing = price / number;

        i++;
    }

    qsort(bands, n_bands, sizeof(struct price_band), comp);

    int number_required;
    printf("Number of wings to buy: ");
    scanf("%d", &number_required);

    printf("Optimal strategy: \n");
    double total_cost = optimal_strategy(number_required, bands, n_bands, 1);

    printf("Total cost: %.2lf\n", total_cost);

    return 0;
}