COMP1511 17s1 Introduction to Programming
    The tutorial will start with a code review.

    Your tutor has asked a lab pair to present their week 6 work.

    Discuss the good, the bad and the ugly aspects of their code.

    Please be gentle in any criticism - we are all learning!

  1. Did you blog last week? What is this week's blogging theme?
    See the class home page.
  2. Discuss the assignment including:
    • what is a CAPTCHA and what they are used for
    • what exactly are the inputs and output of crack_digit and crack_captcha
    • what is a PBM file
    • what do you have to do get a PS (50%) CR (65%), DN (75%) & HD (85%) on the assignment
  3. A paranoid student wants to check that read_pbm is only giving them black & white pixels, in other words all elements of the array pixels contain either 1 or 0. Write a function to check this with this prototype:

    int is_monochrome(int height, int width, int pixels[height][width]);
    

    Your function should return 1 to indicate all elements of the array are 1 or 0. It should return 0 otherwise.

    // return 1 iff image array contains only 1s and 0s, 0 otherwise
    int is_monochrome(int height, int width, int pixels[height][width]) {
        int column, row;
    
        row = 0;
        while (row < height) {
            column = 0;
            while (column < width) {
                if (pixels[column][row] != 1 && pixels[column][row] != 0) {
                    return 0;
                }
                column = column + 1;
            }
            row = row + 1;
        }
        return 1;
    }
    
  4. A student working on assignment 1 wrote code like this:
        density = pixel_count / (height * width);
    
    to calculate an attribute suggested in the assignment spec. When they test their code they find that density is always 0.

    They are mystified becaused they are calculating pixel_count, height and width correctly. What is happening?

    pixel_count, height and width are probably int variables. Even if density is a double variable, the division of 2 ints will be truncated to an integer.

    Here is one way to avoid the problem.

        density = pixelCount / (double)(height * width);
    
  5. What is the end-of-file (EOF) character in C?
    There is no end-of-file character in C.

    Modern operating systems do not use a character to mark the end of files. They track the length of files separately.

    C library functions such as getchar return a special value (EOF) when no input is available.

    A special key sequence can be used in Unix-like terminals, typically cntrl-d to indicate no more input is available. This is a signal to the operating system and is not passed to the program as a character.

  6. When do you have a use a for loop?
    You never have to use a for loop.

    Any for loop can be re-written as a while loop.

    When are for loops preferable?

    You can always use a while loop if you prefer in COMP1511, but experienced C programmers will use a for loop for simple iterations - because its more concise and easier (for experienced programmers) to read.

    For example, instead of this while loop:

       i = 0;
       while (i < N) {
           // ....
           i = i + 1;
       }
    
    Most experienced programmers would instead write this for loop:
    
       for (i = 0; i < N; i = i + 1 ) {
           // ....
       }
    
  7. Name 3 errors in this program:
    #include <stdio.h>
    
    #define MAX_LINE 4096
    
    int main(void) {
        char line[MAX_LINE];
        int  i;
    
        while (fgets(line, MAX_LINE, stdin) != NULL) {
            i = MAX_LINE;
            while (line[i] != '\n') {
                i = i - 1;
            }
            printf("line %d characters long\n", i);
        }
        return 0;
    }
    
    1. On the first execution of the inner while loop it accesses line[MAX_LINE] which is an illegal array index
    2. It accesses uninitialized array elements - fgets only assigns to the array elements necessary to hold the characters of a line plus a '\0'
    3. There may not be a '\n' in the array. fgets won't put a '\n' in the array if the line is too long to fit in the array. If there is no '\n' in the array the code will access an non-existent array element (line[-1]).
  8. Write a program line_length.c which reads lines from its input and prints how many characters each line contains.

    The only functions you can use are fgets and printf.

    You can assume lines contain at most 4096 characters.

    For example:

    ./line_length
    Andrew Rocks
    line 12 characters long
    A very long line.
    line 17 characters long
    short
    line 5 characters long
    
    line 0 characters long
    
    Sample solution for line_length.c
    #include <stdio.h>
    
    #define MAX_LINE 4096
    
    int
    main(void) {
        char line[MAX_LINE];
        int  i;
    
        while (fgets(line, MAX_LINE, stdin) != NULL) {
            i = 0;
            while (line[i] != '\n' && line[i] != '\0') {
                i = i + 1;
            }
            printf("line %d characters long\n", i);
        }
        return 0;
    }
    
    
    Heavily commented sample solution.
    // reads lines from its input
    // and prints how many characters each line contains
    // only use fgets and printf
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 4096	// max number of characters in a line
    
    int main (int argc, char* argv[]) {
    
    	int numC;			// counter for number of characters in line
    	char line[MAX];	// array to store the input
    
    	// keep on reading until EOF or error
    	while (fgets(line, MAX, stdin) != NULL) {
    		// count the number of characters
    		numC = 0;
    		// each elt in the array line is a character (alphanumeric or whitespace)
    		// unless the elt. is a newline or null terminating character
    		// in which case the line has stopped
    		// so numC is also the index for your line array
    		while (line[numC] != '\n' && line[numC] != '\0') {
    			// this is a character
    			numC++;	// now go test the next one
    		}
    
    		// print your result
    		printf("line %d characters long\n", numC);
    
    	}
    
    
    	return EXIT_SUCCESS;
    }
    
  9. Write a program strip_comments.c which reads lines from its input and prints them after removing any C // style comments. In another words if the line contains // it does not print the // or anything after it.

    The only functions you can use are fgets and printf.

    You can assume lines contain at most 4096 characters.

    For example:

    ./strip_comments
         x = x + 1;  // This means add one to the variable x
         x = x + 1;
    
    Also - is that a good comment to add to a C program?

    What if the input contains printf("//");?

    Sample solution for strip_comments.c
    #include <stdio.h>
    
    #define MAX_LINE 4096
    
    int
    main(void) {
        char line[MAX_LINE];
        int  i;
    
        while (fgets(line, MAX_LINE, stdin) != NULL) {
    
            // strip // style comments from input
    
            i = 0;
            while (line[i] != '\n' && line[i] != '\0') {
    
                // safe to look at line[i+1] because
                // we know here line[i] != '\0'
    
                if (line[i] == '/' && line[i + 1] == '/') {
    
                    // replace // with end of -line
                    line[i] = '\n';
                    line[i + 1] = '\0';
    
                    // could break here but loop will stop anyway
                }
    
                i = i + 1;
            }
    
            // write possibly-modified line
    
            printf("%s", line);
        }
        return 0;
    }
    
    
    Heavily commented sample solution.
    // reads lines from its input
    // prints them after removing an // style comments
    // so DOES NOT PRINT // and everything after it
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 4096
    
    int main (int argc, char* argv[]) {
    
    	char line[MAX];		// to store input
    	int i;				// counter to iterate through each line you read in
    
    	// get input until EOF or error
    	while (fgets(line, MAX, stdin) != NULL) {
    		// iterate through line and see if there is a comment, action appropriately
    		// comments start with '/' and are followed by '/'
    		// note the "base case" for the input for line is a 1 elt. array with '\n'
    		// i.e. when you just hit enter
    		// so lines arrays have at least 1 elt. initialized
    		i = 0;
    		while (line[i] != '\n' && line[i] != '\0') {
    			// check if this is a comment
    			// first elt. not newline or null character, so we have at least one other char.
    			// i.e. line[i + 1] is legal
    			if (line[i] == '/' && line[i+1] == '/') {
    				// we have the start of a comment
    				// printf stops printing strings at a null-terminating character '\0'
    				// so "remove" comment and everything after by changing to '\0'
    				
    				line[i] = '\n';			// helps the user so lines print on a new line, 
    				// could go without this line as long as you print later like this
    				// printf("%s\n", line);
    				
    				// this is the necessary one to stop printing
    				line[i + 1] = '\0';
    
    				// break;
    
    				// or loop will stop on next iteration since line[i] == '\n'
    			}
    
    			i++;
    		}
    
    		// write line (modified if it has comments)
    		printf("%s", line);
    
    	}
    
    
    	return EXIT_SUCCESS;
    }
    
  10. Write a program filter_empty_lines.c which reads lines from its input and prints them only if they contain a non-white-space-character.

    In another words remove lines are empty or contain only white-space.

    The only functions you can use are fgets and printf.

    You can assume lines contain at most 4096 characters.

    You can assume there are only 3 white space characters, space, tab & new-line.

    For example:

    ./filter_empty_lines
    full line
    full line
             
    another no-empty line
    another no-empty line
    
    Sample solution for filter_empty_lines.c
    #include <stdio.h>
    
    #define MAX_LINE 4096
    
    int
    main(void) {
        char line[MAX_LINE];
        int  i;
        int whiteSpaceCount;
    
        while (fgets(line, MAX_LINE, stdin) != NULL) {
    
            // print lines iff they contain a non white-space character
    
            i = 0;
            whiteSpaceCount = 0;
            while (line[i] != '\0') {
                // test for white space (isspace would be better here)
    
                if (line[i] != ' ' && line[i] != '\t' && line[i] != '\n') {
                    whiteSpaceCount = whiteSpaceCount + 1;
                    // could break here
                }
    
                i = i + 1;
            }
    
            if (whiteSpaceCount > 0) {
                printf("%s", line);
            }
        }
        return 0;
    }
    
    
    Heavily commented sample solution.
    // reads lines from input
    // prints ONLY IF they contain a non-whitespace character
    // i.e. remove lines that are empty or contain ONLY whitespace
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 4096
    #define TRUE 1
    #define FALSE 0
    
    int main (int argc, char* argv[]) {
    
    	char line[MAX];			// to store input
    	int i;					// counter for the line
    	int notWhite;			// counter for number of notwhitespace characters we have
    
    	// read until EOF or error
    	while (fgets(line, MAX, stdin) != NULL) {
    
    		// now iterate through line to see if it has whitespace
    		// strings are terminated by a null terminating character
    		i = 0;
    		notWhite = 0;	// assume this is an empty line, prove false
    		while (line[i] != '\0') {
    			// test for whitespace
    			if (line[i] != ' ' && line[i] != '\t' && line[i] != '\n') {
    				// this character isn't whitespace
    				notWhite++;	// increment number of non-whitespace
    				break;
    				// can do this without a break
    				// would just go count all the non-whitespace chars
    				// but really now you have all the info you need, slight optimization
    			}
    			i++;
    		}
    
    		// print line only if no whitespace
    		if (notWhite > 0) {
    			// found non-whitespace characters
    			printf("%s", line);
    		}
    
    	}
    
    	return EXIT_SUCCESS;
    }
    
  11. Write a C program reverse.c which reads lines and writes them out with the characters of each line in reverse order. It should stop when it reaches the end of input.

    For example:

    ./reverse
    The quick brown fox jumped over the lazy dog.
    .god yzal eht revo depmuj xof nworb kciuq ehT
    It was the best of times. It was the worst of times.
    .semit fo tsrow eht saw tI .semit fo tseb eht saw tI
    This is the last line.
    .enil tsal eht si sihT
    <control-d>
    
    Sample solution for reverse.c
    #include <stdio.h>
    
    #define MAX_LINE 4096
    
    int
    main(void) {
        char line[MAX_LINE];
        int  i;
    
        while (fgets(line, MAX_LINE, stdin) != NULL) {
    
            i = 0;
            while (line[i] != '\n' && line[i] != '\0') {
                i = i + 1;
            }
    
            i = i - 1;
    
            while (i >= 0) {
                printf("%c", line[i]);
                i = i - 1;
            }
            printf("\n");
    
        }
        return 0;
    }
    
    
    Heavily commented sample solution.
    // reads lines and writes them out
    // with the chars of each line in reverse ordder
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 4096
    
    int main (int argc, char* argv[]) {
    
    	char line[MAX];
    	int i;
    
    	while (fgets(line, MAX, stdin) != NULL) {
    		// now print the line in reverse order
    
    		// so first figure out what your HIGHEST index 
    		// that's been initialized is
    		i = 0;
    		while (line[i] != '\n' && line[i] != '\0') {
    			// this char isn't the last one
    			i++;
    		}
    		// when you exit, i is one greater than the last char
    		// since line[i] == '\n' or line[i] == '\0'
    		i--;		// so minus one to get to the index of the last char
    
    		// now print char by char until the first element at index 0
    		while (i >= 0) {
    			printf("%c", line[i]);
    			i--;
    		}
    		// end this line
    		printf("\n");
    	}
    
    
    	return EXIT_SUCCESS;
    }
    

    Revision questions

    The remaining tutorial questions are primarily intended for revision - either this week or later in session.

    Your tutor may still choose to cover some of the questions time permitting.

  12. Calculate the density of a block. The density can be defined as the number of black pixels divided by the total number of pixels in the block.
    double get_density(int height, int width, int pixels[height][width]);
        
  13. Given a 2d array, rotate all the pixels inside of that clockwise by the rotation number, which can be positive or negative. A clockwise rotation of pixels is simply a circlular rotation of the pixels in the array. A general approach would be to start with the outer layer, and rotate all the values in it around by the rotation amount. To rotate, think about doing this one pixel at a time. (If you get this working with a loop, you can think about making it more efficient by shifting more pixels at a time). Once you have done the outer layer, continue to the inner layers until you get to the middle. Be careful of the corners, since the pixels in the bottom right need to end up in the bottom and shift left.
    void rotate_array(int height, int width, int pixels[height][width], int rotation);
        
  14. Given an array of characters and a string, determine if you can build that string from the array of characters. Return 1 if you can, 0 otherwise. You cannot reuse a character (althought there might be multiple in the array). If you have unused characters from your set, then that is ok.
    int scrabble(char letters[], int num_letters, char *string);