Volume 5

Exercise	Focus
0. Increasing Intervals	Scan an array and identify increasing runs
1. Uniques	Count occurrences using a direct access table
2. Chess Moves	Apply offsets and check two-dimensional bounds
3. Subsets	Generate choices recursively and restore state

Getting Started

• Don’t know how to get started with a Volume? Refer to the instructions in Tutorial 0
• To understand how the volumes are graded, refer to How Are Volumes Graded
• To read our expectations for code in this course, read C Standards

Open your WebTop in Entainer. Run cs1010, select Download CS1010 content, then choose Volumes and Volume 5. Work in the downloaded Volume 5 directory.

For each exercise, write your answer in student.c inside the named directory. You may add helper functions there as well. We have already written the code that reads input and starts the program, so you do not need to change main.c or the header files. Each exercise below explains whether your function should print its result or return it for the program to print.

The Makefiles enable ASan and UBSan. Consider revisiting Tutorial 5: Sanitisers if you need help understanding a sanitiser report.

0. Increasing Intervals

Focus

Scanning an array with loops and keeping track of where a run starts and ends.

Introduction

An array does not have to be sorted for parts of it to be increasing. For example, consider these numbers:

$$2,6,9,1,22,8,55,3.$$

The first three numbers increase, but the next number, 1, breaks that pattern. We can split the whole array into strictly increasing runs:

$$[2,6,9],[1,22],[8,55],[3].$$

Within a run, each number is strictly greater than the one before it. We keep extending the run until the next number is equal or smaller, or we reach the end of the array. Your task is to find the length of each of these runs.

Your Task

In 0-intervals/student.c, implement:

void interval_lengths(int arr[], size_t len);

The array contains len integers. Print the length of each increasing run on its own line, in the order the runs appear in the array.

Expected Behaviour

Every element belongs to exactly one run, and a run can contain just one element. For the example above, the lengths are 3, 2, 2, and 1.

Equal adjacent values start a new run too. For example, [2, 2, 3] splits into [2] and [2, 3], with lengths 1 and 2. An empty array has no runs, so your function should print nothing when len is 0.

Running and Testing

• To compile: run make in 0-intervals
• To run: run ./intervals
• To test: run make test

Type the array’s integers on one line, separated by spaces, then press Enter. A blank line represents an empty array. We handle reading the array; printing the run lengths is part of your function.

Examples

For the array discussed above:

Example 1

Input

2 6 9 1 22 8 55 3

Output

3
2
2
1

Notice what happens when two neighbouring values are equal:

Example 2

Input

2 2 3

Output

1
2

Hints

Hint

Think about using two indices, left and right, rather than just one. What does each index represent? How should they advance, and how do you know when the current run ends?

---

1. Uniques

Focus

Finding uniquely-appearing elements in an array

Introduction

This time, we’re interested in how often a number appears, rather than where it appears. You will receive an array whose values are between 1 and 100, inclusive. Find the values that appear exactly once in the entire array.

For example, in [1, 3, 5, 7, 1, 3, 9], both 1 and 3 appear twice. The values 5, 7, and 9 appear once each, so these are the values we want to keep. Collect the results in ascending order, even if they appeared in a different order in the input.

Your Task

In 1-uniques/student.c, implement:

size_t find_uniques(int const arr[], size_t arr_size, int uniques[100]);

The input array arr contains arr_size values. Write the values that occur exactly once in arr, into uniques, starting at index 0, and return the number of values you wrote. The output array has room for 100 values. You do not need to print anything in this function.

What is this const thing?

We’ll explain it in more detail soon, but the const keyword in this context means that arr should not be modified (i.e., it should be “constant”)

Fun fact: this used to be a TA interview question!

Some of your TAs know: when we interviewed them, we asked them to live-code a solution to this problem within 15 minutes, while also explaining their solution to us as they wrote it :)

Expected Behaviour

The values you write must be in ascending order. For the example above, write 5, 7, and 9 into uniques[0], uniques[1], and uniques[2], then return 3.

A value that appears twice or more must not appear in the result. If every value is repeated, or if the input array is empty, return 0. The input array is read-only; use uniques for your results.

Running and Testing

• To compile: run make in 1-uniques
• To run: run ./uniques
• To test: run make test

Type the array’s integers on one line, separated by spaces, then press Enter. Each integer must be between 1 and 100. A blank line represents an empty array. The program prints num_uniques: followed by your returned count, then prints each of your results on its own line.

Examples

The repeated values are left out of the result:

Example 1

Input

1 3 5 7 1 3 9

Output

num_uniques:3
5
7
9

The order of the input does not determine the order of the result:

Example 2

Input

9 5 7

Output

num_uniques:3
5
7
9

For 1 1 1, the only output is num_uniques:0.

Hints

Hint

You know the range of possible values before you start. Could an array record how often each value appears? How could you then use that array to collect the results in ascending order?

---

2. Chess Moves

Focus

Two-dimensional arrays, movement offsets, and checking bounds before accessing a tile.

Introduction

Let’s put those two-dimensional arrays to work on a chessboard! You will be given one chess piece and its position on an otherwise empty 8 by 8 board. Your task is to mark all the tiles that the piece could move to in one move.

You do not need to know chess already. These are the movement rules for this exercise:

Character	Piece	Movement
K	King	One tile in any horizontal, vertical, or diagonal direction
Q	Queen	Any number of tiles horizontally, vertically, or diagonally
R	Rook	Any number of tiles horizontally or vertically
B	Bishop	Any number of tiles diagonally
N	Knight	Two tiles along one axis and one tile along the other, in any direction

There are no other pieces or obstacles to consider. A move must stay on the board, and the piece’s current tile is not a destination.

Your Task

In 2-chess/student.c, implement:

void mark_moves(char piece, Position pos, char board[8][8]);

The Position type is already defined in student.h:

typedef struct Position {
    int row;
    int col;
} Position;

The array board initially contains * in every tile. Replace each reachable tile with uppercase X, and put the piece character in its own tile. Leave all other tiles as *. Update the array directly; the program will print it afterwards.

Expected Behaviour

Both coordinates are between 0 and 7. Rows count upward from the bottom of the board, and columns count rightward from the left. Access the piece’s tile as board[pos.row][pos.col]. For example, a rook at row 1, column 3 is at board[1][3].

Only mark positions inside the board. A bishop in a corner can move along just one diagonal; a king at an edge has fewer destinations than a king in the middle. Remember to keep the piece character in its original tile, even when marking its row or column.

Running and Testing

• To compile: run make in 2-chess
• To run: run ./chess
• To test: run make test

Type a piece character followed by its row and column, separated by a comma. For example, R 1,3 means a rook at row 1, column 3. The program prints the board from the top row down, so row 7 appears first and row 0 appears last.

Examples

A king at row 1, column 1 can reach all eight neighbouring tiles:

Example 1

Input

K 1,1

Output

********
********
********
********
********
XXX*****
XKX*****
XXX*****

For a rook, mark its row and column while keeping the R at its own position:

Example 2

Input

R 1,3

Output

***X****
***X****
***X****
***X****
***X****
***X****
XXXRXXXX
***X****

Hints

Hint

The offset arrays and bounds checks from Lab 5 may help here. For pieces that can move several tiles in one direction, think about how to extend an offset until you reach the edge of the board.

---

3. Subsets

Focus

Recursion, making include-or-exclude choices, and restoring state between calls.

You should (probably) use recursion here

We haven’t forgotten about recursion, and this is a problem that you might find easier to solve with recursion :)

Introduction

A subset is a selection of elements from a set. For example, the set {1,2} has four subsets: {}, {1}, {2}, and {1,2}. The empty set {} counts as a subset, and so does the whole set.

In this exercise, you will generate every subset of {1,2,...,n} using recursion. Each element gives you a choice: include it in the current subset, or leave it out. There are $2^n$ different subsets altogether, so even a small value of n gives you plenty to print!

Your Task

In 3-subsets/student.c, complete:

void generate_subsets(Set set, int num_elements);

The program starts with an empty Set and calls your function with num_elements equal to n. The Set type lets you use a few functions to work with a set without needing to manage its storage yourself:

• insert_into_set(set, element) adds an element to the current set
• remove_from_set(set, element) removes an element from the current set
• print_set(set) prints the current set on one line

The base case is already written for you:

if (num_elements == 0) {
    print_set(set);
    return;
}

Complete the recursive case so that every possible subset reaches this base case exactly once.

Expected Behaviour

The input satisfies 1 <= n <= 12. Print every subset exactly once, including the empty set and the full set. Each subset must contain only elements from 1 to n, with no repeated element.

The order of the subsets does not matter, and neither does the order of the elements within a subset. For example, {1,2} and {2,1} represent the same subset; print one of them, rather than both. Use print_set to keep the braces and comma-separated format shown below. Generate the subsets recursively.

Running and Testing

• To compile: run make in 3-subsets
• To run: run ./subsets
• To test: run make test

Type one integer n, then press Enter. The program calls your function with an empty set. Unlike exercises where you return a result, this function prints subsets through its base case. The tests accept any ordering that contains every subset exactly once.

Examples

For n = 2, one valid output is:

Example

Input

2

Output

{}
{1}
{2}
{1,2}

You could print the same four subsets in another order and still have a correct answer. For n = 1, you should print just {} and {1}, in either order.

Hints

Hint

For each element, explore both choices: including it and excluding it. If one recursive call adds an element to the set, what do you need to undo before exploring another choice?