Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site cmu-cs-theory.ARPA
Path: utzoo!linus!philabs!cmcl2!seismo!rochester!cmu-cs-pt!cmu-cs-theory!guy
From: guy@cmu-cs-theory.ARPA (Guy Jacobson)
Newsgroups: net.puzzle
Subject: Re: abcde
Message-ID: <203@cmu-cs-theory.ARPA>
Date: Tue, 23-Apr-85 02:14:10 EST
Article-I.D.: cmu-cs-t.203
Posted: Tue Apr 23 02:14:10 1985
Date-Received: Fri, 26-Apr-85 20:58:27 EST
References: <372@ho95b.UUCP>
Organization: Carnegie-Mellon University, CS/RI
Lines: 66

Here is a little program I wrote to determine the shortest list
of words which includes the alphabet (in order) as a subsequence.
Try "a.out < /usr/dict/words" for enlightenment.

-- Guy

/* Alphabet subsequence program by Guy Jacobson, April 22 1985 */

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

#define ALPHA	('z' - 'a' + 1)
#define MAXLEN	32

char bonus[ALPHA];
char bonusword[ALPHA][MAXLEN];

main ()
{
    char word[MAXLEN];
    int i;

    while (gets (word))
	addword (word);

    for (i = 0; i < ALPHA; i += bonus[i])
        printf ("%s ", bonusword[i]);

    printf ("\n");
    exit (0);
}

addword (word) char *word;
{
    static char boon[ALPHA + 1];

    char    nonzerobonusletters[ALPHA];
    register char  *nz = nonzerobonusletters;
    register char  *p;
    register char   ch;

    for (p = word + strlen (word) - 1; p >= word; --p) {
	ch = *p;
	if (isalpha (ch)) {
	    if (isupper (ch))
		ch = tolower (ch);
	    ch -= 'a';
	    if (boon[ch] == 0)
		*nz++ = ch;
	    boon[ch] = boon[ch + 1] + 1;
	}
    }

    while (--nz >= nonzerobonusletters) {
	char    letter = *nz;
	char    thisbonus = boon[letter];

	if (thisbonus > bonus[letter]) {
	    bonus[letter] = thisbonus;
	    strcpy (bonusword[letter], word);
	}
	boon[letter] = 0;
    }
}