// bek.c: C rendering of Beklemishev's worm process.
// Usage e.g.: bek 102  initializes worm to string "102"
// Vaughan Pratt, Stanford University, May 21, 2011

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

int
main(int argc, char *argv[]){		// command line count and parameters
    int m, i, sl;			// stage m, i < m, suffix length sl
    char *w = malloc(1e9), *we, *tr;	// allocate storage for 1 GB worm
    we = w+strlen(strcpy(w,argv[1]))-1;	// initialize worm, we = worm end
    for (m = 1; we >= w; m++) {		// stages 1,2,...,m,...
    	if (*we == '0')			// if last char of w is zero
	    *we-- = 0;			// then delete it
	else {
	    for (tr = we - 1; tr >= w && *tr >= *we; tr--); // find suffix
	    (*we)--;			// decrement last char
	    for (i = 0, sl = we - tr; i < m; i++, we += sl)
	    	strncpy(we + 1, tr + 1, sl); // append m copies of suffix to w
	}
	printf("%d: %s\n", m, w);	// diagnostic
    }
    return 0;				// indicate successful termination
}

/* In pseudocode (i.e. English):

Let w be a word over some n-letter alphabet {0,1,2,...,n-1}
At stage m, beginning from m = 1:
If w is empty then halt;
else if the last character of w is 0 then delete it;
else {
1.  Identify the longest suffix of w all of whose characters are at
    least as large as the last character of w.
2.  Decrement the last character of w (and hence of the suffix).
3.  Append m copies of the suffix to w.
}

Theorem (Beklemishev 2003): This process always halts.
*/