Programming Fundamentals
Information
- This page contains extra challenge exercises for week 05.
- These exercises are not compulsory, nor do they provide any marks in the course.
- These exercises are intended for students that want more challenge in the course.
- You cannot submit any of these exercises, however autotests are available for them (Command included at bottom of each exercise).
Exercise
(●●●)
:
Pointer Path
Download pointer_path.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/23T1/activities/pointer_path/pointer_path.c .
Your task is to add code to these functions in pointer_path.c:
// Prints the index-path from the given `start` index. Starts in the `pointers`
// array and bounces between pointers->indices->pointers->indices...
void print_pointer_path(
int *pointers[MAX_SIZE],
int indices[MAX_SIZE],
int start
) {
// TODO: Complete this function
}
As a quick initial remark, the syntax int *pointers[MAX_SIZE]
can be read as "pointers is an array of length MAX_SIZE where each element is
a pointer to an integer"
Now, the next thing to understand is that every integer we store in a variable has a memory address. This means that all integers in an array have individual memory addresses.
Using this idea, we once again consider the two arrays in the function above:
int *pointers[MAX_SIZE]is an array ofint *int indices[MAX_SIZE]is an array ofint
This means that elements of 'pointers' can point to addresses of elements in 'indices'!
Likewise, elements of 'indices' can store the indices of elements in 'pointers', and so we can have a two-way connection.
For this exercise, inputs will be taken for both arrays such that all elements in 'pointers' will point to the addresses of elements in 'indices'.
Conversely, all elements in 'indices' will store an index into elements of 'pointers'.
From here, you are to print the path from a starting index that is taken by bouncing between the two arrays until you are back at the starting index
Consider example input for the program below.
./pointer_path Please enter which indices the pointer array will reference: 0 5 1 6 8 9 1 1 0 3 Please enter which indices the index array will reference: 5 5 3 2 0 8 1 6 7 9 What index will the path start at? 2 Pointer path: 2->1->5->9->9->3->end
In the initial 10 indices input, each number represents which index in the 'indices' array that an element in the 'pointers' array will reference. For example:
pointers[0]will reference&indices[0]pointers[1]will reference&indices[5]pointers[2]will reference&indices[1]pointers[3]will reference&indices[6]- And so on for all 10 indices...
Now, the next 10 indices act the same but in the reverse direction,
indices[0]will indexpointers[5]indices[1]will indexpointers[5]indices[2]will indexpointers[3]indices[3]will indexpointers[2]
A full diagram has been provided for these relations below. The top array
represents pointers and the bottom array represents
indices. Do not try
to understand it all at once as it can look quite messy. Simply pick an
index and follow the outgoing line to see single relations.
Now, in the example, 2 was chosen as the start of the path. The diagram
has been updated to show how the path is formed from this. Follow the red path
from index 2 in the pointers array.
The path printed in the example above follows this:
- Starts at index 2 of
pointers - Moves to index 1 of
indices - Moves to index 5 of
pointers - Moves to index 9 of
indices - Moves to index 9 of
pointers - Moves to index 3 of
indices - Index 3 of indices contains index 2 to pointers, meaning we have reached the start again, so we stop
Some more program examples are provided below.
./pointer_path Please enter which indices the pointer array will reference: 0 0 0 5 0 0 0 2 0 0 Please enter which indices the index array will reference: 0 0 3 0 0 7 0 0 0 0 What index will the path start at? 3 Pointer path: 3->5->7->2->end ./pointer_path Please enter which indices the pointer array will reference: 5 3 1 9 9 5 4 2 8 0 Please enter which indices the index array will reference: 3 8 4 5 1 9 6 0 9 4 What index will the path start at? 4 Pointer path: 4->9->end ./pointer_path Please enter which indices the pointer array will reference: 0 1 2 3 4 5 6 7 8 9 Please enter which indices the index array will reference: 1 2 3 4 5 6 7 8 9 0 What index will the path start at? 0 Pointer path: 0->0->1->1->2->2->3->3->4->4->5->5->6->6->7->7->8->8->9->9->end
Hints, Notes and Assumptions
- All arrays will be of size MAX_SIZE
- You will never have to deal with paths that don't make it back to the start index
- All input indices will be valid
- All elements in
pointerswill point to addresses of elements inindices - You can get the address of an element of
indicesby using&indices[i]whereiis any index
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest pointer_path
Exercise
(●●●)
:
Math with Function Pointers
Download function_pointers.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/23T1/activities/function_pointers/function_pointers.c .
Your task is to add code to these functions in function_pointers.c:
// Given an `operation`, return a pointer to the function that can perform
// that operation.
//
// E.g. if addition is the operation, a pointer to the `addition` function
// should be returned.
double (*get_operation_function(char operation))(double, double) {
// TODO: COMPLETE THIS FUNCTION & CHANGE THIS RETURN
return NULL;
}
// Performs an operation given various amounts of information.
void perform_operation(
double first,
double second,
double (*operation_function)(double, double)
) {
// TODO: COMPLETE THIS FUNCTION
}
For this exercise you will be exploring a new topic called Function Pointers. It is important to note that this is outside the scope of COMP1511 content, but is an interesting topic to look at.
Just like how we can store pointers to integers and doubles, we can actually store pointers to functions! This can be useful as we can also execute these functions as a result. This means that a single variable can reference and execute one function at a certain point in the program, and another function at another point!
Here is a basic program containing function pointers:
#include <stdio.h>
void add(int a, int b) {
printf("%d + %d = %d\n", a, b, a + b);
}
void subtract(int a, int b) {
printf("%d - %d = %d\n", a, b, a - b);
}
int main(void) {
// Create a new variable `function_pointer` that points at the `add` function
void (*function_pointer)(int, int) = &add;
// Perform the `add` operation
(*function_pointer)(10, 5);
// Now, set the function pointer to point at the `subtract` function
function_pointer = &subtract;
// Call the function again, but this time, subtraction occurs!
(*function_pointer)(10, 5);
return 0;
}
The output of this program is:
10 + 5 = 15 10 - 5 = 5
The biggest challenge with function pointers is often the syntax of it.
Here is a diagram that explains every section of the function_pointer
variable declaration.
It can also be seen from this that the function_pointer variable
can only point at functions which take in two integers and return nothing.
Now, since function pointers have "types", it should be evident that they can also be used in both input and output of functions!
In this exercise, you are to implement the two functions seen above. The first function will return a different function pointer based on input. The second function will take in a function pointer as input to be used.
The actual program consists of constantly taking input from the user to
perform mathematical operations. The user first enters an operation they want to
perform ('+', '-', '*', '/'). You will be implementing a function
get_operation_function that uses that input to return a pointer to
the corresponding function for that operation.
If you look through the provided code, there are already addition,
subtraction, multiplication and division functions implemented.
The user then enters 2 doubles as input to perform this operation on.
The next function you will need to implement is perform_operation
which takes these two inputs as well as a function pointer and calls the
function referenced by it, using the inputs as the parameters.
Examples are shown below.
./function_pointers
Please enter an operation: +
Please enter 2 numbers to perform this operation on: 2 3
Applying this operation to 2.000000 and 3.000000 gives 5.000000
Please enter an operation: -
Please enter 2 numbers to perform this operation on: 5 3
Applying this operation to 5.000000 and 3.000000 gives 2.000000
Please enter an operation: *
Please enter 2 numbers to perform this operation on: 3 3
Applying this operation to 3.000000 and 3.000000 gives 9.000000
Please enter an operation: /
Please enter 2 numbers to perform this operation on: 5 2
Applying this operation to 5.000000 and 2.000000 gives 2.500000
Please enter an operation:
./function_pointers
Please enter an operation: +
Please enter 2 numbers to perform this operation on: 1 1
Applying this operation to 1.000000 and 1.000000 gives 2.000000
Please enter an operation: +
Please enter 2 numbers to perform this operation on: 1 5
Applying this operation to 1.000000 and 5.000000 gives 6.000000
Please enter an operation: +
Please enter 2 numbers to perform this operation on: 100 100
Applying this operation to 100.000000 and 100.000000 gives 200.000000
Please enter an operation: /
Please enter 2 numbers to perform this operation on: 1000 1000
Applying this operation to 1000.000000 and 1000.000000 gives 1.000000
Please enter an operation:
./function_pointers
Please enter an operation: *
Please enter 2 numbers to perform this operation on: 2 3
Applying this operation to 2.000000 and 3.000000 gives 6.000000
Please enter an operation: {
Invalid operation '{'
Please enter an operation: +
Please enter 2 numbers to perform this operation on: 5 4
Applying this operation to 5.000000 and 4.000000 gives 9.000000
Please enter an operation:
If the user inputs an invalid command, return NULL; in the
get_operation_function function. NULL is a standard
way for programmers to identify if a pointer actually points anywhere of value
Hints, Notes and Assumptions
- You can assume all number inputs will be valid
- If you have a function pointer named
functhat takes 3 integers as input, it can be called by saying(*func)(1, 2, 3). The(*func)means dereference the pointer so we can get to the function, then the(1, 2, 3)is the giving the parameters
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest function_pointers
Exercise
(●●●)
:
Conway's Game of Life
For this exercise, you are to write a program game_of_life.c
that simulates
Conway's Game of Life.
This game consists of a 2D grid of cells. Each cell is said to be on 1 of 2 states:
- Dead
- Alive
In this game, the grid is said to change every "tick". The change that occurs depends on the states of each cell. Cells that are alive can die based on information about their neighbours and cells that are dead can come back to life under their own conditions.
There are many variations on what conditions are used to determine the next state of a cell. For this exercise, we will use the classic rules that were originally defined. These rules are listed below.
- If an alive cell has 2 or 3 neighbours, it will be alive in the next state.
- If a dead cell has exactly 3 neighbours, it will be alive in the next state.
- If none of the above conditions are met, the cell in question is dead in the next state.
The neighbours of a given cell are the 8 surrounding cells. E.g. if you take a cell, it has a neighbour above, below, left, right and all diagonals to it.
In this exercise, you will take input from the user in the form of row/column pairs. These correspond to the cells that will be alive when the game starts. All other cells will be dead to begin with.
You will be required to work in a 20x20 array representing a total of 400 cells. In the original Game of Life, it is assumed that the grid is infinite, however, in our game, it will obviously be 20x20.
An addition that has been made as a result of this is that cells can wrap around the grid and have no edge restrictions. This means that cells in row 0 can be affect by cells in row 19, and the same goes for columns.
Sample Program
A fully implemented version of the application is provided below. Click on the squares to make them alive (black means alive, white means dead). Then, click on the Tick button to see what the next state of the grid will be. This can be repeated as much as you would like. Using the Play button makes the grid tick continuously. The frequency can be changed in the Tick Frequency dropdown.
Example inputs and outputs of your program are provided below. Basic steps that you will need to implement are:
- Scan in an arbitrary number of pairs which index the grid. Each pair makes the corresponding cell alive.
- Continuously provide commands to manipulate the grid. Commands are:
- p - Print the current grid
- t n - "Tick" the grid n times where n is a positive
integer
- q - Quit the program
./game_of_life Please enter the row and column of all alive cells. When finished, enter 'p'. 3 2 3 4 4 2 4 4 5 2 5 3 5 4 p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # . . . . . . . . . . . . . . . . . # . # . . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t 1 Ticked 1 times! p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . . . # . # . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t 1 Ticked 1 times! p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t 5 Ticked 5 times! p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . # # . . . # # . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . q Exiting... ./game_of_life Please enter the row and column of all alive cells. When finished, enter 'p'. 3 10 4 10 5 6 5 10 6 5 6 7 6 10 7 6 7 8 7 10 8 9 8 10 8 11 9 8 9 10 9 12 10 11 11 9 11 12 12 8 12 11 13 7 13 10 14 7 14 9 15 8 p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . # . . . # . . . . . . . . . . . . . . # . # . . # . . . . . . . . . . . . . . . # . # . # . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . # . # . # . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . # . . # . . . . . . . . . . . . . . . # . . # . . . . . . . . . . . . . . . # . . # . . . . . . . . . . . . . . . . # . # . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t 1 Ticked 1 times! t 3 Ticked 3 times! t 8 Ticked 8 times! p Current cell state: . . . . . . . . . # . . # . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . # # . # . . # . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . # . . . . # . . . . . . . . . . . . . # . . . . . . # # . . . . . . . . . # # . . . . # . . # # . . . . . . . . . # . . . . . # # . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . # . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . t 30 Ticked 30 times! p Current cell state: . . . . . # # . . # # . . . . . . . . . . . . . . . # # # # . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . # # . . . # # . . . . . . . . . . . . # # . . . # # # . . . . . . . . . . . . . # # # . . # # . . . . . . . . . . . . . # . # # . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . # # . . . # . . . . . . . . . . . . . . # . . . # . . . . . . . . . . . . . . . . # . . . . . . . . . . t 100 Ticked 100 times! p Current cell state: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . # # # # # . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . # . . . # . . . # . . . . . . . . . . # . . . . . . . # # . . . . . . . . . . . # . # . . . . # # . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . q Exiting...
Due to the sheer size of these outputs, no more will be provided. However, the interactive above is a great place to test different inputs and copy them to your program then tick side-by-side to test output.
Hints, Notes and Assumptions
- Your grid will always be 20x20 in size.
- Your grid can be of whatever type you wish (e.g. int, double char). However, cells can only have 2 states so keep that in mind.
- You will never be given invalid row/column pairs.
- You may need to create two cell arrays, one for the current state and one for the next state.
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest game_of_life