(guest@joequery.me)~ $ |

Learning C (Part 3): K&R Ch1 Exercises

(This post is part of the learning c series.)

This article will provide solutions and explanations of K&R ch 1 exercises that I find interesting.

Exercise 1-6

Verify that the expression getchar() != EOF is 0 or 1.

The purpose of this exercise is to demonstrate that the resulting value of a conditional statement can only be 0 or 1.

1
2
3
4
5
6
7
8
9
#include <stdio.h>
int main(){
    int expr_val, c;
    printf("Input a character and press enter: ");
    expr_val = (getchar() != EOF);
    printf("expr_val: %d\n", expr_val);

    return 0;
}

raw source | show output ⇓ 

$ ./a.out
Input a character and press enter: h
expr_val: 1
$ ./a.out # I press CTRL-D to send EOF
Input a character and press enter: expr_val: 0

Exercise 1-8

Write a program to count blanks, tabs, and newlines.

The purpose of this exercise is to test your ability to do a few things:

  • continuously get input from the keyboard
    • know when to stop
  • comparing the value from the keyboard with character literals
  • storing the count of the characters mentioned

 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
26
27
28
29
#include <stdio.h>
int main(){
    int c, num_tabs, num_blanks, num_newlines;
    num_tabs = num_blanks = num_newlines = 0;

    printf("Enter text. Press CTRL-D when finished\n> ");
    while( (c = getchar()) != EOF ){
        if(c == '\n')
            printf("> ");

        switch(c){
            case '\t':
                num_tabs++;
                break;
            case ' ':
                num_blanks++;
                break;
            case '\n':
                num_newlines++;
                break;
        }
    }
    printf("EOF sent\n");

    printf("num_tabs: %d\n", num_tabs);
    printf("num_blanks: %d\n", num_blanks);
    printf("num_newlines: %d\n", num_newlines);
    return 0;
}

raw source | show output ⇓ 

$ ./a.out
Enter text. Press CTRL-D when finished
> Hello there. How are you doing today?
> Really? That's great!
> EOF sent
num_tabs: 0
num_blanks: 8
num_newlines: 2

$ ./a.out
Enter text. Press CTRL-D when finished
> I     Love
> Whitespace    Formatting
> EOF sent
num_tabs: 2
num_blanks: 0
num_newlines: 2

Exercise 1-12

We will naively consider the word separating characters to be , \n, and \t. Also, as always, we must check for EOF.

In this exercise, I will use a helper function named is_word_separator. This will be a good time to demonstrate writing simple tests via the standard library's assert() function. The assert() function takes an expression, generally some sort of comparison, and will stop program execution if the expression evaluates to False. Additionally, assert() will print out the failed assertion.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <stdio.h>
#include <assert.h>  // access to assert() function
int main(){
    int account_balance = 10;
    int product_cost = 20;

    // account_balance isn't allowed to be negative
    assert(account_balance > 0);

    // buy a product...
    account_balance -= product_cost;

    assert(account_balance > 0);
    return 0;
}

raw source | show output ⇓ 

$ ./a.out 
a.out: assertion-ex.c:13: main: Assertion `account_balance > 0' failed.
Aborted (core dumped)

The exercise solution:

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <assert.h>
int is_word_separator(char c);
void test_word_separator();

int main(){
    int c, status;
    // First, we test our is_word_separator function.
    // If program execution makes it past this line, our is_word_separator
    // function is good!
    test_word_separator();

    printf("Type words! CTRL-D to exit.\n");
    printf("> ");

    status = 0; // 0 => out of word, 1 => inside word

    while( (c = getchar()) != EOF ){
        // status can be 0 or 1, c can be word separator or not, so we have
        // 2x2=4 cases total to consider.
        if(status){
            if(is_word_separator(c)){
                status = 0;
                // Just for presentation! :)
                if(c == '\n')
                    printf("\n> ");
                else
                    printf("\n");
            }
            else{
                printf("%c", c);
            }
        }
        else{
            if(is_word_separator(c)){
                // Just for presentation! :)
                if(c == '\n')
                    printf("> ");
            }
            else{
                status = 1;
                printf("%c", c);
            }

        }

    }
    printf("EOF sent.\n");
    return 0;
}

int is_word_separator(char c){
    switch(c){
        case '\n':
        case '\t':
        case ' ':
            return 1;
        default:
            return 0;
    }
}

void test_word_separator(){
    assert(is_word_separator('x') == 0);
    assert(is_word_separator(' ') == 1);
    assert(is_word_separator('\n') == 1);
    assert(is_word_separator('\t') == 1);
    assert(is_word_separator('A') == 0);
}

raw source | show output ⇓ 

$ ./a.out
Type words! CTRL-D to exit.
> Hello there! How are you doing today?
Hello
there!
How
are
you
doing
today?
> I'm doing pretty awesome, thanks!
I'm
doing
pretty
awesome,
thanks!
> 
> 
> 
> 
> 
> Tabs  are     pretty  cool,   man
Tabs
are
pretty
cool,
man
> EOF sent.

Exercise 1-13

Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.

We'll skip the horizontal representation for now. To further clarify, if we recieve 1 word of length one, 2 words of length two, 3 words of length three, etc, the histogram would look like so:

  |
 ||
|||
123

Here's an $O(n^2)$ way of solving it. Note that it's really important you don't attempt to take on the entire exercise at once. Here's an intermediate program that prints the histogram from a hardcoded array. This facilitates quicker development and testing since keyboard input is easy but time-consuming.

 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
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
void make_histogram(int arr[], size_t n);

int main(){
    int word_lengths[] = {0, 3, 6, 5};
    make_histogram(word_lengths, 4);
    return 0;
}

// 3 <= n <= 9
void make_histogram(int arr[], size_t n){
    int i, maxval;

    // 0 length words don't mean anything, skipping over them.
    maxval = arr[1];
    for(i=2; i<n; i++)
        if(arr[i] > maxval)
            maxval = arr[i];

    while(maxval > 0){
        for(i=1; i<n; i++){
            if(arr[i] >= maxval)
                putchar('|');
            else
                putchar(' ');
        }
        putchar('\n');
        maxval--;
    }

    // Print footer
    for(i=1; i<n; i++){
        putchar('0'+i);
    }
    putchar('\n');

}

raw source | show output ⇓ 

 |
 ||
 ||
|||
|||
|||
123

Now that we have verified the make_histogram function works as intended, lets make a separate intermediate program that can take user input and count words. We can use a majority of the code from exercise 1-12, with some slight modifications, to facilitate this.

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
int is_word_separator(char c);
void get_word_lengths(int word_lengths[], size_t n);

int main(){
    int i;
    // Up to length 9. Initialize all to 0.
    int word_lengths[10] = {0};
    get_word_lengths(word_lengths, 10);

    // Print the array elements
    for(i=1; i<10; i++)
        printf("Num words of length %d - %d\n", i, word_lengths[i]);
    return 0;
}

int is_word_separator(char c){
    switch(c){
        case '\n':
        case '\t':
        case ' ':
            return 1;
        default:
            return 0;
    }
}

void get_word_lengths(int word_lengths[], size_t n){
    int c, status, length, i;


    printf("Type words! CTRL-D to exit.\n");
    printf("> ");

    status = 0; // 0 => out of word, 1 => inside word
    length = 0; // current word length

    while( (c = getchar()) != EOF ){
        if(status){
            if(is_word_separator(c)){
                status = 0;

                // We are at the end of the word. This is how we keep a tally.
                // Draw it out on a piece of paper if you don't understand :)
                ++word_lengths[length];

                // Reset the word length since we are now finished with the
                // current word.
                length = 0;

                if(c == '\n')
                    printf("> ");
            }
            else{
                length++;
            }
        }
        else{
            if(is_word_separator(c)){
                if(c == '\n')
                    printf("> ");
            }
            else{
                status = 1;

                // We just encountered our first character of the new word
                length = 1;
            }
        }
    }
}

raw source | show output ⇓ 

$ ./a.out 
Type words! CTRL-D to exit.
> a ab abc a ab abc
> EOF sent.
Num words of length 1 - 2
Num words of length 2 - 2
Num words of length 3 - 2
Num words of length 4 - 0
Num words of length 5 - 0
Num words of length 6 - 0
Num words of length 7 - 0
Num words of length 8 - 0
Num words of length 9 - 0

$ ./a.out 
Type words! CTRL-D to exit.
> Hello there. How are you doing today?
> EOF sent.
Num words of length 1 - 0
Num words of length 2 - 0
Num words of length 3 - 3
Num words of length 4 - 0
Num words of length 5 - 2
Num words of length 6 - 2
Num words of length 7 - 0
Num words of length 8 - 0
Num words of length 9 - 0

Now, with both the histogram and word length counting individually verified, we can combine them without much effort at all! I only made some minor output changes to the functions for presentational purposes.

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
int is_word_separator(char c);
void get_word_lengths(int word_lengths[], size_t n);
void make_histogram(int arr[], size_t n);

int main(){
    // Up to length 9. Initialize all to 0.
    int word_lengths[10] = {0};
    get_word_lengths(word_lengths, 10);
    putchar('\n');
    make_histogram(word_lengths, 10);
    return 0;
}

// 3 <= n <= 9
void make_histogram(int arr[], size_t n){
    int i, maxval;

    // 0 length words don't mean anything, skipping over them.
    maxval = arr[1];
    for(i=2; i<n; i++)
        if(arr[i] > maxval)
            maxval = arr[i];

    while(maxval > 0){
        for(i=1; i<n; i++){
            if(arr[i] >= maxval)
                putchar('|');
            else
                putchar(' ');
        }
        putchar('\n');
        maxval--;
    }

    // Print footer
    for(i=1; i<n; i++){
        putchar('0'+i);
    }
    putchar('\n');
}

int is_word_separator(char c){
    switch(c){
        case '\n':
        case '\t':
        case ' ':
            return 1;
        default:
            return 0;
    }
}

void get_word_lengths(int word_lengths[], size_t n){
    int c, status, length, i;
    printf("Type words! CTRL-D to exit.\n");
    printf("> ");

    status = 0; // 0 => out of word, 1 => inside word
    length = 0; // current word length

    while( (c = getchar()) != EOF ){
        if(status){
            if(is_word_separator(c)){
                status = 0;

                // We are at the end of the word. This is how we keep a tally.
                // Draw it out on a piece of paper if you don't understand :)
                ++word_lengths[length];

                // Reset the word length since we are now finished with the
                // current word.
                length = 0;

                if(c == '\n')
                    printf("> ");
            }
            else{
                length++;
            }
        }
        else{
            if(is_word_separator(c)){
                if(c == '\n')
                    printf("> ");
            }
            else{
                status = 1;

                // We just encountered our first character of the new word
                length = 1;
            }
        }
    }
}

raw source | show output ⇓ 

$ ./a.out 
Type words! CTRL-D to exit.
> a ab abc a ab abc
> 
|||      
|||      
123456789

$ ./a.out 
Type words! CTRL-D to exit.
> Hello there. How are you doing today?
> 
  |      
  | ||   
  | ||   
123456789

$ ./a.out 
Type words! CTRL-D to exit.
> Hello there! How are you doing today, friend? I hope you are enjoying your
> C lessons. It is very good practice. These exercises will enhance your C skills for sure.
> 
  ||     
  ||     
  |||    
| ||||   
|||||||||
|||||||||
123456789

Exercise 1-19

Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.

This will be a good time to draw a picture to get some ideas of how we would like to approach this. Consider the char array ['T', 'a', 'b', 'l', 'e', 't']. This is what reversing it would look like.

We can see that index 0 of s goes to index 5 of reverse(s), and so on. Generalizing this mapping is key to coming up with an algorithm for an arbitrary length string. Let's look at another example and see if you can catch on the pattern. (Hint: Use the length of the string)

So the index mapping can be formulized as x => max_index - x. So, for ['A', 'w', 'e', 's', 'o', 'm', 'e'], a char array of length 8 (thus with max index 7), element 2 ('e') would go to 7-2 == 5.

Also important to note, you'll see pairs of mappings in the index mappings. You see in the ['T', 'a', 'b', 'l', 'e', 't'] example that 0 goes to 5, and 5 goes to 0, 2 goes to 3, 3 goes to 2, etc. We can instead say 0 is swapped with 5, and 2 is swapped with 3. We can essentially cut our index mapping in half and use "swaps" instead of "goes to", while still providing the same information

A couple more warnings before we start coding.

Even/odd length char arrays

I intentionally chose char arrays of even lengths since the index mapping is easier to explain that way. However, our reverse() function needs to be able to handle odd-length char arrays. So let's examine ['H', 'e', 'l', 'l', 'o'].

Verify for yourself that max_index/2 stays put when reversing odd-length char arrays.

null-termination character

All strings are char arrays, but not all char arrays are strings: The difference is the terminating null character '\0' present in the char array. These examples so far have not been strings. When dealing with reversing strings, we need to ensure the null character doesn't move. Reversing a string should not change its length, so there's no need to move the null character.

Solution exercise

I will take advantage of the assert() function yet again to demonstrate the usefulness of automated testing. We can set up test-cases that let us know when we have reached our goal. Additionally, we can put ourselves in the "tester" mindset and focus on edge cases where our code may break.

Let's write our tests. We will use the strcmp() standard library function for string comparison. strcmp() takes two strings and returns 0 when they are equal. Additionally, strcpy will be used to copy string literals into an array, since string literals are read only.

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <assert.h>
#include <string.h>

void test_reverse();
void reverse(char str[], size_t n);
int main(){
    test_reverse();
    printf("reverse() works!\n");
    return 0;
}

/*
 * Reverse a string str with array string length n (don't include null char!)
 * Note: the string passed is altered.
 */
void reverse(char str[], size_t n){
    // To be implemented...
}

/*
 * Set up test cases to help us verify our reverse function works.
 */
void test_reverse(){
    char str[10] = {0}; // Init all elements to \0
    int testnum = 1;

    // Can the function handle odd-length strings?
    strcpy(str, "hello");
    reverse(str, 5);
    assert(strcmp("olleh", str) == 0);
    printf("test %d pass\n", testnum++);

    // Can the function handle even-length strings?
    strcpy(str, "tablet");
    reverse(str, 6);
    assert(strcmp("telbat", str) == 0);
    printf("test %d pass\n", testnum++);

    // What about shorter strings?
    strcpy(str, "hi");
    reverse(str, 2);
    assert(strcmp("ih", str) == 0);
    printf("test %d pass\n", testnum++);

    strcpy(str, "hey");
    reverse(str, 3);
    assert(strcmp("yeh", str) == 0);
    printf("test %d pass\n", testnum++);

    // What about 1-length strings?
    strcpy(str, "i");
    reverse(str, 1);
    assert(strcmp("i", str) == 0);
    printf("test %d pass\n", testnum++);

    // And empty strings?
    strcpy(str, "");
    reverse(str, 0);
    assert(strcmp("", str) == 0);
    printf("test %d pass\n", testnum++);
}

raw source | show output ⇓ 

a.out: ex1-19-testcases.c:32: test_reverse: Assertion `strcmp("olleh", str) ==
0' failed.
Aborted (core dumped)

We have now set up our code in such a way that once all the assertions pass, (and we can thus make "reverse() works!" print out), we can be confident that our reverse() function is correct! It is much easier to program a solution when you have created a roadmap such as this for yourself.

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <assert.h>
#include <string.h>

void test_reverse();
void reverse(char str[], size_t n);
int main(){
    test_reverse();
    printf("reverse() works!\n");

    char str[] = "Hello there";
    reverse(str, 11);
    printf("%s\n", str);
    return 0;
}

/*
 * Reverse a string str with array string length n (don't include null char!)
 * Note: the string passed is altered.
 */
void reverse(char str[], size_t n){
    int i, tmp;

    // Remember / is integer division: 5/2 = 2
    for(i=0; i<n/2; i++){
        tmp = str[i];
        str[i] = str[n-1-i];
        str[n-1-i] = tmp;
    }
}

/*
 * Set up test cases to help us verify our reverse function works.
 */
void test_reverse(){
    char str[10] = {0}; // Init all elements to \0
    int testnum = 1;

    // Can the function handle odd-length strings?
    strcpy(str, "hello");
    reverse(str, 5);
    assert(strcmp("olleh", str) == 0);
    printf("test %d pass\n", testnum++);

    // Can the function handle even-length strings?
    strcpy(str, "tablet");
    reverse(str, 6);
    assert(strcmp("telbat", str) == 0);
    printf("test %d pass\n", testnum++);

    // What about shorter strings?
    strcpy(str, "hi");
    reverse(str, 2);
    assert(strcmp("ih", str) == 0);
    printf("test %d pass\n", testnum++);

    strcpy(str, "hey");
    reverse(str, 3);
    assert(strcmp("yeh", str) == 0);
    printf("test %d pass\n", testnum++);

    // What about 1-length strings?
    strcpy(str, "i");
    reverse(str, 1);
    assert(strcmp("i", str) == 0);
    printf("test %d pass\n", testnum++);

    // And empty strings?
    strcpy(str, "");
    reverse(str, 0);
    assert(strcmp("", str) == 0);
    printf("test %d pass\n", testnum++);
}

raw source | show output ⇓ 

test 1 pass
test 2 pass
test 3 pass
test 4 pass
test 5 pass
test 6 pass
reverse() works!
ereht olleH

Tagged as c

(This post is part of the learning c series.)

Date published - November 27, 2013