Explanation of Kragen's fourth C .signature puzzle

Last updated 1999-07-12.

Here's the program:

char b[2][10000],
     *s,
     *t=b,
     *d,
     *e=b+1,
     **p;
main(int c, char **v) {
    int n=atoi(v[1]);
    strcpy(b,v[2]);
    while(n--) {
        for(s=t, d=e; *s; s++) {
            for(p = v+3; *p; p++) 
                if(**p == *s) {
                    strcpy(d,*p+2);
                    d+=strlen(d);
                    goto x;
                }
            *d++=*s;
        x:
        }
        s=t;t=e;e=s;
        *d++=0;
    }
    puts(t);
}

This program runs L-systems, or Lindenmayer systems. It will crash if they expand too much, since it has very limited space for them. The number of generations, the axiom string, and the productions are specified on the command line.

Here's a line-by-line explanation:

char b[2][10000],

Two arrays of 10,000 characters to use to store two generations of the string;

     *s,

a pointer to the symbol being read from the older generation;

     *t=b,

a pointer to the beginning of the older generation, initialized to point to the first one;

     *d,

a pointer to the next symbol to write in the new generation;

     *e=b+1,

a pointer to the beginning of the new generation, initialized to point to the second one;

     **p;

a pointer to a string that we use to iterate through argv.

main(int c, char **v) {
    int n=atoi(v[1]);

The number of generations is read from the first command-line argument;

    strcpy(b,v[2]);

The second command-line argument, the axiom string, is copied into the older-generation space;

    while(n--) {

If n is zero, this loop will not be run; otherwise, this loop will be run one more time than if n were n-1. So the loop will be run n times.

        for(s=t, d=e; *s; s++) {

We initialize the source pointer to point to the beginning of the old generation and the destination pointer to point to the beginning of the new generation; we stop when the source pointer points at a NUL; and each time through this loop, we increment the source pointer.

            for(p = v+3; *p; p++) 

We start p with the third command-line argument; we stop this loop if p points to a null pointer, which Unix puts after the last real command-line argument; we increment p to the next argument each time through the loop.

                if(**p == *s) {

If the first character of that argument is the same as the source character we're looking for a production for,

                    strcpy(d,*p+2);

copy that argument (from its third character on) into the space starting at the destination pointer,

                    d += strlen(d);

and bump the destination pointer forward to point at the NUL after the end of the string we just copied to it.

                    goto x;

And stop looking for more productions, and skip over copying the source symbol to the destination without change.

                }
            *d++=*s;

If we never find a matching production, we just copy the source character to the destination generation and bump the destination pointer.

        x:
        }

Label 'x' is at the end of the loop.

        s=t;t=e;e=s;

Now we need to swap the 'old' and 'new' generations (using s as a scratch space), and

        *d++=0;

make sure the newly 'old' generation is NUL-terminated.

    }

End of generation loop;

    puts(t);
}

. . . and then at the end of the program we output what would otherwise be the next 'old' generation.

Of course this program is easy to crash: give it not enough arguments, or give it production arguments that are only one character long, or just run it out of space.

Kragen's fourth C .signature puzzle | Kragen's home page