3
\$\begingroup\$

I'm going through the K&R book (2nd edition, ANSI C ver.) and want to get the most from it. How does the following solution look to you? Note that, for the sake of exercise, I don't want to use techniques not introduced yet in the book. Also, I'm trying to reuse whatever code/philosophy already presented in the book.

/* 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.
 * */
/* Solution 1: Horizontal Bars
 * */
#include <stdio.h>

#define MAXLEN  10  /* Any word longer than this will get counted in the >MAXLEN histogram.
                     * For output formatting, the program assumes this won't be greater than 999.
                     * */
#define IN      1   /* inside a word */
#define OUT     0   /* outside a word */

int main()
{
    int c, state;
    int i, j;
    int histo[MAXLEN+1];
    int counter;

    for (i = 0; i < MAXLEN+1; ++i)
        histo[i] = 0;

    /* Perform the counting */
    state = OUT;
    counter = 0;
    while ((c = getchar()) != EOF)
        if (c == ' ' || c == '\n' || c == '\t') {
            if (state == IN && counter > 0) {
                if (counter-1 < MAXLEN)
                    ++histo[counter-1];
                else
                    ++histo[MAXLEN];
            }
            state = OUT;
            counter = 0;
        }
        else {
            ++counter;
            if (state == OUT)
                state = IN;
        }

    /* Print horizontal histogram. I'd use a function for formatting
     * with regards to max. number of digits, but functions haven't
     * been introduced yet.
     * */
    for (i = 0; i < MAXLEN; ++i) {
        if (MAXLEN < 10)
            printf(" %1d | ", i+1);
        else if (MAXLEN < 100)
            printf(" %2d |", i+1);
        else
            printf(" %3d |", i+1);
        for (j = 0; j < histo[i]; ++j)
            putchar('*');
        putchar('\n');
    }
    if (MAXLEN < 10)
        printf(">%1d |", i);
    else if (MAXLEN < 100)
        printf(">%2d |", i);
    else
        printf(">%3d |", i);
    for (j = 0; j < histo[i]; ++j)
        putchar('*');
    putchar('\n');
}

Output when run on the program code:

$ cat ch1-ex-1-13-01.c | ./ch1-ex-1-13-01
  1 |*********************************************************
  2 |****************************************************************
  3 |***************************************
  4 |************************************
  5 |**************
  6 |**********
  7 |************************
  8 |***********
  9 |*******
 10 |*********
>10 |**************
\$\endgroup\$
  • \$\begingroup\$ By the way, which Version of the C Standard are you targeting? Premordial, K&R, C90, C99, C11? \$\endgroup\$ – Deduplicator Oct 18 '18 at 15:59
  • \$\begingroup\$ I didn't think about it until I saw the answer here using C99 & C90. I guess I'll be sticking to K&R 2nd edition as I go through the book, but it certainly wouldn't hurt to be aware of new features where relevant. \$\endgroup\$ – div0man Oct 18 '18 at 16:11
  • \$\begingroup\$ I earnestly suggest that you take a close look at your book: Is it really K&R-C, or (mostly) C90? It depends on the revision. In any case, I suggest targeting at least C90, which might be ancient but is still ubiquitous. For Background, consider reading this post on meta.SO and this tag-wiki on SO. \$\endgroup\$ – Deduplicator Oct 18 '18 at 16:24
  • 1
    \$\begingroup\$ Since it's 2nd ed. I interpret it as being C90, right? The second edition, "K&R2", was first published in 1988 with some updates of the book to meet the version of the language standardized by ANSI in 1989. and The 1989 ANSI C standard was republished by ISO in 1990 \$\endgroup\$ – div0man Oct 18 '18 at 16:28
1
\$\begingroup\$

K&R C requires all variables to be declared at the start of their enclosing block. This is a bad habit to learn: it's much safer to declare variables where they can be initialised:

/* these can already be initialised where they are declared */
int state = OUT;
int histo[MAXLEN+1] = { 0 };  /* C90 */
int counter = 0;
/* reduce scope, and never have uninitialized value */
for (int j = 0; j < histo[i]; ++j)  /* C99 */

We could remove the need to subtract 1 from the length when updating histo if we reserve the first element for long words instead of the last:

        if (state == IN && counter > 0) {
            if (counter <= MAXLEN)
                ++histo[counter];
            else
                ++histo[0];
        }

We obviously need to make a corresponding change to the printing:

for (int i = 1;  i <= MAXLEN;  ++i) {
    if (MAXLEN < 10)
        printf(" %1d | ", i);
    else if (MAXLEN < 100)
        printf(" %2d |", i);
    else
        printf(" %3d |", i);
    for (int j = 0;  j < histo[i];  ++j)
        putchar('*');
    putchar('\n');
}

We can avoid the if/else chain on MAXLEN in this loop, by choosing the formatting string in advance:

const char *format = "";
if (MAXLEN < 10) {
        format = " %1d | ";
} else if (MAXLEN < 100) {
        format = " %2d | ";
}  else {
        format = " %3d | ";
}

for (int i = 1;  i <= MAXLEN;  ++i) {
    printf(format, i);
    for (int j = 0;  j < histo[i];  ++j)
        putchar('*');
    putchar('\n');
}

That might not look like an improvement, but with a small change, we can use the same format string to insert > for the over-long words, too:

const char *format = "";
if (MAXLEN < 10) {
        format = "%c%1d | ";
} else if (MAXLEN < 100) {
        format = "%c%2d | ";
}  else {
        format = "%c%3d | ";
}

for (int i = 1;  i <= MAXLEN;  ++i) {
    printf(format, ' ', i);
    for (int j = 0;  j < histo[i];  ++j)
        putchar('*');
    putchar('\n');
}

/* over-long words */
printf(format, '>', MAXLEN);
for (int j = 0; j < histo[0]; ++j)
    putchar('*');
putchar('\n');

Going beyond the expected level of knowledge, we could even compute the necessary length, and pass it using %*d:

int width = 1;
for (int i = MAXLEN;  i >= 10;  i /= 10) {
    ++width;
}

for (int i = 1;  i <= MAXLEN;  ++i) {
    printf(" %*d | ", width, i);
    for (int j = 0;  j < histo[i];  ++j)
        putchar('*');
    putchar('\n');
}

/* over-long words */
printf(">%*d | ", width, MAXLEN);
for (int j = 0; j < histo[0]; ++j)
    putchar('*');
putchar('\n');

That allows us to have non-constant MAXLEN, which will be to our advantage in future when we make this a function.


Whilst the state machine is a good idea, it turns out we don't need to explicitly store state, because counter is always zero outside a word and non-zero once we're in one:

while ((c = getchar()) != EOF) {
    if (c == ' ' || c == '\n' || c == '\t') {
        if (counter > 0) {
            ++histo[counter <= MAXLEN ? counter : 0];
            counter = 0;
        }
    } else {
        ++counter;
    }
}

Did you spot the bug in this loop? Probably not, because the bug is missing code immediately after the loop. If the input stream ends during a word, we fail to count it. We need to repeat the if (counter > 0) test just after the loop, to catch that case.


We have an unusual definition of "word" - in our source code, strings such as ++histo[counter-1]; count as single words. Even in English text, we'd expect text, to register as a four-character word. To fix this, we could consider only alphanumerics as word characters, and that could be a good introduction to the functions in <ctype.h>.

while ((c = getchar()) != EOF) {
    if (isalnum(c)) {
        ++counter;
    } else {
        if (counter > 0) {
            ++histo[counter <= MAXLEN ? counter : 0];
            counter = 0;
        }
    }
}

if (counter > 0) {
    ++histo[counter <= MAXLEN ? counter : 0];
}

Enhancement - we could avoid bars going off the right edge of the display, by calculating a scale factor first. Here's my suggestion:

#define MAXWIDTH 72             /* screen width available for bars */
    double scale = 1.0;
    for (int i = 0;  i <= MAXLEN;  ++i) {
        if (histo[i] * scale > MAXWIDTH) {
            scale = 1.0 * MAXWIDTH / histo[i];
        }
    }
        for (int j = 0;  j < histo[i] * scale;  ++j) { putchar('*'); }

Finally: it's not part of your C code, but there's no need for cat in the test. We can simply redirect input like this:

./ch1-ex-1-13-01 <ch1-ex-1-13-01.c

Modified code

Applying all my suggestions, I got:

/* 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. */

/* Solution 1: Horizontal Bars
 * */
#include <ctype.h>
#include <stdio.h>

#define MAXLEN  10  /* Any word longer than this will get counted in the
                       >MAXLEN histogram. */

#define MAXWIDTH 72             /* screen width available for bars */

int main()
{
    int histo[MAXLEN+1] = { 0 }; /* element 0 counts over-length words */

    /* Perform the counting */
    int counter = 0;
    int c;
    while ((c = getchar()) != EOF) {
        if (isalnum(c)) {
            ++counter;
        } else {
            if (counter > 0) {
                ++histo[counter <= MAXLEN ? counter : 0];
                counter = 0;
            }
        }
    }

    if (counter > 0) {
        ++histo[counter <= MAXLEN ? counter : 0];
    }

    /* Calculate sensible scale */
    double scale = 1.0;
    for (int i = 0;  i <= MAXLEN;  ++i) {
        if (histo[i] * scale > MAXWIDTH) {
            scale = 1.0 * MAXWIDTH / histo[i];
        }
    }

    /* how wide are the labels? */
    int width = 1;
    for (int i = MAXLEN;  i >= 10;  i /= 10) {
        ++width;
    }

    /* Write the output */
    for (int i = 1;  i <= MAXLEN;  ++i) {
        printf(" %*d | ", width, i);
        for (int j = 0;  j < histo[i] * scale;  ++j) { putchar('*'); }
        putchar('\n');
    }

    /* over-long words */
    printf(">%*d | ", width, MAXLEN);
    for (int j = 0; j < histo[0] * scale; ++j) { putchar('*'); }
    putchar('\n');
}
\$\endgroup\$
  • \$\begingroup\$ Wow, great, thank you! Is your array initialization also C99? I thought about using [0] for the over-length but wasn't sure if it's good for code readability. I do like it, tho. Cool idea for formatting string with the %c%d, I'll remember that (char array assignment hasn't been introduced yet, tho). Didn't know about the %*d trick, I'd probably go with sprintf instead. /= hasn't been introduced, but I get the idea. For the bug, nice catch, I didn't notice. Or, we could say we're counting complete words :) As for word definition, I agree tho I followed the book example 1.5.4 there. \$\endgroup\$ – div0man Oct 16 '18 at 13:52
  • \$\begingroup\$ That initialization is plain C90 (C99 adds support for non-constant initializers, but incomplete initializer lists go back to at least the first Standard C). The use of element [0] is clearer in my (subjective) opinion, but others may differ (or might want more comments). As for the rest, I don't have my K&R with me here, so had to guess what's in scope and what's not! \$\endgroup\$ – Toby Speight Oct 16 '18 at 14:07
  • \$\begingroup\$ Nice to know, I'm yet to learn about different standards. For now I'm just following K&R as if we're still living in the 80's. I've implemented your comments myself and posted it as another answer. Fixed some scaling issues, too. \$\endgroup\$ – div0man Oct 17 '18 at 13:21
  • \$\begingroup\$ If the number of stars is bounded and acceptably small, they can all be printed at once using part of the same string-literal. And that can be fused with the preceding printf() and trailing printing of a newline. \$\endgroup\$ – Deduplicator Oct 18 '18 at 11:55
  • \$\begingroup\$ Yes @Deduplicator, that's probably what I'd do with this. I was already in too deep, though... \$\endgroup\$ – Toby Speight Oct 18 '18 at 12:10
0
\$\begingroup\$

Take 2

I've reworked my code according to the comments received here but sticking to the techniques which have been introduced up to this point in K&R, which means the following is NOT used:

  • variable declaration where first initialized,
  • assignment of char array constants,
  • %*d format specifier,
  • ctype.h.

Some other improvements:

  • avoided repeating some code by introducting readEOF state,
  • improved scaling,
  • check whether MAXWIDTH is sufficient to print the smallest possible chart,
  • printing numerical value next to histogram,
  • figured out how to print labels better, while sticking to the techniques introduced so far,
  • limited source code width to 72,
  • fixed a scaling bug due to flating point precision,
  • reverted to storing >MAXLEN count in the last element.

Modified code

/* 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.
 * */
/* Solution 1: Horizontal Bars
 * Take 2: Implementing some comments received from SE:
 * https://codereview.stackexchange.com/questions/205674#205680
 * but sticking to the techniques which have been introduced up to this
 * point in K&R, which means the following is NOT used:
 *      - variable declaration where first initialized,
 *      - assignment of char array constants,
 *      - %*d format specifier,
 *      - <ctype.h>.
 * Some other improvements:
 *      - avoided repeating some code by introducing `readEOF` state,
 *      - improved scaling,
 *      - check whether MAXWIDTH is sufficient to print the smallest
 *          possible chart,
 *      - printing numerical value next to histogram,
 *      - figured out how to print labels better, while sticking to the
 *          techniques introduced so far,
 *      - limited source code width to 72,
 *      - fixed a scaling bug due to flating point precision,
 *      - reverted to storing >MAXLEN count in the last element.
 * */
#include <stdio.h>

#define MAXLEN      10  /* Any word longer than this will get counted in
                         * the >MAXLEN histogram. */
#define MAXWIDTH    72  /* Max. width for chart printout, the whole
                         * chart will be scaled to fit. */

int main()
{
    int c;
    int i, j;
    int histogram[MAXLEN+1]; /* last element will count the over-length
                              * words */
    int alnumCount;
    int readEOF;
    int labelW;
    int maxLabelW;
    int maxWordCount;
    int maxWordCountW;
    float scale;

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

    /* Perform the counting */
    alnumCount = 0;
    readEOF = 0;
    c = getchar();
    while (readEOF == 0) {
        if ((c >= '0' && c <= '9') || 
            (c >= 'a' && c <= 'z') ||
            (c >= 'A' && c <= 'Z'))
            ++alnumCount;
        else {
            if (alnumCount > 0) {
                if (alnumCount <= MAXLEN)
                    ++histogram[alnumCount-1];
                else
                    ++histogram[MAXLEN];
                alnumCount = 0;
            }
        }
        if ((readEOF = (c == EOF)) == 0)
            c = getchar();
    }

    /* Chart Printing Section
     * */
    /* Each histogram will look like:
     * ">NNN |******************** MMM",
     * showing both the label and the histogram value, so we can display
     * accurate information even if the chart is scaled.
     * To be able to plot on a fixed screen width, we must calculate the
     * max. histogram value, the widths of NNN & MMM fields, and finally
     * the scale.
     * */

    /* Find max. histogram value */
    maxWordCount = 0;
    for (i = 0; i <= MAXLEN; ++i) 
        if (maxWordCount < histogram[i])
            maxWordCount = histogram[i];

    /* Calculate histogram value max. width */
    maxWordCountW = 1;
    for (i = maxWordCount;  i >= 10;  i = i/10)
        ++maxWordCountW;

    /* Calculate label max. width */
    maxLabelW = 1;
    for (i = MAXLEN;  i >= 10;  i = i/10)
        ++maxLabelW;

    /* Calculate the scale */
    /* Note - histogram layout: ">NNN |******************** MMM". */
    scale = 1.0*(MAXWIDTH - 1 - maxLabelW - 2 - 1 - maxWordCountW) / 
            maxWordCount;

    /* Fix a scale rounding bug */
    if (scale * maxWordCount < MAXWIDTH - 1 - maxLabelW - 2 - 1 - 
        maxWordCountW)
        scale = scale + 0.000001;

    /* Print the chart only if MAXWIDTH is sufficient to print at least
     * the values */
    if (maxWordCount * scale >= 0)
        /* Print horizontal histogram. */
        /* Row loop */
        for (i = 0; i <= MAXLEN; ++i) {
            /* Print either the " " or ">" for the last histogram */
            if (i < MAXLEN)
                putchar(' ');
            else
                putchar('>');

            /* Calculate the label width */
            labelW = 1;
            for (j = i+1;  j >= 10;  j = j/10)
                ++labelW;

            /* Print blanks as required for lavel alignment and print
             * the label */
            for (j = maxLabelW - labelW; j > 0; --j)
                putchar(' ');
            if (i < MAXLEN)
                printf("%d |", i+1);
            else
                printf("%d |", MAXLEN);

            /* Column loop, print the histogram */
            for (j = 1; j <= scale*histogram[i]; ++j)
                putchar('*');

            /* Print the histogram value */
            printf(" %d", histogram[i]);
            putchar('\n');
        }
    else
        printf("Error: insufficient screen width for print-out.\n");
}

Output when run on the program code

$ ./ch1-ex-1-13-01_Take2 < ch1-ex-1-13-01_Take2.c
  1 |*************************************************************** 103
  2 |*************************************** 64
  3 |************************************************* 81
  4 |***************************** 49
  5 |********************************************* 74
  6 |************************** 43
  7 |****************** 31
  8 |************** 24
  9 |************************* 41
 10 |*********** 18
>10 |************** 23
\$\endgroup\$
  • \$\begingroup\$ If you want to get that reviewed, make it a new question. \$\endgroup\$ – Deduplicator Oct 18 '18 at 11:49
  • 1
    \$\begingroup\$ Didn't intend to go through round 2, just posting here for info. I'll post the vertical variant as a new Q once I'm done with it. \$\endgroup\$ – div0man Oct 18 '18 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.