CS1010 Programming Methodology

Lab 5: Basic Problem Solving With Loops

We mostly spent the previous lab on more mechanical concepts about loops. This week, we will try to show certain “common patterns” that people use in loops. These tend to be helpful as a starting point. The lab will start by showing you code that corresponds to certain tasks, and how it’s written to correspond to that.

Then in the second half, we will have you write loops to solve similar looking problems. Try to apply whichever approach seems to be the most applicable based on the first half.

Get Started

Download the Lab 5 code through Entainer and open a terminal in the Lab 5 directory Each activity has its own directory and Makefile Run make inside the activity directory to compile its programs, and run it again after changing the code

The code to study and edit is in student.c. We handle input, program setup, and output in main.c; you do not need to change it. Shared declarations are in student.h.

The Makefiles enable AddressSanitizer and UndefinedBehaviorSanitizer. These can help you investigate invalid array accesses; refer to Tutorial 5: Sanitisers. Some snippets are deliberately unsafe or incomplete for you to investigate and fix.

Part 1: Pattern List

These patterns are not listed in any particular order, they just so happen to be clean practices that people do and they’re useful idioms that might make life easier in one way or another. You might notice quite a few of these have to also do with the idea of indexing.

Activity 1: Guarding Against Bounds

Open activity-1/student.c.

In activity-1, run make, then ./radius-sum

Enter idx (0 to 4) and radius (0 to 5), separated by a space

The array is {1, 2, 3, 4, 5}

Add the guard clauses in student.c, then rebuild with make

Let’s say we were given an integer array int arr[] (of integers) and had to sum up all elements within radius of a certain index 0 <= idx < n. Then the idea might look something like:

  1. Start from index idx
  2. Iterate to both the left and the right for radius iterations and sum those values up
  3. Return the sum

Which probably looks like this:

int radius_sum(int arr[], size_t idx, size_t n, size_t radius) {
    int sum = 0;
    sum += arr[idx];
    for (size_t r = 1; r <= radius; ++r) {
        sum += arr[idx + r]; // Point A
        sum += arr[idx - r]; // Point B
    }
    return sum;
}

Except if you did this, you ignore the possibility of running off the array. For example, given arr[] = {1, 2, 3, 4, 5}, idx = 1, and radius = 2, then we should sum up the elements 1, 2, 3, 4. But we would have iterated into a very large array index (because size_t is unsigned) if we ran the above code. And this in turn would likely cause the program to crash.

Reminder

Remember that array-out-of-bounds access is actually undefined behaviour. So it might not even crash. Sometimes you might see a segmentation fault. But other times the program might actually just terminate and return the correct value. It might also return the wrong value. No guarantees.

Take particular note that we can be promised that idx is within range of the array. It’s only the possibility of running out of bounds within our own iteration (this is very common).

So a very common way to handle this is to ask yourself:

In order for Point A to “not break”, what kind of condition(s) has/have to be true?

And similarly:

In order for Point B to “not break”, what kind of condition(s) has/have to be true?

Your Task: Refactor the above snippet with guard clauses so that the program won’t exhibit undefined behaviour. In particular, we should make sure each respective array access line only gets executed when it is “safe” to.

Activity 2: Offset Arrays

The original version is in activity-2/part-1/student.c, and Cheems’s incomplete version is in activity-2/part-2/student.c. Both programs initialise and print the grid.

In activity-2, run make

Run ./original and ./offsets to compare their behaviour

Each program reads x and y (both 0 to 4), separated by a space

Complete part-2/student.c, then rebuild with make

When you’re given an array (could be 1 dimensional or more) and you need to apply some sort of repeated logic on a set of offsets centered around some point, it’s actually pretty handy to store this in a fixed-size array.

As an example, let’s say that we were given some 2D array grid[][] with dimensions NUM_ROWS, and NUM_COLS, and some coordinate (row, col). And we wished to mark the surrounding tiles in the 4 cardinal directions with N, S, E, W respectively. Well, definitely one way to do this would be the following:

#include <stddef.h>
 
typedef struct Point {
    size_t x;
    size_t y;
} Point;
void mark_tiles(char grid[NUM_ROWS][NUM_COLS], Point coord) {
    if (coord.x >= 1) { // then the left tile is within bounds
        grid[coord.y][coord.x - 1] = 'W';
    }
 
    if (coord.x + 1 < NUM_COLS) { // then the right tile is within bounds
        grid[coord.y][coord.x + 1] = 'E';
    }
 
    if (coord.y >= 1) { // then the upper tile is within bounds
        grid[coord.y - 1][coord.x] = 'N';
    }
 
    if (coord.y + 1 < NUM_ROWS) { // then the lower tile is within bounds
        grid[coord.y + 1][coord.x] = 'S';
    }
}

Part 1:

You might notice that in our bounds check, when checking the “lower” bounds, we did:

if (coord.x >= 1) {
    ...
}
...
if (coord.y >= 1) {
    ...
}

Why did we not check it in the following way instead?

if (coord.x - 1 >= 0) {
    ...
}
...
if (coord.y - 1 >= 0) {
    ...
}

Part 2:

We want to clean this code up to be a little more succinct, and a little more extensible. Your colleague Cheems has prepared the following template for you:

#include <sys/types.h>
 
typedef struct Point {
    ssize_t x;
    ssize_t y;
} Point;
 
void mark_tiles(char grid[NUM_ROWS][NUM_COLS], Point coord) {
    ssize_t dy[4] = {};
    ssize_t dx[4] = {};
    char label[4] = {'N', 'S', 'E', 'W'};
    for (size_t idx = 0; idx < 4; ++idx) {
        grid[coord.y + dy[idx]][coord.x + dx[idx]] = label[idx];
    }
}

The code is incomplete, however. You need to fill out the arrays dy[] and dx[]. And also, how should you make sure that the array accesses are always safe (and don’t exhibit undefined behaviour)?

Your task: Complete the code written by Cheems to make sure that this program exhibits the same behaviour as the previous snippet.

Note

We are using ssize_t instead in this example, which can be used if you include the types.h header file, via #include <sys/types.h>. This of this as similar to size_t but allowing for negative values. (Typically the negative values are for error indication, but we’re instead using it here for other kinds of ergonomics.)

Activity 3: Direct Access Tables

Open activity-3/student.c.

In activity-3, run make, then ./months

Enter a month number when the program waits for input

After refactoring the function, rebuild with make

One more useful thing about arrays is the ability for you to map numbers directly into something you’d prefer. Consider the following code before that tries to map the months from 1 through 12 to the number of days in the month.

Here is a very tedious way to figure that out on a case by case basis.

unsigned int number_of_days_in_the_month(unsigned int num) {
    if (num == 1) {
        return 31;
    } else if (num == 2) {
        return 28;
    } else if (num == 3) {
        return 31;
    } else if (num == 4) {
        return 30;
    } else if (num == 5) {
        return 31;
    } else if (num == 6) {
        return 30;
    } else if (num == 7) {
        return 31;
    } else if (num == 8) {
        return 31;
    } else if (num == 9) {
        return 30;
    } else if (num == 10) {
        return 31;
    } else if (num == 11) {
        return 30;
    } else if (num == 12) {
        return 31;
    } else {
        return 0; // invalid month
    }
}

Your task: Can you think of a way you might be able to replicate this behaviour with a size 12 array? Refactor the above code to have the same behaviour with far fewer lines.

Activity 4: Applying Short Circuits

Open activity-4/student.c, which contains both versions.

In activity-4, run make

Run ./short-circuits 1 for the first version and ./short-circuits 2 for the second

Enter the array values on one line, separated by spaces; a blank line represents an empty array Try an array containing a nonzero value, an all-zero array, and an empty array

Study both functions in student.c; after changing the code, rebuild with make

Look at the following two snippets of code that tries to find the earliest index that is not 0 in an array. If no such index exists, we should return the length of the array.

size_t find_first_nonzero_ver1(int arr[], size_t len) {
    size_t idx = 0;
    while (idx < len && arr[idx] == 0) {
        ++idx;
    }
    return idx;
}
 
size_t find_first_nonzero_ver2(int arr[], size_t len) {
    size_t idx = 0;
    while (arr[idx] == 0 && idx < len) {
        ++idx;
    }
    return idx;
}

What’s the difference between the two snippets? Do both snippets work? Is there any potential case for undefined behaviour in either snippet?

Part 2: Problem Solving

Problem Solving Practice 1: Chess Moves

Attempt Chess Moves in Volume 5. Read the problem and examples there, then implement mark_moves in 2-chess/student.c. Download the Volume 5 code through Entainer as explained on that page.

Problem Solving Practice 2: Increasing Intervals

Practise scanning an array and keeping track of where a run starts and ends. Before you code, think about how your indices should advance and when each run ends.

Attempt Increasing Intervals in Volume 5. Read the problem and examples there, then implement interval_lengths in 0-intervals/student.c.

Graph View

Backlinks