Exercise 12
Info

This is an in-class exercise. An exercise page like this one will contain a brief description but is intended to be supplemented by discussion during our meeting time. Complete the exercise to the best of your ability in the time given. Feel free to talk with other students as you work, and do not be afraid to ask questions if you get stuck. Aim to complete as much as possible during our meeting, and submit on Gradescope to check your solution. You are encouraged to work at home to complete what you do not get through today, and ask questions on Piazza or in office hours.

Learning Objectives

Reinforces concepts learned in today's meeting:

  • Use pointer arithmetic to access array elements
  • Use pointer arithmetic to treat regions of a larger array as "sub-arrays"
  • Use pointer differences to compute indices of array elements based on their displacement from the base address
  • Use pointers to access subsets of a 2D array as 1D arrays

Part 1

Pull the starter code for this exercise from the public repo by taking the following steps:

  1. Log into an undergraduate cluster computer. Update the course public repo with a git pull command.

  2. Confirm that you can access the template files for today’s exercise by typing ls exercises/ex12 – you should see files named bsearch.c and sudoku.c, as well as 3 plain text input puzzle files puzzle*.txt. There should also be files sudokuHelpers.h, sudokuHelpers.c, and a Makefile for easy compilation and updating of the sudoku code.

  3. Navigate to your personal repo for the course and make a directory for today’s exercise. Then copy all the files from the public class repository (in the */exercises/ex12/* directory) and put it in your personal repo’s directory for today’s exercise.

Part 3

Open bsearch.c with a text editor. To compile the code, use this command:

gcc -std=c99 -pedantic -Wall -Wextra bsearch.c -g -o bsearch

or use our alias:

gccc bsearch.c -g -o bsearch

You will need to modify bsearch.c as follows.

First, add a declaration and definition for a function called search. The declaration should look like this:

int *search(int *start, int *end, int search_val);

TODO comments indicate where to add the declaration and definition.

This function implements a binary search to find an integer value search_val in a region of a sorted array of int values. The start and end parameters specify a range of elements to search, where start is a pointer to the inclusive start element, and end is a pointer to the exclusive end element. I.e., the pointers to the elements in the range to be searched are greater than or equal to start, and strictly less than end.

If the search is successful, the search function should return a pointer to the element where search_val was located. If the search is unsuccessful, the search function should return NULL.

Recall that you implemented binary search in Exercise 7. Note that in today’s exercise, you are not required to implement the binary search using recursion. Either recursion or iteration is fine. However, keep in mind that for Ex 7 both of the range indices low and high were inclusive.

Next, after you have implemented the search function, you should complete the code in the main function. You will see a block of code that looks like this:

// example of a successful search
pos = search(arr1, arr1 + 10, 809);
assert(pos != NULL);
assert(*pos == 809);
index = // TODO: compute the index of the matching element
assert(7 == index);

Fix the code at the point of the TODO comment so that it computes the index of the array element that pos points to, where pos is the result of a successful search. Hint: this will involve a pointer difference computation.

Once you’ve completed the main function, you should be able to run the program. If the tests pass, you will see the output:

All tests pass!

To finish this part of the exercise, add additional test cases to test the search function. You should add at least three test cases for successful searches and three test cases for unsuccessful searches. Make sure that all of your tests pass.

Part 4

For the next part of this exercise, you’ll be finishing the implementation of a sudoku checker program. The purpose of the program is to read an input puzzle file, where 0s represent empty cells. It should then check every row, column and cube to see if the puzzle is completely solved already, or not. You will only need to modify the sudokuHelper.c file, but should take time first to read through the code in the other files and ask if you have any questions.

There are several helper functions you need to complete, as indicated by TODO comments in the file. In both makeCol and makeCube you need to declare the unit array that will be populated and returned in each function. (Their declarations will be identical.) You should also carefully read through the provided code in each method to ask if you don’t understand how they work.

Next you’ll need to call these functions from two other helpers, again where indicated by TODO comments in functions checkRows, checkCols and checkCubes. Once this is done correctly, you should be able to compile everything with the Makefile and run the main program with each puzzle file as input. The first two are not correct/complete solutions, but puzzle3.txt is a completely solved puzzle.

Part 5

Lastly, using the tools you learned in Ex 11 during the last class session, modify the Makefile, adding the -g option to your compilation command(s) so that you can run gdb and valgrind on this code. Find a fix the memory leaks in sudokuHelpers.c for this final task.

Reminder

Remember to add and commit to your local repo copy as your work. Push to your remote repo when finished. Also scp and submit to Gradescope to check your solution. Use exit to logout from your ugrad account when finished. If you continue to work on the program after class, make sure to keep your repo updated as well!