Homework #3¶

Due Date: Monday, April 25th at 9pm.

The following homework exercises are intended to help you practice some of the programming concepts introduced in weeks 3 and 4, including arrays, heap allocation, strings, and structs.

Getting Started¶

You will be using a new repository for each homework in this course. Please follow the instructions in the Ed post “Homework #3 now available” to set up your Homework #3 repo.

Compiling and testing your code¶

We will continue to use the testing infrastructure that you are now accustomed to. For a refresher, please read through the “Compiling and testing your code” section of Homework #1. To run the Homework #3 tests, you will need to replace homework1 with homework3 as needed.

You also might want to run your code with LLDB and Valgrind to aid in debugging. Please see the “Debugging with LLDB and Valgrind” section below for instructions on how to run your code with these tools.

Exercises¶

Throughout this assignment, you may assume that pointer parameters point to valid data and are not NULL. You can also assume that the value of the length of an array passed as parameter to a function is indeed the length of that array. You can use function sfrom stdlib.h, like malloc, calloc, and free as needed throughout this assignment. You should not use functions from other libraries unless it is explicitly stated that you can do so in a task.

In the first group of exercises, you will implement an interface for a struct that describes a color. A color on a computer is specified by three values between zero and 255 (inclusive) for the red component, green component, and blue component of the color. The red, green, and blue values together are usually referred to as an RGB triple. We will implement a color using the struct:

typedef struct color color_t;

struct color {
    uint8_t red;
    uint8_t green;
    uint8_t blue;
    char *name;
};

A color_t stores red, green, and blue color values as uint8_t (unsigned 8-bit integers) and the color’s name as a string. You will start by implementing a color_t interface, then write some functions that utilize colors.

Complete the function new_color which takes three uint8_t values (the red, green, and blue color values) and a string containing a color’s name, and creates a new heap-allocated color. This function should create a heap-allocated copy of the color’s name. A function that creates a new struct is often called a constructor. You may use the string.h function strdup in your implementation.
Complete the function free_color which takes a pointer to a color_t and frees the color, as well as the heap-allocated fields of the color. You can assume that the color was created using the new_color function.
Complete the function copy_color which takes a pointer to a color_t and returns a heap-allocated copy of the color with a heap-allocated copy of the color’s name.
Complete the function luminance which takes a pointer to a color_t and computes the “luminance”, or brightness, of the color. Luminance is computed using the formula: 0.2126*R + 0.7152*G + 0.0722*B where R is the red value of the color, G is the green value of the color, and B is the blue value of the color.
Complete the function grayscale which takes a pointer to a color_t and creates the grayscale version of the color. There are many ways to average an RGB triple, but one common way is to use the formula: (77*R + 150*G + 29*B)/256. For example, the grayscale of the RGB triple (185, 145, 0) is (140, 140, 140). Notice that each RGB component has the same value in a grayscale color.

The grayscale color should be heap-allocated and have the heap-allocated name "gray".
Complete the function

color_t **make_stripe(color_t *c, int stripe_len)

which takes a pointer to a color_t and an integer, and creates an array of pointers to color_t of length stripe_len of the color c. Each element of the array should point to a unique heap-allocated color_t.
Complete the function

void free_stripe(color_t **stripe, int stripe_len)

which takes a heap-allocated array of pointers to heap-allocated color_t and the length of the array, and frees the array and all memory associated with it. You can assume that stripe was created using your make_stripe function.
In this exercise, you will perform an operation called “bitpacking”, which “packs” multiple values into a single number. In this case, you will pack and RGB triple, stored as three uint8_t values, into a uint32_t (an unsigned 32-bit integer). We could store three uint8_t values in 24 bits, but there is no three-byte integer type in C.

You will pack the RGB values as 0 R G B. Each RGB value consumes one byte of the four-byte integer and the highest-order byte is zero. Note that the spaces printed here are purely for readability and should not be implemented in your code.

For example, consider the RGB triple (255, 128, 4). This would be packed into 32 bits like so:

00000000 11111111 10000000 00000100

The equivalent in hex (which is easier to read) is:

00 FF 80 04

Complete the function

uint32_t pack_color(color_t *c)

which takes a pointer to a color_t and returns the “packed” version of that color as a uint32_t.

Restriction: You may not use the arithmetic operators (+, -, /, *, %) for this problem. Your implementation should use the bitwise operators (<<, >>, &, |). Logical operators like ! are okay to use.
Complete the function

color_t **unpack_colors(uint32_t *packed_colors, char **names, int num_colors)

which takes an array of packed colors, a corresponding array of color names, and the number of colors, and returns a heap-allocated array of pointers to heap-allocated color_t, each representing a packed color with its corresponding name. A helper function could be useful to decompose this exercise into smaller tasks.

Note: Our tests make use of your functions new_color, free_color, and free_stripe to create colors and free the memory created when testing your functions copy_color, grayscale, make_stripe, and so on. If the tests crash or are incorrect for a given function, and you are relatively sure that function is correct (perhaps you have debugged it thoroughly via student_test_homework.c), check to make sure that one of new_color, free_color, and free_stripe is not the culprit.

In the next group of exercises, you will make use of the following typedef and struct:

typedef struct ingredient ingredient_t;

struct ingredient {
    char *food_name;
    double amount;
};

An ingredient_t represents a food with a name (a string) and an amount (a double). For our purposes, all food will be measured in the same unit, like grams. For example, a recipe for peanut butter cookies might call for 200 grams of sugar, or you might have a 320 gram jar of honey in your pantry.

Complete the function shopping_list_amounts which takes the following parameters:
- ingredient_t *pantry: An array of ingredients in your pantry
- int pantry_len: The length of the pantry array
- ingredient_t *recipe: An array of ingredients in a recipe
- int recipe_len: The length of the recipe array
This function should return an array of doubles that represents the amount of each ingredient in the recipe that is needed to cook the recipe, given the ingredients in the pantry. More precisely, element i of the ouput array is the number of units of ingredient i in the recipe array needed to cook the recipe.

For example, consider this simple recipe to make peanut butter cookies:
- 250 grams of peanut butter
- 200 grams of sugar
- 50 grams of egg
And say your pantry contains:
- 80 grams of sugar
- 320 grams of honey
- 100 grams of egg
- 150 grams of flour
Then shopping_list_amounts should return the array {250, 120, 0}, since, to make the recipe from the pantry, you would need to shop for 250 grams of peanut butter, 120 grams of sugar, and 0 grams of egg (since there is enough in the pantry already). The output array has three elements, one for each ingredient in the input recipe.

Note that there can be ingredients in the pantry that aren’t in the recipe, and ingredients in the recipe that aren’t in the pantry. You should not assume anything about the order of the ingredients in the pantry or the recipe. You can assume that there is at least one ingredient in the recipe, but you should not assume that there are any ingredients in the pantry. You may use the string.h function strcmp in your implementation.

Also note that the input arrays are arrays of structs, not arrays of pointers to structs.
Complete the function shopping_list which takes the following parameters:
- ingredient_t *pantry: An array of ingredients in your pantry
- int pantry_len: The length of the pantry array
- ingredient_t *recipe: An array of ingredients in a recipe
- int recipe_len: The length of the recipe array
- shopping_list_len: An out parameter
This function should return an array of ingredient_t that represents the ingredients needed to cook the recipe, given the ingredients in the pantry. It should also return the length of the output in the out parameter shopping_list_len.

Using the peanut butter cookie recipe and pantry above as input, shopping_list should return the array with ingredients representing:
- 250 grams of peanut butter
- 120 grams of sugar
There is no need to shop for egg, since the pantry has enough of that ingredient already. Furthermore, shopping_list_len should point to the value 2, since you would need to shop for 2 ingredients in order to cook the recipe.

For this problem, you can make use the ingredient_t constructor new_ingredient, which is implemented in homework3.c. You can also use your shopping_list_amounts function from before to simplify your implemenation and avoid repeating code.

Again, note that the input and output arrays are arrays of structs, not arrays of pointers to structs.

Debugging with LLDB and Valgrind¶

You can use the student_test_homework3.c file to run your code with LLDB and Valgrind. For example, you may want to create a few variables of type color_t and free them using your new_color and free_color functions, then run your code with Valgrind to check that you are indeed freeing all heap-allocated memory.

Use these commands in the terminal to run your code with Valgrind:

$ make student_test_homework3

$ valgrind ./student_test_homework3

And these to launch an LLDB debugging session:

$ make student_test_homework3

$ lldb student_test_homework3

Please note that running the test suite test_homework3.c with Valgrind will not give you the results you want. Valgrind does play well with Criterion, the testing framework we use. Please use student_test_homework3.c instead.

Grading¶

For this assignment, the weights will be:

Completeness: 60%
Code Quality: 40%

The code quality score will be determined by code clarity, style, and whether your implementation stays within the allowed constructs for each exercise.

Preparing your submission¶

There are three things you should do before you submit your work.

First, make sure you have added the required information to the header comment in homework3.c:

your name,
the names of anyone beyond the course staff you discussed the assignment with, and
links to any resources that you used other than course materials and the course textbook.

Please remove the explanation for what is required. Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

Second, remove directives, such as:

// YOUR CODE HERE
// Replace 0.0 with an appropriate return value

from your code. Make sure to recompile and rerun the tests after you make these changes. It is easy to introduce a syntax error at this stage.

Third, add, commit, and push your work to GitHub.

And finally, get your directory into a clean state. Run make clean to remove any executables that are laying around.

Submission¶

To submit your work, you will need to add, commit, and push your code to GitHub. Before you upload your code to GitHub, run git status . to make sure you did not forget to add/commit any of the required files. Then upload your submission to Gradescope under the “Homework #3” assignment. Make sure to choose the right assignment on Gradescope!

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.