Task Five: “Connect Two”
For this task you need to calculate the shortest path between two points on a grid. The starting location will be labelled ‘1’ and the destination location will be labelled ‘2’. The shortest path will initially follow a diagonal (if necessary) followed by a vertical or horizontal path (if necessary).
Define a function called ConnectTwo() which is passed one input: a 2-dimensional array (10 rows and 10 columns) of integers. This 2-dimensional array represents a map. All elements in the array will be equal to zero, except for the starting location (which has the value 1) and the ending location (which has the value 2). Your function should determine the shortest path between these two locations and then modify the array by setting each element on the path to the value 3. The starting and ending locations should remain unchanged. The diagram below illustrates this (the input map is on the left, and the resulting modified map is on the right):
0000000100
0000003000
0000030000
0000300000
0003000000
0003000000
0003000000
0003000000
0002000000
0000000000
Element 1 represents the starting location and element 2 represents the destination
Function prototype declaration
1 | void ConnectTwo(int maze[10][10]) |
Assumptions
You can assume the input array dimensions are always 10x10, and that every element is initialised to zero except for the starting and ending locations (which will be initialised to 1 and 2 respectively).
Example
1 | int i, j; |
Expected output
1000000000
0300000000
0030000000
0003000000
0003000000
0003000000
0003000000
0003000000
0003000000
0002000000
Task Six: “The Wolf of Wall Street”
Your friend is trying to make money on the share market and has asked you to help them analyse the price data for a number of stocks they are looking at. In particular, they are interested in finding “runs” in the data, where a run consists of an increasing sequence of prices (moving left to right). For example, consider the data below which shows 10 prices changing over time:
123, 120, 118, 119, 121, 126, 127, 130, 129, 132
The longest “run” in this sequence of data values begins with the value 118. Starting with the value 118, the next 5 values are in strictly increasing order (119, 121, 126, 127, 130). The length of this “run” is therefore 5. Your friend wants you to write a program which takes a sequence of prices as input and calculates two things: where the longest “run” begins in the data and the length of the longest “run”.
Define a function called DayTrader() which takes four inputs: an array of integers representing the price information, the length of the array (i.e. the number of prices), and two integer pointers which you should use to store the calculated output values. The first pointer records the address where you should store the length of the best “run”, and the second pointer records the address where you should store the index position of the start of the “run”.
Function prototype declaration
1 | void DayTrader(int *prices, int numPrices, int *bestRun, int *bestRunIndex) |
Assumptions
You can assume that the array will contain at least one price (i.e. the length of the array will be greater than 0).
Runs only consist of strictly increasing values (two consecutive equal values do not constitute a “run”)
If there are two or more “runs” of the same length in the array, then you must return the smallest index position (i.e. left most value) when reporting the start of the run (i.e. the bestRunIndex)
Example
1 | int pricesA[15] = {59, 60, 55, 23, 42, 44, 48, 50, 43, 45, 43, 44, 47, 51, 52}; |
Expected output
Best run = 4, best run index = 3
Best run = 3, best run index = 6
Best run = 5, best run index = 2
Task Seven: “Compression”
Compression is an important technique for reducing the amount of space required to store information. This is of particular importance when large amounts of data need to be transmitted from one place to another. Define a function called Compress() which implements a basic compression algorithm. The input data to be compressed is represented simply as an array of positive integers. The end of the input data is indicated by the special value -1.
Compress the data by counting how many times a value is repeated consecutively. You can then represent that data value with two values: the number of repetitions of the value and the value itself. For example, if the data consists of eight “10”s: 10, 10, 10, 10, 10, 10, 10, 10 then this can be represented in compressed form as just two values: 8, 10.
Of course, this algorithm is not very effective if values aren’t repeated consecutively in the data. In the worst case, when there is no repetition, the compressed data will be double the size of the original data! You should store the compressed data in the second input to the function, which is also an array of integers. Don’t forget to place the value -1 at the end of the compressed data!
Function prototype declaration
1 | void Compress(int *input, int *output) |
Assumptions
The input array will always contain the special value -1 (indicating the end of the data).
The input array will consist of at least one value to be compressed (i.e. before the -1).
Ensure that you add the value -1 to the end of the compressed data in the output array.
Example
1 | int input[MAX_ARRAY_SIZE] = {7,7,7,7,7,3,4,4,4,7,0,0,0,0,0,0,0,0,0,0,0,0,-1}; |
Expected output:
5 7 1 3 3 4 1 7 12 0
Task Eight: “Arbitrary Incrementing”
In C, the int type is limited to (typically) 32 bits. The following example, where 1 is added to the largest positive integer value, illustrates integer overflow:1
2
3int value = 2147483647;
int result = value + 1;
printf("%d + 1 = %d", value, result);
In this case, the output would be:
2147483647 + 1 = -2147483648
If we want to represent arbitrarily large integers, then we could use an array where each element in the array represents a digit in the number. In fact, we could use strings for this purpose, and have the characters in the string represent the digits. We could then define special functions to perform arithmetic. As an example, consider the following code:1
2
3
4char value[MAX_ARRAY_SIZE] = "2147483647";
char output[MAX_ARRAY_SIZE];
AddOne(value, output);
printf("%s + 1 = %s", value, output);
In this case, we use the string “2147483647” to represent a large integer value. The AddOne() function is then used to compute a new string where the characters represent the integer that is one larger than the original. The output from the code above is:
2147483647 + 1 = 2147483648
This apparently solves the integer overflow problem! However, there are some downsides arithmetic performed in this way is much slower than using the int type.
We can now perform this basic arithmetic on really large numbers:1
2
3
4char value[MAX_ARRAY_SIZE] = "123456789123456789123456789";
char output[MAX_ARRAY_SIZE];
AddOne(value, output);
printf("%s + 1 = %s", value, output);
and the output is:
123456789123456789123456789 + 1 = 123456789123456789123456790
For this task, you should define the AddOne() function.
The AddOne() function takes two inputs: the first is a string (i.e. an array of characters) which represents an arbitrarily large number. The second is also a string into which you should store the output of the function. The output is a string which represents the number one larger than the input number.
Function prototype declaration
1 | void AddOne(char *input, char *output) |
Assumptions
You can assume that the input string represents a valid positive integer (greater than or equal to 1).
You cannot assume that the length of the output string will equal the length of the input string - for example, this will clearly not be the case if all of the characters in the input string are equal to ‘9’.
Example
1 | AddOne("12345", output); |
Expected output
Result = 12346
Result = 10000000000000
Result = 2000000000000
Task Nine: “Textual histogram”
Let’s say that we have the following 6 data values representing frequencies of some measurement:
3, 1, 2, 0, 4, 1
and we now would like to plot these on a histogram. We could do this easily using many graphical plotting programs such as Excel:
We could also represent the same data using a textual representation, where the bars are represented by “X” characters:
X
X X
X X X
XXX XX
And to make this look a little nicer, we could surround the bars with a border of ‘*’ characters:
********
* X *
* X *
*X X *
*X X X *
*X X X *
*XXX XX*
********
Define a function called Histogram() that takes an array of integers representing the data to be plotted, and generates a string (representing the histogram) in precisely the format described above. Please take note of the following:
- each line of text in the string ends with a new line (‘\n’) except for the very last line
- there must be no extra space characters anywhere at the beginning or end of a line
The Histogram() function should take three input values. The second and third input values represent the data to be plotted. This is stored as an array of integers, and the number of elements in the array. The first input to the function is the string into which you should store the resulting histogram.
Function prototype declaration
1 | void Histogram(char *result, int *values, int numValues); |
Assumptions
You can assume the input array will consist of at least one value greater than 0.
Example
1 | int values1[10] = {1, 0, 3, 1, 2, 4, 5, 6, 2, 2}; |
Expected output
************
* X *
* XX *
* XXX *
* X XXX *
* X XXXXXX*
*X XXXXXXXX*
************
*****
*X X*
*****
This matches EXACTLY and is correct
Task Ten: “Gold Rush!”
The year is 1849 and you have just arrived in California to make your fortune in the gold rush. You have your pick axe, your kerosene lamp, a box of dynamite and your laptop. You need to stake your claim over the land that contains the largest gold deposits. You have access to a number of prospecting maps (which are grid based) which contain information about the quality of the gold deposits in the land. Fortunately, this data is digitized so you can easily read it into your program as a 2dimensional array.
The values (which are digits between 0 and 9) in each cell of the map represent the type of minerals present in the corresponding locations. The value 0 indicates that there are no deposits of any value at the location, and values between 1 and 8 indicate various kinds of common minerals which are of little interest to you. The value you are interested in is the value 9 as this represents the presence of gold! To help you quickly determine which maps are most promising, you want to write a program to compute how much gold (i.e. cells with a value of 9) is present in a given map.
You also want to compute one other value - that is, how much pure gold is present in the map. A cell contains pure gold if it contains gold and if all eight of the cells directly adjacent to it (in any direction: up, down, left, right or any diagonal) also contain gold. By this definition, cells on the border of the map cannot contain pure gold.
The 15 x 15 map shown above contains 4 separate regions of gold (which are not connected to each other). The table below illustrates these four regions. In the column labelled “Prospecting map”, the map is shown and cells containing gold are highlighted in bold. Cells containing pure gold are also underlined. In the column labelled “Region”, the four non-connected regions are shown on separate rows. The column labelled “Gold” shows how much gold is contained in the region and the column labelled “Pure gold” shows the amount of pure gold
Define a function called GoldRush() that takes five inputs:
- A one-dimensional array of integers, called results, into which you will store the results computed by your function
- An integer, called rows, which indicates how many rows are present in the map
- An integer, called cols, which indicates how many columns are present in the map
- A two-dimensional array of integers, called map, which contains the map data
- An integer called bonus which is only used if you have attempted the bonus tasks described later (for this task, this input will always have the value 0)
This function should compute the total amount of gold in the map, and the total amount of pure gold in the map. Using the example map shown above, the total amount of gold is 39 and the total amount of pure gold is 3.
The function is void (i.e. it does not return a value). To return the results that you have computed, you should use the results array (the first input to the function). You should store the total amount of gold in results[0] and the amount of pure gold in results[1].
Function prototype declaration
1 | void GoldRush(int *results, int rows, int cols, int map[MAX_MAP_SIZE][MAX_MAP_SIZE], int bonus); |
Assumptions
You can assume the map will have at least two rows and two columns, and will have no more than MAX_MAP_SIZE rows and MAX_MAP_SIZE columns
Example
1 | int i, j; |
Expected output
Searching for gold!
Total gold = 39
Pure gold = 3
Bonus Task I: “Gold regions”
The last input to the GoldRush() function is an integer called bonus. For Task Ten, described above, this input will always be 0. For the first bonus task, the value of this input will be set to 1.
For the first bonus task, you should count the total amount of gold present in each non-connected region of gold on the map. You should report your results by storing them in the results array, in decreasing order (so the largest region of gold is reported first). Once you have stored the results for each region, in consecutive elements of the array, you must then store the value 0 in the next element of the array to indicate there are no more results.
Example
1 | int i, j; |
Expected output
Searching for gold!
Total gold regions = 21 9 6 3
Bonus Task II: “Pure gold”
The last input to the GoldRush() function is an integer called bonus. For the second bonus task, the value of this input will be set to 2.
For the second bonus task, you should count the total amount of pure gold present in each nonconnected region of gold on the map. You should report your results by storing them in the results array, in decreasing order (so the largest region of pure gold is reported first). Once you have stored the results for each region, in consecutive elements of the array, you must then store the value 0 in the next element of the array to indicate there are no more results.
Example
1 | int i, j; |
Expected output
Searching for gold!
Total pure gold regions = 2 1