K&R (C): generate histogram of word-lengths

From "The C Programming Language" (K&R):

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.

I wrote a program to generate a vertically-oriented histogram. It doesn't accurately handle punctuation (punctuation characters get counted as word characters), but given the limited tools covered in chapter 1 of the book, I felt this was reasonable. I've tried to limit myself to tools covered up until this point in the book (I had to resist the urge to use ternaries in a couple spots).

#include <stdio.h>

#define IN_WORD     1   /* point in word */
#define OUT_WORD    0   /* point out of word */
#define MAX_LEN     20  /* max word length to consider */

int main()
{
int i, j;       /* iterators */
int c;          /* character */
int len;        /* word length */
int state;      /* in/out of word */
int top_count;
int histogram[MAX_LEN];

i = j = c = len = top_count = 0;
state = OUT_WORD;

for (i = 0; i < MAX_LEN; ++i)
histogram[i] = 0;

/* process input */
while ((c = getchar()) != EOF) {

if (c == ' ' || c == '\t' || c == '\n') {
if (state == IN_WORD) {
/* increment histogram entry for current word length */
if (len < MAX_LEN)
j = len;
else
j = MAX_LEN;
++histogram[j - 1];

/* keep a record of the highest count */
if (histogram[j-1] > top_count)
top_count = histogram[j-1];
}
/* reset state */
len = 0;
state = OUT_WORD;

} else {
/* keep track of current word length */
++len;
state = IN_WORD;
}
}

/* print histogram from top to bottom */
for (i = top_count; i > 0; --i) {
/* print Y-axis */
printf("%3d|", i);

/* print entries for each word length */
for (j = 0; j < MAX_LEN; ++j) {
if (histogram[j] < i)
printf("  ");
else
printf(" .");
}
putchar('\n');
}

printf("    ");
/* print X-axis */
for (i = 0; i < MAX_LEN; ++i)
printf("--");
putchar('\n');

return 0;
}


A small sample run against a quote by Benjamin Franklin:

In wine there is wisdom, in beer there is Freedom, in water there is bacteria.

  6|   .
5|   .
4|   .     .
3|   .     .
2|   .   . .
1|   .   . .   . . .
----------------------------------------


Initial reaction to your program is that it seems to be good and clean C code. So the overall impression is good, but there are things to review, even though some comments may be a bit of personal reference.

• Punctuation char or not – The code includes check against single characters, so the extension to check against the ranges from c > 'a' && c < 'z', should be within reach
• Split main method in multiple functions – This might not be covered yet, but I include it as it is good to start doing this as early as possible. However this does introduce the icky subject of passing arrays with/without size. Sorry about that!
• Use of state vs simple length of current word – The naming of the states was a little unclear to me, and whilst reviewing the logic it hit me that if you are not counting the length of a word (i.e. the character is a legal word character), you can simply test if the length of the word, len, is larger than 0 to match your current IN_WORD state. As such, the state variable can be replaced with a test len > 0
• Make the most common (shortest?) block come first – In your code you start of the input processing by verifying length of something and adding to the histogram. But of what? Then comes the block actually increasing the length and reading the words. To me, it is more natural to switch these blocks, so that you know why len has a length
• Stay consistent with bracing – For most of the code you've chosen to have start braces at preceding line, and that is a style choice. You've also chosen to let one-liners be without braces, this I would advise against. At some point in time this cause you some issue. My strong suggestion is to always enclose for or if (or similar) blocks with braces always. It will save you some grief further down the line.
• Include number on both axes – Kind of strange not have numbers on the x-axis. To allow for two digits in the length of word, you can increase width of each column to three characters
• Skip empty columns – No need to print the empty columns, is there?
• Consider changing columnn marker – To me, the . is a little invisible, and I feel the # or * is more intuitive to use to mark the count
• Consider labeling the axes – Consider adding labels like Count or Occurences, and Word length for the axes. It does however impose a smaller problem of where to put them...
• Why the putchar, when printf works? – The usage of putchar('\n'); seems unmotivated, when you can do a printf("\n");. Is there a reason behind that?
• Comment on comments – You've added suitable comments in most places, and when going to functions this becomes even more importantprocessing

Refactored code

That is enough rambling, and here is my suggestion to refactor code addressing most of the issues I've commented upon:

#include <stdio.h>

#define IN_WORD     1   /* point in word */
#define OUT_WORD    0   /* point out of word */
#define MAX_LEN     20  /* max word length to consider */

/*
* Reset the histogram to all 0's too clear it out
*/
void init_histogram(int histogram[], size_t histogram_length)
{
int i;

for (i = 0; i < histogram_length; ++i) {
histogram[i] = 0;
}
}

/*
* Read input, character by character, and divide into
* words which are counted the length of (up until the max
* max length specified in histogram_length). If word is
* actually longer, the histogram records is at max length.
*
* Count characters, a-z and A-Z, and increase length of word,
* and add to histogram if length>0 when we hit a non-character
*/
void create_histogram_from_input(int histogram[], size_t histogram_length)
{
int len=0;       /* length of current word */
int c;           /* current character */

/* Keep reading character until end of file */
while ((c = getchar()) != EOF) {

// Check if it is an character ...
if ( ( c >= 'a' && c <= 'z') ||
( c >= 'A' && c <= 'Z') ||
c == '-' ) {

++len; /* Increase length of current word */

} else {
/* ... it was not a character, so check if we have
* a positive word length
*/
if (len > 0) {
/* increment histogram entry for current word length */
if (len >= histogram_length) {
len = histogram_length;
}

histogram[len - 1]++;

len = 0; /* Reset length of current word */
}
}
}
}

/* Pretty print the histogram vertically, with numbered x-
* and y-axis. Only print as many columns as we have word lengths
*/
void print_histogram(int histogram[], size_t histogram_length)
{
int i, j, c;
const int y_axis_width = 4;

int top_count = 0; /* Highest count of a given length */
int max_length = 0; /* The longest word in histogram */

/* Find the highest count, and longest word */
for (i = histogram_length; i > 0; --i) {

/* If max_length is not set, and we find a positive length
* whilst going backwards, it is the longest word
*/
if (max_length == 0 && histogram[i-1] > 0) {
max_length = i;
}

/* Scan entire histogram to find the highest count of that length */
if (histogram[i-1] > top_count) {
top_count = histogram[i-1];
}
}

/* print histogram from top to bottom */
for (i = top_count; i > 0; i--) {

/* print Y-axis */
printf("%3d|", i); /* If this changes, change y_axis_width */

/* print entries for each word length */
for (j = 0; j < max_length; j++) {
if (histogram[j] < i) {
printf("   ");
} else {
printf(" # ");
}
}
printf("\n");
}

/* print X-axis separator*/
printf("%*s", y_axis_width, " ");
for (i = 0; i < max_length; i++) {
printf("---");
}
printf("\n");

/* print X-axis numbers */
printf("%*s", y_axis_width, " ");
for (i = 0; i < max_length; i++) {
printf("%2d ", i+1);
}
printf("\n");
}

int main()
{
int histogram[MAX_LEN];

/* Reset histogram */
init_histogram(histogram, MAX_LEN);

/* Read input, and fill out the histogram */
create_histogram_from_input(histogram, MAX_LEN);

/* Print out the histogram */
print_histogram(histogram, MAX_LEN);

return 0;
}


Some extra comments regarding my refactored code:

• Location of top_count in functions – When all is gathered within main() your choice of doing the top_count in the input processing loop is not the worst. However when dividing into functions, it does rather belong in the print_histogram() instead of input processing. This also removes the extra setting of this multiple times during the processing
• Size of arrays and functions – One of the major hickups with C is that when an array is sent as an parameter to a function, you loose the size information. It is a best practice to include this as a parameter. For more information see How do I determine the size of my array in C?
• Some dislike printf("literal string") – This is sometimes frowned upon, as it is considered to be a security issue, especially in the form char *s; ... ; printf(s). The first parameter of printf is supposed to be a format string, and neither the literal string nor the string pointer are safe in that respect. They could be replaced by using printfs("%s", s), but often this is skipped by most people
• The printf width as parameter trick – Using printf("%*d", width, number), i.e. that is including * in the format string, you can specify the width in the parameter. This allows in my code for setting the leading indent before the x-axis text using the constant y_axis_width
• Finding number of columns – To ease the logic of finding the longest word, I reversed the scan for top_count and max_length. This allows me to use one single loop, since top_count doesn't care, but for max_length I can there simply test if is set or not, before checking if that histogram column has a length, which indicates that there is a list one word of that length.

A test run against the leading comment of create_histogram_from_input() gave the following output:

 15|       #
14|       #
13|       #
12|    #  #
11|    #  #
10|    #  #
9|    #  #
8|    #  #        #
7|    #  #        #
6|    #  #        #        #
5|    #  #  #  #  #        #
4|    #  #  #  #  #        #
3|    #  #  #  #  #        #
2|    #  #  #  #  #  #  #  #
1| #  #  #  #  #  #  #  #  #  #        #
---------------------------------------
1  2  3  4  5  6  7  8  9 10 11 12 13

• Be careful with making assumptions about character coding. If you've been brought up in an ASCII world, you might have unreasonable expectations about expressions like c > 'a' && c < 'z'. – Toby Speight Oct 17 '18 at 13:26

No need for state

The state variable is redundant because state == IN_WORD is equivalent to len > 0.

Use isspace()

Instead of checking for whitespace with your own check, you could use isspace() from ctype.h. It checks for more types of whitespace such as form feed and carriage return.

Array initialization

Your code to initialize the histogram to zero:

for (i = 0; i < MAX_LEN; ++i)
histogram[i] = 0;


could be simpler. You could either just do it when you declare the array:

int histogram[MAX_LEN] = {0};


or use memset():

memset(histogram, 0, sizeof(histogram));


Label the x-axis

I find it hard to read your histogram without seeing labels on the x-axis for the word lengths.