11
\$\begingroup\$

This will test if a user entered an pangram (every letter in alphabet used at least once), however with 4 for loops there's got to be a better algorithmic approach or with the language of C itself.

pangram.c

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

 typedef enum { true, false } bool;

 typedef struct node{
     char letter;
     bool exists;
 } node;

 int main(int argc, char *argv[]){
     int SIZE = 500;
     char input[SIZE];

     printf("Enter your pangram: ");
     fgets(input, SIZE, stdin);

     // 26 letters
     node alphabet[26];
     int i = 0;
     for(char c='a'; c<='z'; ++c, i++){
         alphabet[i].letter = c;
         alphabet[i].exists = false;
     }


     for(int i=0; i<SIZE; i++){
         for(int j=0; j<27; j++){
             if(isalpha(input[i]) && input[i] == alphabet[j].letter){
                 alphabet[j].exists = true;
             }
         }
     }

     for(int i=0; i<27; i++){
         if(alphabet[i].exists==false){
             printf(" no pangram, missing letter.\n");
             return 1;
         }
     }

     printf("you've entered a pangram.\n");

     return 0;
 }

command line:

>> gcc -o pangram pangram.c -std=c99; ./pangram
Enter your pangram: this should fail
 no pangram, missing letter.

>> gcc -o pangram pangram.c -std=c99; ./pangram
Enter your pangram: the quick brown fox jumps over the lazy dog
you've entered a pangram.
\$\endgroup\$
  • \$\begingroup\$ Detail: "every letter in alphabet" --> Better to be specific. Although it certainly appears to be A-Z, how portable should code be? Which alphabet? A-Z or the alphabet of the locale which may include other characters? In the common default "C" locale, it is A-Z. \$\endgroup\$ – chux Feb 22 '18 at 20:54
10
\$\begingroup\$

This is a good challenge. Your code is clear and easy to read.

Some things can be improved, in addition to those mentioned in Roland's answer.

Choose your main()

As we're not using argc and argv, we can use the simpler int main() that takes no arguments.

Alternatively (and this makes for easier testing), you could use command-line arguments, and only ask for input if none were given:

int main(int argc, char *argv[])
{
    if (argc < 2) {
        char input[500];
        printf("Enter your pangram: ");
        fflush(stdout);
        if (!fgets(input, sizeof input, stdin)) {
            perror("fgets");
            return 1;
        }
        return test_pangram(input);
    } else {
        int failures = 0;
        for (int i = 1;  i < argc;  ++i) {
            failures += test_pangram(argv[i]);
        }
        return failures;
    }
}

I've separated the action of the program into a new function test_pangram() so we can call it from both branches of this.

Note that I've called fflush() between writing output and reading input. This ensures that the prompt is visible to the user in time.

A bug

This is wrong:

 /* BUG */
 for(int i=0; i<SIZE; i++){
     /* code that uses input[i] */
 }

When we read input using fgets() it wrote a null-terminated string to input - everything after the NUL character is uninitialized and using it is undefined behaviour. It's quite possible that the unspecified values we read from there could cause a false-positive result (if they fill in the characters missing from the actual input). We need to stop the loop when input[i] is '\0':

 for(int i=0;  input[i];  i++){
     /* code that uses input[i] */
 }

Assumptions about letters

This code makes a critical assumption:

node alphabet[26];
int i = 0;
for(char c='a'; c<='z'; ++c, i++){
    alphabet[i].letter = c;
    alphabet[i].exists = false;
}

The assumption is that the letters a...z have contiguous character codes. But C doesn't guarantee this, and there are systems where 'z'-'a' is not 25. You're probably using ASCII, or Latin-1, or UTF-8, as your encoding, where your assumption turns out lucky, but if your code is compiled for an EBCDIC-based machine (for example), you will write beyond the end of alphabet during this loop. That's not a Good Thing.

A safer way to approach this is to do the processing in the opposite order: instead of looking up each character as you see it, we can simply keep a note of each different character seen (letter or otherwise), and afterwards check that all the letters are marked. That requires a bit more storage, but it will be a bit more efficient:

int test_pangram(const char *input)
{
    char seen[UCHAR_MAX+1] = { 0 };
    for (const char *p = input;  *p;  ++p) {
        unsigned char c = (unsigned char)*p;
        seen[c] = 1;
    }

    for (unsigned int i = 0;  i < sizeof seen;  ++i) {
        if (!seen[i] && islower(i)) {
            /* missing a required letter */
            return 1;
        }
    }
    return 0;
}

There are a few things to note here:

  • I use sizeof seen so I can get the compiler to provide the right value where it's needed.
  • I've used a pointer p rather than indexing into input - it's exactly equivalent, but shorter and more idiomatic C.
  • Characters all need to be converted to unsigned char before being used with the <ctype.h> functions - this is one of the annoying constraints of those functions.
  • Because I've used isalpha(), we stand a better chance of making this work in locales other than English - e.g. Danish, where æ, ø, å and ü are letters, too.

Consider uppercase characters

Traditionally, pangrams ignore the case of characters. You should be able to modify the program so that uppercase characters count towards seen. Possibly the simplest way to do this is to count both upper and lower versions of each character (toupper() and tolower() just return their inputs for the non-alphabetic characters). Then remove the islower(i) test from the second loop.


Modified program

Here's my take on this problem, with the changes I've proposed:

#include <ctype.h>
#include <limits.h>
#include <stdio.h>
/* return true if it's a pangram */
int test_pangram(const char *input)
{
    char seen[UCHAR_MAX+1] = { 0 };
    for (const char *p = input;  *p;  ++p) {
        unsigned char c = (unsigned char)*p;
        seen[toupper(c)] = 1;
        seen[tolower(c)] = 1;
    }

    for (unsigned int i = 0;  i < sizeof seen;  ++i) {
        if (!seen[i] && isalpha(i)) {
            printf("Not a pangram - missing '%c'.\n", (char)i);
            return 0;
        }
    }

    printf("You've entered a pangram.\n");
    return 1;
}
int main(int argc, char *argv[])
{
    if (argc < 2) {
        char input[500];
        printf("Enter your pangram: ");
        fflush(stdout);
        if (!fgets(input, sizeof input, stdin)) {
            perror("fgets");
            return 1;
        }
        return !test_pangram(input);
    } else {
        int failures = 0;
        for (int i = 1;  i < argc;  ++i) {
            failures += !test_pangram(argv[i]);
        }
        return failures;
    }
}
\$\endgroup\$
  • \$\begingroup\$ The return value 1 for "not a pangram" looks strange. The "0 means success and 1 means failure" should only be used in main. All other functions should either return a bool or the combination "0 means success and -1 means failure". \$\endgroup\$ – Roland Illig Feb 22 '18 at 12:55
  • \$\begingroup\$ Yes, makes sense. It's pretty easy to invert the result, and have failures += !test_pangram(s) instead. I might edit for that. \$\endgroup\$ – Toby Speight Feb 22 '18 at 13:05
  • \$\begingroup\$ I havn't got through reading everything, just skimming this real quick i'm curious why the loop would exit with ` for(int i=0; input[i]; i++)? Wouldn't you want something like input[i] == '\0'` for the condtion? \$\endgroup\$ – Tony Feb 22 '18 at 13:19
  • \$\begingroup\$ I think there's an off-by-one error in the size of seen; if UCHAR_MAX is 255, then the array should be 256 bytes. As for localization (and lower/upper); C is so under-equipped that I would either not mention it OR warn the unsuspecting beginner that toupper/tolower/isalpha should NOT be used on many non-European languages. Chinese requires more than 256 values. \$\endgroup\$ – Matthieu M. Feb 22 '18 at 13:52
  • 1
    \$\begingroup\$ @Tony, the exit condition for the loop works as follows: we want the loop to keep going while input[i] != '\0'. Writing just input[i] is a shortcut to say the same thing (because '\0' is zero, and zero is false). It's fairly idiomatic in C and C++, particularly when using pointers; I've done the same with for (const char *p = input; *p; ++p). The value of *p is false when p points to the NUL terminator of the string (and true before that point). \$\endgroup\$ – Toby Speight Feb 22 '18 at 14:32
14
\$\begingroup\$

Please never define true to have the value 0, since that value is reserved for the name false. Just include <stdbool.h> instead of defining the type yourself.

Do not call any function from <ctype.h> with a char argument since that can easily lead to undefined behavior.

In the call to fgets fails, the input array may be uninitialized, which would also lead to undefined behavior.

Accessing alphabet[26] leads to undefined behavior since there valid array indices go from 0..25.

The rest of your code looks well-organized and is easy to read. Congratulations on that.

For your primary question of solving the pangram with fewer than 4 for loops, you can find at least 10 different solutions by searching the web since the pangram is a classical programming task.

Forget the above paragraph. I just searched for "pangram c" and found only crappy solutions, and telling these apart from the good ones is impossible for a beginner.

One idea is to remember for each letter whether it was found it not:

bool found[26] = { false };   // This initializes all 26 values at once, but only works for "zero" values.
int remaining = 26;

for (size_t i = 0; input[i] != '\0'; i++) {
    char ch = input[i];

    if ('a' <= ch && ch <= 'z') {
        if (!found[ch - 'a']) {
            found[ch - 'a'] = true;
            remaining--;
        }
    }
}

If, at the end of the loop, there is no remaining character, you have found them all, and the input is a pangram. All with a single loop.

Note: the code I suggested only works when all 26 letters are defined in a contiguous block of the character set. On all modern systems this is the case. When working with IBM machines and EBCDIC encoding, this will not work. On Rosetta Code, the code is perfect and also handles these exotic cases. It uses the same idea and takes care of everything. It looked complicated at first sight, therefore I preferred to explain the basic idea first. But now you should be able to understand the code over there.

\$\endgroup\$
  • 3
    \$\begingroup\$ Addressing a beginner, you may want to expand on <ctype.h> functions with a char argument. \$\endgroup\$ – vnp Feb 22 '18 at 5:13
  • \$\begingroup\$ @vnp I added a link related to that topic. Sadly I didn't find any good reference documentation for this topic that clearly explains how to use ctype.h correctly. \$\endgroup\$ – Roland Illig Feb 22 '18 at 13:23
  • \$\begingroup\$ If remaining is 0 you can just break out of the loop. \$\endgroup\$ – ChatterOne Feb 22 '18 at 13:43
  • \$\begingroup\$ @ChatterOne: oh, you're right. I'm leaving the code as-is for now to keep it as simple as possible. "First get it right, then optimize". :) \$\endgroup\$ – Roland Illig Feb 22 '18 at 14:46
  • 2
    \$\begingroup\$ Ooh, I would be careful with the comment // This initializes all 26 values at once. Makes it look like you can change false to true to initialize all of them with true. \$\endgroup\$ – pipe Feb 22 '18 at 19:30
3
\$\begingroup\$

Since you're asking about a better algorithm I will point out that there is a more efficient, albeit perhaps less readable, way to approach the problem.

There are only twenty-six letters in the alphabet. One approach would be to assign each letter to one bit of an integer. After checking a proposed pangram, bits 0 - 25 should all be set. If those bits of an integer are set, the value will be (2 to the 26) minus 1.

Because, as other answers pointed out, the letters may not be adjacent in the character set, we first build a translation table that goes from letters to bit masks.

    int32_t masks[UCHAR_MAX] = { 0 };
    int32_t index = 0;

    // build translation table
    for (unsigned char c = 0; c < UCHAR_MAX; c++) {
        if (isalpha(c) && islower(c)) masks[c] = 1 << index++;
    }

This creates an array whose elements are all zero, except for the ones corresponding to the letters 'a' through 'z', whose entries receive a 1 shifted left 0 times, a 1 shifted left 1 time, and so on. Thus, the values 1, 2, 4, 8, 16, ... all the way up to 33,554,432.

When it is time to test a proposed pangram, we mask these values together, first converting the character to lower case so that we take upper case letters in our pangram into account:

    int32_t total = 0;
    for (const char *p = proposal; *p; p++) {
        total |= masks[tolower((unsigned char) *p)];
    }

This takes each character, casts it to unsigned because tolower expects an int and we don't want negative values from signed chars to foul us up, converts it to lower case if possible (if not, it just returns the original value unmodified), and looks up the mask from our translation table.

Now, our translation table has zeroes for all characters that are not lower case letters. We OR these values together into total. The letters will cause their respective bits to be set; the zeroes will be ignored.

When this is complete, total will have the value (2 to the 26) minus 1 if and only if the string was a pangram; if it wasn't, the zero bits could be used to detect which letters were missing, if so desired.

Here is the complete program:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

#define SIZE 512
// 2 to the 26 minus 1:
#define TARGET ((1 << 26) - 1)

int main() {
    int32_t masks[UCHAR_MAX] = { 0 };
    int32_t index = 0;

    // build translation table
    for (unsigned char c = 0; c < UCHAR_MAX; c++) {
        if (isalpha(c) && islower(c)) masks[c] = 1 << index++;
    }
    assert(index == 26);

    char proposal[SIZE];

    do {
        fputs("Enter proposed pangram: ", stdout);
        fflush(stdout);
        fgets(proposal, SIZE, stdin);

        if (strlen(proposal) > 1) {
            int32_t total = 0;
            for (const char *p = proposal; *p; p++) {
                total |= masks[tolower((unsigned char) *p)];
            }
            if (total == TARGET) puts("you've entered a pangram.");
            else puts(" no pangram - missing letter.");
        }
    } while (strlen(proposal) > 1);

    return 0;
}

I believe this code will be correct in the C locale where there are only 26 letters. If in another locale there are more than 32 unsigned chars for which isalpha(c) && islower(c) returns true, it may give unpredictable results. I have added an assert to ensure the expectation that there are only 26 letters is not violated.

\$\endgroup\$
  • 1
    \$\begingroup\$ Off by 1. masks[UCHAR_MAX] --> masks[UCHAR_MAX + 1u] and for (unsigned char c = 0; c < UCHAR_MAX; ... --> for (unsigned c = 0; c < UCHAR_MAX + 1u; c++) { or there abouts. \$\endgroup\$ – chux Feb 22 '18 at 20:22
  • \$\begingroup\$ Why if (isalpha(c) && islower(c)) and not just if (islower(c))? \$\endgroup\$ – chux Feb 22 '18 at 20:23
  • \$\begingroup\$ Higher portable code would insure 32-bitness 1 << index++; --> (uint32_t)1 << index++; or the like. Same for 1 << 26. \$\endgroup\$ – chux Feb 22 '18 at 20:26

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.