If Arthur C. Clarke’s story The Nine Billion Names of God were true, then it seems rather pointless to plow through all 9,000,000,000 permutations to find one matching name. In fact, the exercise is more like a brute-force password cracking program than some celestial name search. What if the monks already knew the name? That would save time and effort.

Assume that out of the billions of letter combinations, the monks knew that the Big Guy’s holy password contained six letters, all lower case. If so, you could craft a program that would spin through all letter combinations and eventually spit out the match. This technique is pretty much how password cracking programs work, albeit at a very crude level.

The following code demonstrates how nested for loops can permute letter combinations in an attempt to match a preset password, zzyxx.

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

int main()
{
    char password[6] = "zzyxx";
    char brute[6] = "\0";

    
    for(brute[0]='a';brute[0]<='z';brute[0]++)
        for(brute[1]='a';brute[1]<='z';brute[1]++)
            for(brute[2]='a';brute[2]<='z';brute[2]++)
                for(brute[3]='a';brute[3]<='z';brute[3]++)
                    for(brute[4]='a';brute[4]<='z';brute[4]++)
                        if( strcmp(brute,password)==0 )
                        {
                            printf("%s -> %s\n",brute,password);
                            return(0);
                        }

    return(0);
}

Line 6 defines the password, the target text to match.

In Line 7, the brute[] char buffer is initialized to null characters. This step is important! if you don’t initialize the buffer, the strings may never match.

The point of all the for loops is to fill the brute[] array with letters aaaaaa through zzzzzz. At each permutation, the strcmp() function checks to see whether the letters match those stored in string password. If so, the looping madness stops and the result is displayed:

zzyxx -> zzyxx

The big problem with this brute force method is time; nested loops consume a lot of processing power. The more loops you have, the slower the code runs. Eventually, adding yet another loop to the nest makes the program crawl.

Back in the old microcomputer days, programmers used loops to delay execution. On my TRS-80, a for loop that counted to 2400 would pause the program one second. As processor technology improved, these timing loops were dropped in favor of using the computer’s internal clock. In fact, many early PC games can no longer be played on a modern PC because their timing loops run too quickly.

Another problem is a lack of flexibility: You must re-write the code to accommodate a longer or shorter target string. One solution to handle that issue is to use recursion instead of writing nested loops. I’ll present that solution in next week’s Lesson.