# Counting letters program. Notation and optimisation help

I am writing a program in C running on UNIX which counts the number of each letters in a input text file. For a file like this:

The cat sat on the green mat

The output would be like this:

   The letter ’a’ occurs 3 times.
The letter ’c’ occurs 1 times.
The letter ’e’ occurs 4 times.
The letter ’g’ occurs 1 times.
The letter ’h’ occurs 2 times.
The letter ’m’ occurs 1 times.
The letter ’n’ occurs 2 times.
The letter ’o’ occurs 1 times.
The letter ’r’ occurs 1 times.
The letter ’s’ occurs 1 times.
The letter ’t’ occurs 5 times.

5                    *
4     *              *
4     *              *
3 *   *              *
3 *   *              *
2 *   *  *     *     *
2 *   *  *     *     *
1 * * * **    ***  ***
1 * * * **    ***  ***
0 **************************
0 **************************
... abcdefghijklmnopqrstuvwxyz


Where the graph represents the amount of times a letter appears. (If it is more than 10, i simply put a '+' after the 10th row). The code I've currently written to achieve this is as follows: (Haven't found a good way to test for capital letters as well as lowercase yet).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

void drawGraph(int letters[26], char alpha[26]);
void printLetters(int letters[26], char alpha[26]);
void getLetters(FILE *fp, int letters[26], char alpha[26]);

int main(int argc, char *argv[]) {
FILE *fp;
int letters[26] = { 0 };
char alpha[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
int indexedAlpha[256] = { 0 };
int j = 1;

for (i = 97; i <= 127; i++)
{
indexedAlpha[i] = j;
j++;
}

//open file
if ((fp = fopen(argv[1], "r")) == NULL)
{
perror("Cannot open file");
exit(EXIT_FAILURE);
}

getLetters(fp, letters, alpha);
printLetters(letters, alpha);
printf("\n");
drawGraph(letters, alpha);
printf("\n");

return EXIT_SUCCESS;
}

void getLetters(FILE *fp, int letters[26], char alpha[26]) {
int c;
for (int i = 0; (c = fgetc(fp)) != EOF; i++)
{
c = fgetc(fp);
if ( isalpha(c) )
{
for ( int j = 0; j < 26; j++ ) //find which letter it is
{
if( c == alpha[j] )
{
letters[j]++;
break;
}
}
}
}
}

void printLetters(int letters[26], char alpha[26]) {
for( int i = 0; i < 26; i++ )
{
if(letters[i] != 0){
printf("The letter '%c' occurs %d times.\n", alpha[i], letters[i]);
}
}
}

void drawGraph(int letters[26], char alpha[26]) {
int x = 11;
int y;
while(x >= 0)
{
y = 0;
while (y < 2)
{
if (x == 10)
{
printf(" %d ", x);
}
else if (x == 11)
{
printf("    ");
}
else
{
printf("  %d ", x);
}

for( int i = 0; i < 26; i++ )
{
if(letters[i] > 10)
{
printf("+");
letters[i] = 10;
y++; // Break out of while loop
}
else if(letters[i] == x)
{
printf("*");
}
else
{
printf(" ");
}
if (letters[i] == x && y == 1)
{
letters[i] = letters[i] - 1;
}
}
printf("\n");
y++;
}
x--;
}
printf("... ");

for( int i = 0; i < 26; i++ )
{
printf("%c", alpha[i]);
}
}


What I'm looking for is advice and tips on notation, efficiency(In amount of code written and memory usage) and any other good tips/Best practices or better methods i could use to complete this task.

Thanks!

-

Let just say when I first read the question I was very impressed by the graph.
Well done.

Small mistake in reading the file:

char c;
for (int i = 0; !feof(fp); i++)
{
c = fgetc(fp);


This is wrong in all languages. The eof is never set until you read past the eof. The last successful read reads up-to (but not past) the eof. So even if there are no more characters in the file the eof flag is not set (until you try and read the character after eof).

As a result you are suffering a one off error. The loop is executed one time to many. The value of 'c' on the last iteration is EOF truncated to fit into a char.

So the standard patter is to read from the file and see if it works. If it works then you enter the loop:

int c;
for (int i = 0; (c = fgetc(fp)) != EOF; i++)
{


Note we need to change the c from a char into an int to make sure that EOF is not truncated out of the value.

Not an error: But you are implementing an O(1) operation is O(n).

  for ( int j = 0; j < 26; j++ ) //find which letter it is
{
if( c == alpha[j] )
{
letters[j]++;
break;
}


With a little though you can invert the array. So you use the letter to look up its ID.

char alpha[256] =
{  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   //  0->15 ignore
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 16->31 ignore
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 32->47 ignore
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 48->63 ignore
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 64->79 ignore
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 80->95 ignore
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,   // 96->111 a -
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 0, 0, 0, 0, 0,   // 112->127 -z
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   // 128->143 ignore

.. etc

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};  // 240->255 ignore

// Now the lookup becomes:
if (alpha[c] != 0)
{
letters[alpha[c] - 1]++;
}


But do you really care if you count all the characters. I would not (unless there are some serious space constraints). You can just count all the characters. When you print them out you just print the ones you want.

   int letters[256];

....
letters[c]++;   // or maybe letters[tolower(c)]++;
.....

// Now we just need to de reference the count of the letters we are interested in.
for( int i = 0; i < 26; i++ )
{
int count = letters[alpha[i]];
if(count != 0){
printf("The letter '%c' occurs %d times.\n", alpha[i], count);
}
}


Some small tidy up (you seem to have embeded tabs that mess up spacing on this site).

-
Your second solution letter[c-'a'] comments on an assumption of consecutively numbers letters. It is worth noting that your first solution makes an even stronger assumption, one which I do not believe is actually guaranteed by the standard. –  Brian Nov 27 '12 at 15:00
Brian... I don't see the problem with the first solution, whereas your point about the second solution might be valid if we're talking about alternate charsets, etc. The first solution (if chars are treated numerically as unsigned bytes, I forget) should work with any set of bytes imaginable, as long as you map any byte either to zero or their "appropriate" location (plus one) in the count array. The programmer determines the appropriate-ness of the location, and a proper alpha array even allows for the numbering of "classes" of bytes, if desired. –  JayC Nov 27 '12 at 19:58
@Brian: Yes I coded up the hand built array assuming ascii. But the point is not the encoding it is the fact that you can use a look up to do it in O(1). With only a tiny bit of work you can build the array dynamically at run time (so it works for your current encoding). –  Loki Astari Nov 27 '12 at 20:15
@JayC: Fixed concerns with second alternative. –  Loki Astari Nov 27 '12 at 20:26
If i use the inverted array, will this help to catch Uppercase and lower case characters? as aren't their ASCII values different? Also is there any ideas on how i could only print the Y-axis up to the value needed? E.g for the example shown the Y-axis would go only up to 5. Thanks for the great answer already! –  BradStevenson Nov 27 '12 at 22:46

General points:

• Many people, including me, put functions in the opposite order to their use. This avoids having to use prototypes. In your code this would mean putting main at the end.

• make all local functions 'static'. This is not important in single-file programs but is preferable for bigger programs.

• starting functions with the '{' in column 0 is preferable.

• leave a space after keywords consistently (or if you must, don't leave a space, but be consistent).

• you have several points where the level of indenting is excessive to my taste. Nested loops are best avoided in my opinion.

• use of 26 everywhere might be best replaced by a #define constant (upper case)

• note that in a function that takes a 1-D array such as void f(char array[26]); the array size (26) is ignored. The function is the same as void f(char *array);

Detailed remarks:

• note that alpha should be const

• I would define it as const char alpha[] = "abcdefghijklmnopqrstuvwxyz";. This is one byte longer but is briefer and makes printing the alphabet easier too.

• indexedAlpha is not used beyond the initialization loop.

• the error message printed by the call to perror would be better if the failed file name is passed: perror(argv[1]);

in getLetters:

• alpha should be const

• the for loop would be better as a while, since you dont use the loop variable i : while((c = fgetc(fp)) != EOF)

• and delete the call to fgetc in the body of the loop

• the nested for loop in getLetters can be replaced, as discussed by @LokiAstari. That solution is best, but if you were to keep your way of finding a match, this nested loop would belong as a separate simple function.

in printLetters:

• alpha and letters should both be const

in drawGraph:

• printGraph might be more a accurate name

• alpha should be const

• I don't find the function easy to read. Too many loops and nesting levels and variables numbers.

• I dont understand why you want to double the vertical scale. It makes the graph less readable (to me). I'm going to address the function on the basis of one line per count vertically.

• note that the printf format "%2d" prints a number in a field width of 2 - which is what your conditionals at the beginning of the 2nd while loop do.

• the printf(" "); can be extracted outside the loop.

• printing the + line can also be extracted from the loop;

• you can print the graph without modifying the letters array with a little reorganisation.

Here is my version of drawGraph:

static void printGraphLine(const int *letters, char ch, int limit)
{
for (int i = 0; i < 26; i++) {
putchar(letters[i] >= limit ? ch : ' ');
}
printf("\n");
}

static void printGraph(const int *letters, const char *alpha)
{
printf("    ");
printGraphLine(letters, '+', 11);

for (int x = 10; x >= 0; --x) {
printf(" %2d ", x);
printGraphLine(letters, '*', x);
}
printf("... %s\n", alpha);
}

int main(int argc, char *argv[])
{
const char alpha[] = "abcdefghijklmnopqrstuvwxyz";
...


So did I cheat? My code is much simpler but prints only one line per count instead of the two yours prints; it breaks the original "contract". You could double-up the printGraphLine calls if you wanted the original behaviour.

Simplicity is king in my book (and I recommend it to be so in yours too) and if I can do almost the same job for half the code, I will, unless there is a strong reason not to. Even if it doesn't do exactly what I started out wanting to do. This is perhaps a philosophical point and you must draw your own conclusions :-)

-