EEEN10036 C Programming Assignment: Escape From Island
Introduction
The purposes of the coursework part of the course are:
1. To give a slightly longer programming exercise than that which can be undertaken in a standard lab session.
2. To give a more open-ended programming task. That is, a task with an overall aim and set of requirements, and then freedom for you as a programmer to devise the most appropriate solution. Depending on coding style, a complete solution likely requires 200-400 lines of code.
3. To provide summative feedback on your work and performance, completing the formative feedback from the labs.
Aim
Objective
The objective of this assignment is to write a C program which estimates the probability that an explorer will safely escape from a dinosaur- and volcano-infested island ("Jurassic Island") by taking random walks across it. As well as calculating the probability of escape, the mean and standard deviation of the path lengths should be determined for each starting cell.
Island map
The island map is represented as a 9x9 array:
B W W B B W B W W
B L L V L L L L B
W L L L L D L L B
B L L D L L L L W
B L D L L L L L W
W L L L L L V L B
W V L L L L L L W
W L L L D L L L W
B B W B W B B W B
where each cell is labelled as follows:
· L: Land, the explorer can safely step on this cell.
· B: Bridge, the explorer can safely step on this cell and use it to get off the island.
· W: Water, the explorer will die if this cell is stepped on.
· D: Dinosaur, the explorer will die if this cell is stepped on.
· V: Volcano, the explorer will die if this cell is stepped on.
Note that there is a space between each letter in the island map and no space at the end of the line. Also, this is not the same map as that used in the task itself.
The only way to escape from the island is for the explorer to step onto a Bridge (B) cell.
Stepping onto a Land (L) cell is safe, however if the explorer steps on a Dinosaur (D), Volcano (V), or Water (W) cell, the walk is terminated and the next random walk should be attempted.
Task
Each cell in the map is to be used as a starting point for walks, beginning, for example, with the B cell at the top-left corner (i.e. [0][0] in a 2D array representing the island map).
For each cell on the map, the program should perform 1000 random walks where the explorer attempts to get off the island.
On each attempt, the explorer can take up to, and including, 10 steps before they run out of energy and the walk terminates unsuccessfully, moving on to the next attempt.
Each step on a walk is randomly chosen from one of eight directions, i.e. North (N), Northeast (NE), East (E), Southeast (SE), South (S), Southwest (SW), West (W), or Northwest (NW), with equal probability.
After each step, the program should check to see if the walk:
· Is successful by stepping onto a Bridge cell.
· Has failed by stepping onto a Dinosaur, Volcano or Water cell.
· Continues by stepping onto a Land cell.
· Has failed due to the maximum number of steps being taken.
For example, assuming that the explorer is near the top-left, at location [1][1] (ignoring the spaces) which is a Land (L) cell. If the next step is to the NW or E they will have stepped on a Bridge cell (B) and so will have escaped from the island successfully. If the next step is to E, SE, or S, then they have moved to another Land (L) cell and the walk should continue for another step. However, if the next step is to N, NE, or SW then the explorer lands on a Water (W) cell and the walk terminates unsuccessfully.
Requirements
Inputs
Your program should read a 9x9 island map from a text file, stored in the same directory as your program, called "island_map.txt".
Input validation
We will compile and execute your code, using unseen maps to check the behaviour. This will include passing invalid inputs to your code. You should add input validation checks to your code, anticipating the different ways in which a user may provide an incorrect input.
If your code detects an error with the input it should display:
Error!
and exit, with an exit status of 1. No other output should be displayed, and the text above must be exact. You can use:
printf("Error!");
to display the required text.
Starting conditions
You should analyse walk paths starting from each of the 81 possible starting cells in a 9x9 island map. If the starting cell is a Bridge (B), no steps are needed and so the path length should be recorded as 0. If the starting cell is Water (W), Dinosaur (D), or Volcano (V), the explore will die immediately and so the path length should be recorded as 0.
Coding scheme
To perform the random movement you must use the rand() function (see below). You should map each move to an integer value as follows:
· 0 represents move N.
· 1 represents move NE.
· 2 represents move E.
· 3 represents move SE.
· 4 represents move S.
· 5 represents move SW.
· 6 represents move W.
· 7 represents move NW.
This coding scheme is shown on the diagram below.
Generating random movements
You are required to use the rand() function to randomly move in one of eight possible directions.
rand(), which is part of the C standard library stdlib.h, returns a pseudo-random integer uniformly distributed within the interval given by [0, RAND_MAX], where RAND_MAX typically has a value of 32767.
You should constrain the range of random numbers that rand() generates by using the modulus (remainder) operator introduced in Topic 3.
Note that rand() must be seeded with a value before it is first called. For this purpose you must use srand() as:
srand(123456);
You should only call srand() once, near the start of your program in int main(). (Aside: Random numbers.)
If on an edge cell, and a random move would take the explorer outside the edge of the map, then the explorer should stay put in that direction. For example:
· If they are on the bottom row, and try and move South, they will stay on the same cell. (As a move South would take them out of the map.)
· If they are on the bottom row and try and move South East they will move East, but stay on the same row.
· If they are on the bottom row, in the bottom right corner, and move South East they will stay on the same cell. (As a move South would take them out of the map, and a move to the East would take them out of map.)
All of these cases still count as a step, and so the step counter should be incremented.
Note that the explorer can take up to 10 steps on each try. 0 and 10 are thus valid numbers of steps to take.
Standard deviation
The standard deviation is defined as
𝜎=∑i(xi−𝜇)2N‾‾‾‾‾‾‾‾‾‾‾‾√
where
xi
is element number
i
in array
x
,
𝜇
is the mean of array
x
, and
N
is the number of elements in array
x
. Note that the demonimator is N.
If checking your standard deviation function in another programming language, note that the above equation is implemented by (for an example array containing 1 to 10):
· Matlab: std([1, 2, 3, 4, 5, 6, 7, 8, 9, 10],1)
· Python with numpy: np.std(a,ddof=0)
Just say, just:
· Matlab: std([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
implements a different definition of the standard deviation (where the denominator is N-1.)
Other standard libraries
You can use other built-in C libraries as you wish, provided that all of your code is contained in the one coursework.c file. In particular, you may wish to use the sqrt() function included in math.h.
You are not allowed to include your own custom headers. These will not be used by the marking system.
Outputs
For every cell on the island map your program should display (to two decimal places when suitable):
· A copy of the input map.
· The probability of successfully escaping from the island, displayed as a percentage. That is, how many of the random walks made it to a Bridge (B) cell.
· The mean path length (i.e. number of steps) of successful walks.
· The standard deviation of path lengths of successful walks.
Invalid starting cells have 0.00 for the above numerical items. The values should be displayed to the terminal.
An example output is shown on the following page. The output displayed must be formatted correctly:
· Use the headings (e.g. "Map:") exactly as shown on the example.
· Numbers on the same row should be separated by spaces.
· Suitable format specifiers should be used to set the precision and field width, to keep information in each table aligned.
· Include a blank line in between each of the output blocks (the map display, probability display, and so on). There is no blank line between rows in a table.
Use of functions
Although you can complete a suitable program without them, we suggest that you use your own custom functions to keep your code compact and avoid repetitive code for common actions. You might like to use the following (incomplete) function prototypes:
· void random_step(…);
· int calculate_status(…);
where:
· random_step calculates the next random step.
· status returns the status of the next step:
o 0 Failure
o 1 Successfully made it to a bridge cell
o 2 Walk continuing
Planning and testing
We suggest that you plan your code, before you start typing it in. Think about the main steps your code has to go through - getting data, processing the data, and outputting the results.
You should also think about your test strategy. How will you check that your code does what you want it to do? How will you check that any functions you write in your code do what you want them to do? Feel free to make your own maps and use these to test your code.
Coding style and quality
We will check your code for common programming issues, including the number of comments used. You will lose marks if, for example, warnings are generated by the compiler, or there are issues with overflowing arrays.
Aside: Random numbers
Getting computers to generate truly random numbers is in fact really hard (but important, lots of encryption schemes rely on using random numbers).
In general, computers actually generate pseudo-random numbers. That is, they look random if you look at the probability distribution, but are in fact following a fixed pre-determined sequence. If you know where in this fixed sequence the program is starting from, known as the seed, you will get the same random numbers each time.
srand() sets the starting position in the number sequence. Using
srand(123456);
ensures you use the same random numbers each time the code is run, making your code easier to debug and to mark. If you run your code multiple times, you should find you get exactly the same output (which isn't what you would expect if the explorer was taking truly random walks).
This is the behaviour that we want in this coursework, but it probably isn't the behaviour that you want while programming more generally. Usually, you would use srand() more like:
srand(time(NULL));
time() is provided by the time.h header, and time(NULL) returns the current time. (In milliseconds since 00:00:00 1st January 1970, which is a format known as Unix time.) Thus, the seed to srand() is set based upon the current time, and so you will get different random numbers each time the program is run.
Note that even with the above seed rand() in general only produces approximately random numbers, and shouldn't be relied upon in situations where truly random numbers are important. There are other C libraries, beyond the scope of this course, that you can investigate for use in (for example) cryptography applications.
The implementation of rand() is also platform dependent. That is, the algorithm used to generate random numbers is different on Windows, macOS, and Linux. This means that the random numbers generated by the same function are different, even when using the same seed. The marking system uses Linux and will automatically convert for you whichever platform you develop your code on. The marking system will display what you should see if developing your code on Windows or macOS, in addition to what it sees when running the code on Linux.
