Week 05 Laboratory Exercises

Objectives

  • creating functions
  • manipulating 2D arrays
  • introduction to pointers

Activities To Be Completed

The following is a list of all the activities available to complete this week...

Worth one mark in total:

  • swap_pointers
  • array_sum_prod

Worth half a mark in total:

  • common_elements
  • advanced_addition

Worth half a mark in total:

  • remove_duplicates_function
  • largest_z_sum

For your interest, but not for marks:

  • p1511

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Exercise
(●◌◌)
:

Using pointers and a function to swap number values

Download swap_pointers.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/swap_pointers/swap_pointers.c .

Your task is to add code to this function in swap_pointers.c:

// swap the values in two integers, given as pointers
void swap_pointers(int *a, int *b) {
    // PUT YOUR CODE HERE (you must change the next line!)
}
swap_pointers should take two pointers to integers as input and swap the values stored in those two integers.

For example if the integers are:

int first = 1;
int second = 2;

After your function runs, first should be 2 and second should be 1.

Assumptions/Restrictions/Clarifications.

swap_pointers is a void function. It cannot return any values.

swap_pointers should not call scanf (or getchar or fgets).

swap_pointers should not print anything. It should not call printf.

Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style swap_pointers.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest swap_pointers

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_swap_pointers swap_pointers.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(●◌◌)
:

Calculate both the sum and product of the values in an array

Download array_sum_prod.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/array_sum_prod/array_sum_prod.c .

Your task is to add code to this function in array_sum_prod.c:

// Calculates the sum and product of the array nums.
// Actually modifies the  variables that *sum and *product are pointing to
void array_sum_prod(int length, int nums[length], int *sum, int *product) {
    // TODO: Complete this function
}

The above file array_sum_prod.c contains a function array_sum_prod, which should find the sum and the product of the values stored in the array. It should write these values into the integers referenced by the pointers in the input to the function.

Unfortunately, the provided function doesn't actually work. For this lab exercise, your task is to complete this function.

Note: you must not modify the array within the array_sum_prod function. You should only read the values in the array, not change them.

Note: you will not be given an empty array as input, you can assume that you have at least 1 value.

The file also contains a main function which you can use to help test your array_sum_prod function. It has two simple test cases.

This main function will not be marked -- you must write all of your code in the array_sum_prod function. You may modify the main function if you wish (e.g. to add further tests), but only the array_sum_prod function will be marked.

Once your program is working, the output from the two provided tests in the main function should be:

dcc -o array_sum_prod array_sum_prod.c 
./array_sum_prod 
Sum: 20, Product: 360
Sum: 10, Product: 24
You can run an automated code style checker using the following command:
1511 style array_sum_prod.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest array_sum_prod

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_array_sum_prod array_sum_prod.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Find any elements that are the same in two arrays and make a new array with them

Download common_elements.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/common_elements/common_elements.c .

Your task is to add code to this function in common_elements.c:

int common_elements(int length, int source1[length], int source2[length], int destination[length]) {
    // PUT YOUR CODE HERE (you must change the next line!)
    return 42;
}
common_elements should copy the values in the first source array which are also found in the second source array, into the third array.

In other words, all of the elements that appear in both of the source1 and source2 should be copied to the third destination array, in the order that they appear in the first array. common_elements should return a single integer: the number of elements copied to the destination array.

For example, if the source arrays contained the following 6 elements:

source1: 1, 4, 1, 5, 9, 2

source2: 1, 1, 8, 2, 5, 3

common_elements should copy these 4 values to the destination array: 1, 1, 5, 2

The value 4 and 9 do not get copied because they do not occur in the second array.

common_elements should return the integer 4, because there were 4 values copied.

common_elements should copy the elements in the order that they appear in the first array.

If a value in the first array occurs one or more times in the second array, each occurrence of those values in the first array should be copied.

It doesn't matter how many times the values occur in the second array, as long as the values occur at least once. For example. if the two arrays contained the following 5 elements:

source1: 1, 2, 3, 2, 1

source2: 1, 2, 3, 4, 5

Your function should copy all five values (1, 2, 3, 2, 1) from source1 to the destination array {} as all of the values (1, 2, 3) appeared at least once in source2 and it should return 5 because because 5 values were copied.

Assumptions/Restrictions/Clarifications.

You can assume the two source arrays contain only positive integers.

You can assume that all three arrays are the same size (length) and length is > 0.

You cannot assume anything about the number of common elements, i.e. there may not be any common elements between both arrays, or conversely, the entire contents of the first array may also be present in the second array.

common_elements should return a single integer.

common_elements should not change the array it is given.

common_elements should not call scanf (or getchar or fgets).

common_elements should not print anything. It should not call printf.

Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style common_elements.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest common_elements

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_common_elements common_elements.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Add numbers in an array together, carrying numbers where neccesary.

Download advanced_addition.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/advanced_addition/advanced_addition.c .

Your task is to add code to this function in advanced_addition.c:

// Put the sum of the lines in the array into the last line
// accounting for carrying. Return anything you did not carry.
//
// NOTE: num_lines is the number of lines you are adding together. The
// array has an extra line for you to put the result.
int sum(int num_lines, int num_digits, int array[MAX_SIZE][MAX_SIZE]) {
    // Put your code here.
    return 0;
}

You will implement the sum function, which will be given a two-dimensional array with a variable number of rows ("lines") and columns ("digits"), like the following:

0 1 2 3 4
0 4 3 2 4
0 0 1 1 1
0 0 0 0 0

When you receive this array, you are guaranteed the last row will be all zeroes. You should write the sum of every column into the last number in that column.

As an example, your function should modify the above array to be the following:

0 1 2 3 4
0 4 3 2 4
0 0 1 1 1
0 5 6 6 9

For each column, starting from the right-most digit, you should add every digit in that column, and put the result of that addition into the last row.

To simulate real addition, however, none of the values in the array may exceed 9, so you will need to implement "carrying", just like in normal addition. "Carrying" is when all the numbers in a column sum to greater than 9, and you add extra to the next column to keep the current column below 10. For example, the following array:

0 9
0 8
0 7
0 0

Should become:

0 9
0 8
0 7
2 4

The sum function will normally return 0. If, however, your addition cannot be represented in the array because the last column you add still carries something over, your function should return the amount carried:

9
8
7
0

Should return 2, and make the array:

9
8
7
4
    

More formally, you should:

  1. Start at the rightmost column of the array.
  2. Add together the integers in that column, as well as anything "carried across".
  3. If the result of that addition would be less than ten, write the result of that addition into the last number in that row. Nothing is carried across.
  4. Otherwise, find the result of the addition modulo 10, and write that into the last value in the column.
  5. Then, divide the result of the addition by 10, and "carry that accross" to the next column.
  6. Repeat on the next column to the next, from step two.
  7. If you reach the leftmost column of the array, and there is still a value "carried across", return it. Otherwise, return zero.

The file advanced_addition.c contains a main function which reads values into a 2D array and calls sum.

Here is how advanced_addition.c should behave after you add the correct code to the function add:

dcc advanced_addition.c -o advanced_addition
./advanced_addition
Enter the number of rows (excluding the last): 3
Enter the number of digits on each row: 3
Enter 2D array values:
1 2 3
4 5 6
0 1 0
5 8 9

./advanced_addition
Enter the number of rows (excluding the last): 4
Enter the number of digits on each row: 2
Enter 2D array values:
1 3
1 3
1 3
1 3
5 2
./advanced_addition
Enter the number of rows (excluding the last): 2
Enter the number of digits on each row: 1
Enter 2D array values:
9
9
8
Carried over: 1
You can run an automated code style checker using the following command:
1511 style advanced_addition.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest advanced_addition

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_advanced_addition advanced_addition.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Remove any duplicate values from an array and write the result into another array

Write a C function that removes duplicate elements from an array, by copying the non-duplicate values to a second array, i.e. only the first occurrence of any value should be copied.

Place your answer in a file named remove_duplicates_function.c

Your function should take three parameters: the length of source array, the source array itself, and the destination array. It must have this prototype:


int remove_duplicates(int length, int source[length], int destination[length]);
Your function should return a single integer: the number of elements copied to the destination array.

For example if the source array contains these 6 elements:

3, 1, 4, 1, 5, 9

Your function should copy these 5 values to the destination array:

3, 1, 4, 5, 9

Your function should return the integer 5, because there were 5 values copied -- the second occurrence of the digit 1 was not copied.

Assumptions/Restrictions/Clarifications.

You can assume the source array only contains positive integers.

You can assume the source array contains at least one integer.

You can assume that the destination array will always be large enough to fit all of the copied values.

You cannot assume anything about the number of duplicates, i.e. there may not be any duplicates, or conversely, the entire array may be duplicates.

Your function should return a single integer.

Your function should not change the array it is given.

Your function should not call scanf (or getchar or fgets).

Your function should not print anything. It should not call printf.

Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style remove_duplicates_function.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest remove_duplicates_function

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_remove_duplicates_function remove_duplicates_function.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Find the Largest Sum of Numbers in a z Shape

Download largest_z_sum.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/largest_z_sum/largest_z_sum.c .

Your task is to add code to this function in largest_z_sum.c:

// Return the largest sum of numbers in a z shape.
int largest_z_sum(int size, int array[MAX_SIZE][MAX_SIZE]) {
    // Put your code here.
    return 42;
}

You are to implement the largest_z_sum function which should return the sum of values forming the shape of a z character in a square 2D array.

A z shape is made up of three lines of equal length. Two of these lines are horizontal and one is diagonal. The length of the three lines must be equal but can range from 3 up to the size of the array. Only correctly oriented z shapes are valid - z shapes with a northwest/southeast diagonal are not valid.

The 2D square array may contain any positive or negative integers.

You can assume that the side length of the 2D square array will always be greater than or equal to 3.

You can assume that the side length of the 2D array will never be greater than 100.

The file largest_z_sum.c contains a main function which reads values into a square 2D array and calls largest_z_sum.

Here is how largest_z_sum.c should behave after you add the correct code to the function largest_z_sum:

dcc largest_z_sum.c -o largest_z_sum
./largest_z_sum
Enter 2D array side length: 5
Enter 2D array values:
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
The largest z sum is 169.
./largest_z_sum
Enter 2D array side length: 5
Enter 2D array values:
 28 -47 -40  29  49
 26 -42 -37  48  1
-36  50  41 -24 -33
 41  25 -39  39  48
 14 -26 -46 -3  -29
The largest z sum is 153.
./largest_z_sum
Enter 2D array side length: 3
Enter 2D array values:
1 1 1
1 1 1
1 1 1
The largest z sum is 7.

Note: In the first example, the z of size 5 starting from (0, 0) is used to form the largest sum of:
1 + 2 + 3 + 4 + 5 + 9 + 13 + 17 + 21 + 22 + 23 + 24 + 25 = 169
In the second example, the z of size 4 starting from (0, 1) is used to form the largest sum of:
-47 - 40 + 29 + 49 + 48 + 41 + 25 - 39 + 39 + 48 = 153
In the third example, there is only one possible z sum of size 3.

You can run an automated code style checker using the following command:
1511 style largest_z_sum.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest largest_z_sum

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab05_largest_z_sum largest_z_sum.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 25 October 20:00 to obtain the marks for this lab exercise.

Exercise
(☠)
:

Implement p1511, a new programming language.

So far in this course, you have been learning the C language.

While C is a very famous and popular language, thousands (perhaps tens of thousands) of programming languages exist. Some are very popular, though others are designed as a joke or a game. Joke languages like this are often called "eso-langs" or "esoteric languages".

Some more famous examples of eso-langs include:

In this challenge, we ask you to implement a dialect of P'' called P1511.

There are only three concepts you need to know:

  • Commands: A P1511 program is an array of characters. Each character represents a command. After running a command, you run the next one (unless the command says otherwise).
  • Your Memory: This is an array of integers, which is 0 initialized. The array can be as big as you like (we recommend 20 for debugging purposes). Each value in the array is called a "cell"
  • The Cell-Pointer One cell is always "selected". Many commands in P1511 act on the selected cell. To keep track of which cell is selected, we have the "cell pointer".

You should assume the list of commands is no longer than 10000.

An instruction can be one of the following commands:

Code Description
> Move the cell-pointer right. If you are at the last cell, loop back around to the first one.
< Move the cell-pointer left. If you are at the first cell, loop back around to the last one.
+ Add one to the current value of the cell-pointer.
- Subtract one from the current value of the cell-pointer.
. Print out the value of the cell-pointer as an ascii character.
, Replace the cell-pointer's value with a scanned in number (i.e. scanf a number, and set the cell-pointer to be equal to it).
any lowercase letter If the value of the cell-pointer is 0, jump through your commands to the uppercase version of this letter.
any uppercase letter If the value of the cell-pointer is not 0, jump through your commands to the lowercase version of this letter
! End the program :)

With this simple language, you can write almost any program!

To complete this challenge, you should write a program which simulates P1511.

Examples

Here is a simple P1511 program:


  char commands[10000] = {
    '>', '+', '+', '+', '+', '+', '+', '+', '+',
      'a', '<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '>', '-', 'A',
    '<', '.', '+', '.', '!'
  };

This program prints out "HI". To see the logic of this program, run 1511 p1511, which will walk you through, step by step.

Write your own P1511 programs

If you manage to write a program in P1511, post it on the forums at this link.

Try writing a program to print out a word, or (challenge) to add two numbers together!

You can run an automated code style checker using the following command:
1511 style p1511.c

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 7 Monday 20:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1511 classrun -sturec