ACSU Programming Competition

27 September 1997

Results and Solutions


Problems

The problems are available as a Microsoft Word document. (You may have to shift-click on the link to get it to download properly.)

This year, I wrote the four problems myself. I am concerned that Problem 4 was the only one with any correct submissions. Thus, I would really like feedback from participants about the problems: level of difficulty, clarity, length, etc. One complaint was that in C++ it is difficult to detect a blank line. (Just use the istream::readline method.) Another complaint was that the problems were too long. I would welcome any additional feedback.

I would like to get a team together to send to the regional ACM competition. Anyone who is interested should just send me e-mail.


Results

The top three contestants were:
  1. Harold Fox, 1 correct, 41 minutes
  2. Wilson Huang, 1 correct, 72 minutes
  3. Jeff Raguza, 1 correct, 98 minutes
Problem 4 had ten correct submissions.

There were 38 participants.


Solutions

I wrote all my solutions in C.

Problem 1 -- Perpetual Motion

There were no correct submissions to this problem. One person did submit a solution, which was correct when the game was won or the game was blocked. However, when the player got bored, the round in which that occurred was off by one. This means that the contestant did not try the sample data given in the problem statement.

Here is my solution:

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

/***************************************************************************
Perpetual Motion

Play the Solitaire game Perpetual Motion. Given an initial deck, indicate
whether the game was won, blocked, or we got bored.
***************************************************************************/

#define MAX 80   /* maximum line length */
#define NUM 52   /* number of cards */
#define STOP 100 /* if no cards removed for this many rounds, stop */

void play(char deck[MAX]);

/***************************************************************************
main
***************************************************************************/
void main(void)
{
char line[MAX];
int i;
int seed;

for (i = 1; ; i++)
	{
	/* Read a line containing the cards. If the line is blank, it's the
	   end of input. */
	if (gets(line) == NULL)
		/* EOF detected. End of input. */
		return;
	if (strlen(line) == 0)
		/* Blank line detected. End of input. */
		return;
	/* Play the game, and do appropriate output. */
	printf("Game %2d: ", i);
	play(line);
	}
}

/***************************************************************************
play

Play the card game, and print the appropriate message.
***************************************************************************/
void play(char deck[MAX])
{
char pile[4][NUM];
int index[4];
char deck2[NUM];
int n = 52;
int i, j, k;
int same, removed;
int round, no;

#define JUNK 'X'
#define card(q) (index[q] > 0 ? pile[q][index[q]-1] : JUNK)

round = 0;
for (round = 1; ; round++)
	{
	/* Initialize all piles to empty. */
	for (j = 0; j < 4; j++)
		index[j] = 0;
	removed = 0;
	/* Deal out the cards onto the piles. Remove cards and move to left
	   if possible. */
	for (i = 0; i < n; i += 4)
		{
		/* Deal 4 cards, face up, one per stack. */
		for (j = 0; j < 4; j++)
			{
			pile[j][index[j]] = deck[i+j];
			index[j] ++;
			}
		/* Check if cards can be removed or collected. */
remove:
		/* Check if cards can be removed. */
		if (card(0) != JUNK)
			{
			same = 1;
			for (j = 1; j < 4; j++)
				if (card(j) != card(0))
					same = 0;
			if (same)
				{
				for (j = 0; j < 4; j++)
					index[j] --;
				removed = 1;
				goto remove;
				}
			}
collect:
		/* Check if cards can be moved to left. */
		for (j = 0; j < 3; j++)
			if (card(j) != JUNK)
				for (k = j+1; k < 4; k++)
					if (card(j) == card(k))
						{
						pile[j][index[j]] = card(k);
						index[j] ++;
						index[k] --;
						goto collect;
						}
		/* Cannot remove or collect. Deal 4 more cards. */
		}
	/* Remake the deck from the piles. */
	n = 0;
	for (j = 0; j < 4; j++)
		for (k = 0; k < index[j]; k++)
			deck2[n++] = pile[j][k];
	/* Check if we've won. */
	if (n == 0) break;
	/* We haven't won. Check if we're blocked or bored. */
	if (! removed)
		{
		/* Make sure decks haven't repeated. */
		same = 1;
		for (i = 0; i < n; i++)
			if (deck[i] != deck2[i])
				same = 0;
		if (same) break;
		/* If too many rounds with same number of cards, stop. */
		no ++;
		if (no == STOP) break;
		}
	else
		/* There have been 0 rounds with same number of cards. */
		no = 0;
	/* Copy the secondary deck into the primary deck. */
	for (i = 0; i < n; i++)
		deck[i] = deck2[i];
	}

/* Print winning or losing message. */
if (n == 0)
	printf("Won after %d rounds.\n", round);
else if (same)
	printf("Blocked after %d rounds with %d cards left.\n", round, n);
else
	printf("Got bored after %d rounds with %d cards left.\n", round, n);
}
The test input was:
556Q7QQ99A26KK839700444483356AA379JA08225KJQ786J0K2J
783QA5837JA5035K39Q46200K095J62Q4A2944Q7JK27KJ98A668
3604A97A20K935854J76884QK94K36223AQJAQ568Q05J2K7907J
J2JAAQ34Q95A736765K420972864K3820Q9386058A4KQJJ09K57
758A425KK60635729533J9A496KQ07QJ20A884K9Q0J4J7A2Q368
53823A9A670K96KJA498K575Q2Q7JK8J00JQ3794AQ2243064658
K6J74A6392A904A58923KKJ0JQ7K59Q6230Q8A658QJ473724580
A04QJ24A777239Q5J078A42686J495K039582K50QKQK6633A89J
Q24375JJ66Q75A74629A24QK859J9J4AK380A0028K35608KQ739
84Q9A232634J690J7Q7556Q90KA8396A048A5JK322KK7QJ70584
44359Q9A7JAA85238K7J8A55Q400602Q7J0QKK629J869632743K
49K79055Q3KQJA2953J824J029066386476J3AA8Q8Q7024K75AK
3K46QK076K8A825692QAK5239786504AJQA97J30907Q824J3J45
5Q5J3J2QAK23KAK956776047324K6870AQ4J20JQ43569880899A
4906AK56374Q907652KJ07485323K8AJJ5Q62Q89KQ72A49308JA
484Q6403JKJ793AA757608Q905A60J23Q35Q7A8K496JK822925K
K649A3Q5KA7652A0923QJ6K88A72JQ050K497J35836089Q424J7
The correct output was:
Game  1: Won after 17 rounds.
Game  2: Won after 15 rounds.
Game  3: Won after 28 rounds.
Game  4: Won after 51 rounds.
Game  5: Won after 42 rounds.
Game  6: Won after 42 rounds.
Game  7: Blocked after 23 rounds with 12 cards left.
Game  8: Blocked after 49 rounds with 12 cards left.
Game  9: Blocked after 45 rounds with 16 cards left.
Game 10: Blocked after 85 rounds with 12 cards left.
Game 11: Blocked after 41 rounds with 12 cards left.
Game 12: Blocked after 44 rounds with 8 cards left.
Game 13: Got bored after 151 rounds with 16 cards left.
Game 14: Got bored after 138 rounds with 16 cards left.
Game 15: Got bored after 127 rounds with 16 cards left.
Game 16: Got bored after 145 rounds with 16 cards left.
Game 17: Got bored after 147 rounds with 20 cards left.
According to some tests I ran, you have about a 15% chance of winning this particular version of Solitaire.

Problem 2 -- Arithmetic Maze

Here is my solution:
#include < stdio.h >
#include < stdlib.h >
#include < string.h >

/************************************************************************
Arithmetic Maze

A maze is described by a series of one-way edges. Each edge has an operation
(add, subtract, multiply, or divide) and a value associated with it. Find
the "best" path from the first node to the last. The best path is the one
with the highest value, when travelling along the path and performing the
operations (beginning with 0). If two paths result in the same value, then
the shorter one is preferred. If two paths have the same value and the same
length, then it doesn't matter which one is output.
************************************************************************/

#define MAX 80    /* maximum line length */
#define MSG 6     /* maximum length of points description of any edge */
#define N   50    /* maximum number of nodes */
#define M   100   /* maximum number of edges */

typedef enum { ADD, SUB, MULT, DIV } Operation;

typedef struct
	{
	int from;
	int to;
	Operation op;
	int val;
	} EdgeType;

int read_maze(int *n, int *m, EdgeType edges[M]);
EdgeType parse_edge(char line[MAX], int *n);
void search(int n, int m, EdgeType edges[M]);

/************************************************************************
main
************************************************************************/
void main(void)
{
int n;               /* number of nodes */
int m;               /* number of edges */
EdgeType edges[M];   /* array of edges */
int set = 0;

while (read_maze(&n, &m, edges))
	{
	printf("Maze %d\n", set+1);
	search(n, m, edges);
	printf("\n");
	set ++;
	}
}

/************************************************************************
read_maze

Read a maze. Return 1 if the read was successful.
************************************************************************/
int read_maze(int *n, int *m, EdgeType edges[M])
{
char line[MAX];
int count = 0;

/* Initialize number of nodes and edges to zero. */
*m = *n = 0;

/* Read edge descriptions until the end of file or a blank line. */
while (gets(line) && strlen(line))
	/* Parse an edge description. */
	edges[count++] = parse_edge(line, n);

/* Return 1 iff a maze was successfully read. */
if (count == 0)
	return 0;
*m = count;
return 1;
}

/************************************************************************
parse_edge

Given an edge description, extract the source and destination of the edge,
the operation performed while crossing it, and its value. Also, determine
how many edges there are.
************************************************************************/
EdgeType parse_edge(char line[MAX], int *n)
{
char str[MSG];
EdgeType ret;

/* Read the source and destination nodes. */
sscanf(line, "%d %d %s", &(ret.from), &(ret.to), str);
/* Record the number of nodes. */
if (ret.from >= *n)
	*n = ret.from + 1;
if (ret.to >= *n)
	*n = ret.to + 1;
/* Process the operation. */
switch (str[0])
	{
	case '+' : ret.op = ADD; break;
	case '-' : ret.op = SUB; break;
	case '*' : ret.op = MULT; break;
	case '/' : ret.op = DIV; break;
	default : printf("Unrecognized message '%s'\n", str); exit(1);
	}
/* Process the value. */
ret.val = atoi(str+1);

return ret;
}

/************************************************************************
search

Perform a depth-first search to find the best path from node 0 to node
n-1. The best path is the one with the highest score. If two paths have
the same score, then the shorter path is better.
************************************************************************/
void search(int n, int m, EdgeType edges[M])
{
/* We're really cool, so we'll manage our own stack. None of this so-called
   recursion. */

typedef struct
	{
	int loc;    /* current node number */
	int score;  /* current score */
	int edge;   /* edge used to get to this node */
	int next;   /* next edge to look at */
	} State;

State state[N+1];   /* stack */
int s = 0;          /* length of our stack */
State best[N+1];    /* best path found so far */
int b = -1;         /* length of best path found so far */
int used[M];        /* array indicating which edges have been used */
int e;
int i;

/* Define the initial state. We start at node 0 with a score of 0. We did not
   use any edges to get here. The next edge to look at is edge 0. */
state[0].loc = 0;
state[0].score = 0;
state[0].edge = -1;
state[0].next = 0;

/* Mark all the edges as unused. */
for (i = 0; i < m; i++)
	used[i] = 0;

/* Do the depth-first search. */
while (s >= 0)
	if (state[s].loc == n-1)
		{
		/* We have found a path to the end. */
		if ((b == -1) || (state[s].score > best[b].score) ||
			((state[s].score == best[b].score) && (s < b)) )
			{
			/* This path is the first one, or it's better than the old path,
			   or it's the same score but shorter, then keep it. */
			for (i = 0; i <= s; i++)
				best[i] = state[i];
			b = s;
			}
		/* Pop this state off the stack. */
		if (state[s].edge >= 0)
			used[state[s].edge] = 0;
		s --;
		}
	else if (state[s].next == m)
		{
		/* We have looked at all edges. Pop this state off the stack. */
		if (state[s].edge >= 0)
			used[state[s].edge] = 0;
		s --;
		}
	else
		{
		/* Look at the next edge, and take it if possible. */
		/* Remember which edge we're currently considering. */
		e = state[s].next;
		/* Next time, we will consider the next edge. */
		state[s].next ++;
		/* Make sure this edge starts where we're currently located. */
		if (edges[e].from == state[s].loc)
			/* The next edge does start on our node. Make sure we haven't
			   already used this edge. */
			if (! used[e])
				/* We haven't used this edge yet. Push a new state onto the
				   stack. */
				{
				used[e] = 1;  /* Mark this edge as used. */
				s ++;
				state[s].loc = edges[e].to;
				state[s].score = update(state[s-1].score, edges[e]);
				state[s].edge = e;
				state[s].next = 0;
				}
		}

/* Print out the best path. */
if (b == -1)
	printf("There is no path.\n");
else
	for (i = 0; i <= b; i++)
		printf("%3d: node = %d, score = %d\n", i+1, best[i].loc, best[i].score);
}

/************************************************************************
update

Given a current score and an edge type, return the score obtained by
travelling across that edge.
************************************************************************/
int update(int score, EdgeType edge)
{
int s = score;

switch (edge.op)
	{
	case ADD : s += edge.val; break;
	case SUB : s -= edge.val; break;
	case MULT : s *= edge.val; break;
	case DIV : s /= edge.val; break;
	default : printf("Unrecognized operation\n"); exit(1);
	}
return s;
}
The test input was:
0 1 +1
0 2 -1
1 3 *2
2 4 /3
3 5 +1
4 5 +10

1 0 +999
0 0 -999

0 1 +1
0 2 +2
0 3 +3
1 4 *2
2 5 *3
3 6 +5
4 7 +2
5 7 -1
5 8 +1
6 8 -3
7 3 +1
7 9 *2
8 1 +2
8 9 /2

0 1 -1
1 0 -1
0 2 +1
2 0 +2
0 3 +1
3 0 +1
0 4 /2
4 0 *2
4 5 +1
5 4 *2
4 6 *2
6 4 +1
4 7 +1
The correct output was:
Maze 1
  1: node = 0, score = 0
  2: node = 2, score = -1
  3: node = 4, score = 0
  4: node = 5, score = 10

Maze 2
There is no path.

Maze 3
  1: node = 0, score = 0
  2: node = 2, score = 2
  3: node = 5, score = 6
  4: node = 7, score = 5
  5: node = 3, score = 6
  6: node = 6, score = 11
  7: node = 8, score = 8
  8: node = 1, score = 10
  9: node = 4, score = 20
 10: node = 7, score = 22
 11: node = 9, score = 44

Maze 4
  1: node = 0, score = 0
  2: node = 2, score = 1
  3: node = 0, score = 3
  4: node = 3, score = 4
  5: node = 0, score = 5
  6: node = 4, score = 2
  7: node = 5, score = 3
  8: node = 4, score = 6
  9: node = 6, score = 12
 10: node = 4, score = 13
 11: node = 7, score = 14

Problem 3 -- Class Schedule

Here is my solution:
#include < stdio.h >
#include < stdlib.h >
#include < string.h >

/***************************************************************************
Class Sorter

Read in a list of classes and their prerequisites. Each line is of the form
	 :   ...
for some number of prerequisites (possibly 0). Print out the order in which
the classes must be taken, so that the prerequisite requirement is satisfied.
If two classes could be taken at the same time, take the one with the lowest
number first; if the numbers match, take the one with the alphabetically
highest department first.
***************************************************************************/

#define NUM 100    /* maximum number of classes */
#define MAX 80     /* maximum line length */
#define NAME 8     /* maximum length of a class name */

void initialize(char pre[NUM][NUM], int *count);
void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1],
	int *count);
int get_word(char line[MAX], char temp[MAX], int *i);
int valid(char c);
int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count);
void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count);
int compare(char a[], char b[]);
int number(char name[]);

/***************************************************************************
main
***************************************************************************/
void main(void)
{
char pre[NUM][NUM];
char name[NUM][NAME+1];
char line[MAX];
int count;
int set = 0;
char *ret;

initialize(pre, &count);
do {
	ret = gets(line);
	if (strlen(line) > 0)
		{
		/* Add this class and its prerequisites. */
		add_class(line, pre, name, &count);
		}
	else if (count > 0)
		{
		printf("Dataset %d:\n", set+1);
		set ++;
		/* We should perform the topological sort and print the output. */
		top_sort(name, pre, count);
		printf("\n");
		/* Reinitialize. */
		initialize(pre, &count);
		}
	} while (ret);
}

/***************************************************************************
initialize
***************************************************************************/
void initialize(char pre[NUM][NUM], int *count)
{
int i, j;

for (i = 0; i < NUM; i++)
	for (j = 0; j < NUM; j++)
		pre[i][j] = 0;
*count = 0;
}

/***************************************************************************
add_class
***************************************************************************/
void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1],
	int *count)
{
char temp[MAX];
int i = 0;
int c, k;

/* Get the name of the class. Look it up in the list of names. If it is not
   found, then add it. */
get_word(line, temp, &i);
c = name_lookup(temp, name, count);

/* Read all the prerequisites and update the array. */
while (get_word(line, temp, &i))
	{
	k = name_lookup(temp, name, count);
	pre[c][k] = 1;
	}
}

/***************************************************************************
get_word

Extracts the next word from line. i indicates where to start. After reading
the word, i is changed to the end of the word for the next reading.
***************************************************************************/
int get_word(char line[MAX], char temp[MAX], int *i)
{
int j = 0;

/* Skip white space. If the end of the line is found, return that no word was
   read. */
while (! valid(line[*i]))
	{
	if (line[*i] == 0)
		return 0;
	(*i) ++;
	}

/* Copy the word. */
while (valid(line[*i]))
	{
	temp[j] = line[*i];
	j ++;
	(*i) ++;
	}

/* Terminate the copied word correctly and return that a word was found. */
temp[j] = 0;
return 1;
}

/***************************************************************************
valid

Return 1 iff the character is an uppercase letter or a numeral.
***************************************************************************/
int valid(char c)
{
if (('A' <= c) && (c <= 'Z'))
	return 1;
if (('0' <= c) && (c <= '9'))
	return 1;
return 0;
}

/***************************************************************************
name_lookup

Return the location of  in the list . If  does not occur,
then add it and return the new location.
***************************************************************************/
int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count)
{
int i;

/* Check if temp occurs in the list of names. */
for (i = 0; i < *count; i++)
	if (strcmp(temp, name[i]) == 0)
		return i;

/* It doesn't occur. Add it. */
strcpy(name[*count], temp);
(*count) ++;
return (*count) - 1;
}

/***************************************************************************
top_sort

Perform the topological sort. If two classes have no unsatisfied prerequisites,
then take the one that has the lowest number; if the numbers are the same, take
the one with the alphabetically lowest department. If a cycle is detected,
print that out.
***************************************************************************/
void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count)
{
char used[NUM];   /* flag indicating whether class has been printed by sort */
int total[NUM];   /* total number of prerequisites that a class has */
int order[NUM];   /* Order that classes are printed out. */
int i, j, k;

/* Initialize that all classes are un-used, and count total number of
   prerequisites for each class. */
for (i = 0; i < count; i++)
	{
	used[i] = 0;
	total[i] = 0;
	for (j = 0; j < count; j++)
		if (pre[i][j])
			total[i] ++;
	}

/* Perform topological sort. */
for (i = 0; i < count; i++)
	{
	k = -1;
	for (j = 0; j < count; j++)
		if (!used[j] && (total[j] == 0))
			{
			/* Class j has no unsatisfied prerequisites. */
			if (k == -1)
				/* We have not found a class yet with no unsatisfied prereqs. */
				k = j;
			else
				/* We have found another class with no unsatisfied prereqs.
				   Keep the class with the lowest number, or if numbers are
				   the same, alphabetically lowest department. */
				{
				if (compare(name[k], name[j]) == 1)
					k = j;
				}
			}
	if (k == -1)
		{
		/* There is no class with unsatisfied prereqs. Must be a cycle. */
		printf("A cycle was detected in the classes.\n");
		return;
		}
	/* Mark class k as used, and remove it from the array of prereqs. */
	used[k] = 1;
	for (j = 0; j < count; j++)
		if (pre[j][k])
			{
			pre[j][k] = 0;
			total[j] --;
			}
	/* We'll eventually print out this class next. */
	order[i] = k;
	}

/* No cycles were detected. Print out the classes in order. */
for (i = 0; i < count; i++)
	printf("%3d: %s\n", i+1, name[order[i]]);
}

/***************************************************************************
compare

Returns -1 if a < b, 0 if a == b, and 1 if a > b. The order is defined by
first comparing the number part of the class names; if they're equal, compare
the department part.
***************************************************************************/
int compare(char a[], char b[])
{
int na, nb;

na = number(a);
nb = number(b);
if (na < nb)
	return -1;
if (na > nb)
	return 1;
return strcmp(a, b);
}

/***************************************************************************
number

Returns the number portion of a class's name.
***************************************************************************/
int number(char name[])
{
int i = 0;

while (('A' <= name[i]) && (name[i] <= 'Z'))
	i ++;
return atoi(name + i);
}
The test input was:
CS113 : CS100
CS114 : CS100
CS130 :
CS211 : CS100
CS212 : CS100
CS213 : CS211
CS222 : CS100 MATH294
CS280 : CS211
CS314 : CS211
CS381 : CS280
CS400 : CS280
CS410 : CS280
CS412 : CS314 CS381 CS410
CS414 : CS314
ARCH374: CS211
CS421 : MATH294
CS481 : CS280 CS381
CS482 : CS481 CS410
MATH294 : MATH293

Z1 : X1 Y1
Y1 : X1
X1 : W1
W1 : Z1

EF1006 : EF1005 MATH1001
EE2005 : EF1006
EE2006 : EE2005
EE2504 : EF1005
EE4505 : EE2504
EE4506 : EE4505
The correct output was:
Dataset 1:
  1: CS100
  2: CS113
  3: CS114
  4: CS130
  5: CS211
  6: CS212
  7: CS213
  8: CS280
  9: MATH293
 10: MATH294
 11: CS222
 12: CS314
 13: ARCH374
 14: CS381
 15: CS400
 16: CS410
 17: CS412
 18: CS414
 19: CS421
 20: CS481
 21: CS482

Dataset 2:
A cycle was detected in the classes.

Dataset 3:
  1: MATH1001
  2: EF1005
  3: EF1006
  4: EE2005
  5: EE2006
  6: EE2504
  7: EE4505
  8: EE4506

Problem 4 -- New Alphabetical Order

This was the only problem with any correct submissions. Here is my solution:
#include < stdio.h >
#include < stdlib.h >
#include < string.h >

/***************************************************************************
New Alphabetical Order

Read in a new alphabetical order, and a list of words. Print out the words
in (the new) alphabetical order.
***************************************************************************/

#define MAX 80   /* maximum line length */
#define NUM 50   /* maximum number of words to alphabetize */
#define WORD 16  /* maximum word length */

void make_order(char line[MAX], int order[26]);
void sort(int order[26], char words[NUM][WORD+1], int count);
int compare(int order[26], char a[WORD+1], char b[WORD+1]);

/***************************************************************************
main
***************************************************************************/
void main(void)
{
char line[MAX];
char *ret;
char words[NUM][WORD+1];
int order[26];
int set = 0;
int count;

count = -1;
do {
	line[0] = 0;
	ret = gets(line);
	if (strlen(line) > 0)
		{
		/* This is either the new alphabetical order, or a word to be
		   alphabetized. */
		if (count == -1)
			/* This is the new alphabetical order. */
			make_order(line, order);
		else
			/* This is a word to be alphabetized. */
			strcpy(words[count], line);
		/* Either way, increment our counter. */
		count ++;
		}
	else if (count >= 0)
		{
		printf("Dataset %d\n", set+1);
		/* We should alphabetize the words and print them out in order. */
		sort(order, words, count);
		/* Reset our counters. */
		count = -1;
		set ++;
		printf("\n");
		}
	} while (ret);
}

/***************************************************************************
make_order

Makes an array such that given a letter c, the index of c in the new
alphabetical order is order[c - 'a'].
***************************************************************************/
void make_order(char line[MAX], int order[26])
{
int i;

for (i = 0; i < 26; i++)
	order[line[i] - 'a'] = i;
}

/***************************************************************************
sort

Print out the words in the new alphabetical order.
***************************************************************************/
void sort(int order[26], char words[NUM][WORD+1], int count)
{
int used[NUM];
int i, j;
int low;

/* Reset used array to all 0's. */
for (i = 0; i < count; i++)
	used[i] = 0;

for (i = 0; i < count; i++)
	{
	/* Each time through loop, find alphabetically-lowest unused word. */
	low = -1;
	for (j = 0; j < count; j++)
		if (!used[j])
			{
			if (low == -1)
				low = j;
			else
				if (compare(order, words[low], words[j]) == 1)
					low = j;
			}
	/* Now, low is index of smallest word. Print it out. */
	printf("%3d: %s\n", i, words[low]);
	/* Mark this word as used. */
	used[low] = 1;
	}
}

/***************************************************************************
compare

Compare the two words a and b. Return -1 if a is less, 0 if they are
the same, and 1 if b is less. Use the new alphabetical order defined by
order.
***************************************************************************/
int compare(int order[26], char a[WORD+1], char b[WORD+1])
{
int i = 0;
int aa, bb;

while (1)
	{
	if ((a[i] == 0) && (b[i] == 0))
		/* We have simultaneously hit the end of both words. They must be the
		   same. */
		return 0;
	if (a[i] == 0)
		/* We have hit end of a. It must be less. */
		return -1;
	if (b[i] == 0)
		/* We have hit end of b. It must be less. */
		return 1;
	/* Look up values of ith character in a and b in the new alphabet. */
	aa = order[a[i] - 'a'];
	bb = order[b[i] - 'a'];
	if (aa < bb)
		return -1;
	if (aa > bb)
		return 1;
	/* So far, words are same and haven't ended. Keep going. */
	i ++;
	}
}
The test input was:
abcdefghijklmnopqrstuvwxyz
bca
bcb
aac
abb
abc
aca
bcc
acb
acc
baa
bbc
ccc
bab
bac
bba
aab
bbb
caa
cab
cac
cba
cbb
aba
cbc
cca
ccb
aaa

qwertyuiopasdfghjklzxcvbnm
now
is
the
time
for
all
good
men
to
come
to
the
aid
of
their
country
mary
had
a
little
lamb
whose
fleece
was
white
as
snow
The correct output was:
Dataset 1
  0: aaa
  1: aab
  2: aac
  3: aba
  4: abb
  5: abc
  6: aca
  7: acb
  8: acc
  9: baa
 10: bab
 11: bac
 12: bba
 13: bbb
 14: bbc
 15: bca
 16: bcb
 17: bcc
 18: caa
 19: cab
 20: cac
 21: cba
 22: cbb
 23: cbc
 24: cca
 25: ccb
 26: ccc

Dataset 2
  0: was
  1: white
  2: whose
  3: time
  4: to
  5: to
  6: the
  7: the
  8: their
  9: is
 10: of
 11: a
 12: aid
 13: as
 14: all
 15: snow
 16: for
 17: fleece
 18: good
 19: had
 20: little
 21: lamb
 22: country
 23: come
 24: now
 25: men
 26: mary

Last updated 28 September 1999.