Solving a 1993 Programming Challenge in 2022 (Updated)
I recently came across a collection of old (1990s) “programming challenges”. I thought it might be amusing to tackle one of these challenges using technologies from the period in which they were posed, and compare the solution to one using contemporary techniques. In other words, do the same problem in C and Python.
The Problem
Stripped to its essence, the question is to identify, among a list of words,
those words that are not anagrams of another word from the list. In other
words, to identify those entries in the list that are not permutations of
another entry. The comparison is not case sensitive, so that tIeD and
EdiT are considered permutations of each other.
The formulation of the challenge contains very detailed specifications of the expected input and output formats, which I’ll quote here in full:
The dictionary will contain no more than 1000 words. Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. (…) The file will be terminated by a line consisting of a single
#.Output will consist of a series of lines. Each line will consist of a single word that is a relative anagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order.
For my solutions, I added the requirement that the input will always be read from standard input (rather than a named file).
The original challenge provided a sample input:
ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries
#
which is expected to produce the following output:
Disk
NotE
derail
drIed
eye
ladder
soon
Solution 1 (Contemporary):
Here is the Python version:
1import sys
2
3# Read words into terms
4terms = []
5for line in sys.stdin:
6 if line.startswith( "#" ):
7 break
8 terms += line.strip().split();
9
10# Create dictionary of sorted words as keys; index of raw term as values
11hashes = {}
12for i, t in enumerate(terms):
13 key = ''.join( sorted( t.lower() ) )
14 hashes.setdefault( key, [] ).append( i )
15
16# Eliminate hashes that occurred more than once
17for key in list( hashes.keys() ):
18 if( len(hashes[key]) > 1 ):
19 del hashes[key]
20
21# Output
22print( "\n".join( sorted( [ terms[ hashes[k][0] ] for k in hashes ] ) ) )
The main “algorithm”, as there is, consists of sorting the letters in each word alphabetically, thus creating a “hash” of each word. Because permutations will hash to the same key, the solution consists of those hashes that occur only once.
Solution 2 (Period):
Experienced C programmers will have read the detailed spec of the input format with a sense of recognition: oh, yes, you need to worry about the length of strings and arrays, explicitly, all the time. And it helps a lot knowing what the upper bounds are.
With this in mind, here is my C solution, which takes full advantage of knowing the maximum size of problem ahead of time:
1#include <string.h>
2#include <stdlib.h>
3#include <stdio.h>
4#include <ctype.h>
5
6#define MAXTERM 1000
7#define MAXLINE 80
8#define MAXWORD 20
9
10int cmp( const void *a, const void *b ) {
11 char *p = (char *)a;
12 char *q = (char *)b;
13 return *p - *q;
14}
15
16int cmp2( const void *a, const void *b ) {
17 char **p = (char **)a;
18 char **q = (char **)b;
19 return strcmp( *p, *q );
20}
21
22int read_and_allocate_terms( char **terms ) {
23 char *line = (char *)malloc( MAXLINE+1 );
24 char *res;
25
26 int words = 0;
27 int i, j; /* start and end of words input line */
28
29 while( 1 ) {
30 res = fgets( line, MAXLINE+1, stdin );
31
32 if( !res ) { /* Should not happen */
33 fprintf( stderr, "Null pointer while reading\n" );
34 }
35
36 if( res[0] == '#' ) { /* stop reading if first char is #; ignore newln */
37 free( line );
38 return words;
39 }
40
41 for( i=0; ; i++ ) {
42 /* Break if end-of-line */
43 if( line[i] == '\n' ) {
44 break;
45 }
46
47 /* Iterate to find start of word */
48 if( line[i] != ' ' ) {
49
50 /* Iterate to find end of word */
51 for( j=i+1; ; j++ ) {
52 if( line[j] == ' ' || line[j] == '\n' ) {
53 terms[words] = strndup( line+i, j-i );
54 words += 1;
55 i = j-1; /* pick up at crr pos of j again: for(i) will inc! */
56 break;
57 }
58 }
59 }
60 }
61 }
62}
63
64int main() {
65 char **terms = (char **)malloc( MAXTERM );
66 char **sorted = (char **)malloc( MAXTERM );
67 char **output = (char **)malloc( MAXTERM );
68 int *res = (int *)malloc( MAXTERM );
69
70 int i, j, words, matches, flag;
71
72 /* populate terms with the input words */
73 words = read_and_allocate_terms_getchar( terms );
74
75 /* duplicate input, lowercase, then sort each word alphabetically */
76 for( i=0; i<words; i++ ) {
77 sorted[i] = strdup( terms[i] );
78 for( j=0; j<strlen(sorted[i]); j++ ) {
79 sorted[i][j] = tolower( sorted[i][j] );
80 }
81 qsort( sorted[i], strlen(sorted[i]), sizeof(char), cmp );
82 }
83
84 /* compare all sortd words to all others; remember those that dont match */
85 matches = 0;
86 for( i=0; i<words; i++ ) {
87 flag = 0;
88 for( j=0; j<words; j++ ) {
89 if( i!=j && strcmp( sorted[i], sorted[j] ) == 0 ) {
90 flag = 1;
91 }
92 }
93
94 /* if no match, remember the index of the trial word */
95 if( flag == 0 ) {
96 res[ matches ] = i;
97 matches += 1;
98 }
99 }
100
101 /* copy, then sort for output */
102 for( i=0; i<matches; i++ ) {
103 output[i] = strdup( terms[res[i]] );
104 }
105 qsort( output, matches, sizeof(char *), cmp2 );
106 for( i=0; i<matches; i++ ) {
107 printf( "%s\n", output[i] );
108 }
109
110 /* clean up */
111 for( i=0; i<words; i++ ) {
112 free( terms[i] );
113 free( sorted[i] );
114 }
115 for( i=0; i<matches; i++ ) {
116 free( output[i] );
117 }
118 free( terms );
119 free( sorted );
120 free( output );
121 free( res );
122
123 return EXIT_SUCCESS;
124}
Notice how much of the program deals only with reading and parsing the
input file! Essentially the entire routine read_and_allocate_terms()
does nothing but read the file, identify individual words, and store
them for later use. Another significant source of boilerplate is the
explicit memory management: not only all the calls to malloc()
(directly and indirectly through strdup()), but also the crucial
calls to free() at the end.
The main “algorithm” for detecting duplicate permutations (or their absence) is virtually unchanged from the Python version. Without a readily available hashmap, the program has to iterate over an array of possible hashes. Given the small size of the input, this is not a problem in this case.
Finally: although I tested the code, I make no claims that it will correctly handle edge cases and not leak memory!
Conclusion
At least to me, one of the most welcome changes in programming overall has been the reduction of effort required for “non-essential tasks”: bookkeeping, resource management, I/O. In a similar spirit, I am deeply grateful for the (now) universal availability of basic data structures: hashmaps, resizable arrays, proper strings.
Postscript
It later occurred to me that, given the specifics of the input format,
it might be more convenient to read the input character-by-character,
rather than breaking it into lines. Here is an alternative version of
the read_and_allocate_terms() routine that uses getchar() instead:
1int read_and_allocate_terms_getchar( char **terms ) {
2 char *buf = (char *)malloc( MAXWORD );
3 char *p = buf;
4
5 int words = 0;
6 int c, flag; /* flag is 1 if actively scanning word; 0 for whitespace */
7
8 flag = 0;
9 while( c=getchar() ) {
10 if( c=='#' || c==EOF ) {
11 free( buf );
12 return words;
13 }
14
15 if( flag == 0 ) {
16 if( c!=' ' && c!='\n' ) {
17 flag = 1;
18 *p++ = c;
19 }
20 } else {
21 if( c!=' ' && c!='\n' ) {
22 *p++ = c;
23 } else {
24 flag = 0;
25 terms[words] = strndup( buf, p-buf );
26 words += 1;
27 p = buf;
28 }
29 }
30 }
31}
It is amusing to see that employing a “higer-level abstraction” (lines and words, instead of individual characters) in this case leads to more code, not less.
Post-Postscript
An astute reader reminded me of the strtok() function that breaks a
string into delimiter-separated tokens. So, here is yet another version
of the read_and_allocate_terms() routine; this one uses strtok():
1int read_and_allocate_terms_strtok( char **terms ) {
2 char *line = (char *)malloc( MAXLINE+1 );
3 char *res;
4
5 int words = 0;
6 char *tok;
7 char *delim = " \n";
8
9 while( 1 ) {
10 res = fgets( line, MAXLINE+1, stdin );
11
12 if( !res ) { /* Should not happen */
13 fprintf( stderr, "Null pointer while reading\n" );
14 }
15
16 if( res[0] == '#' ) { /* stop reading if first char is #; ignore newline */
17 free( line );
18 return words;
19 }
20
21 tok = strtok( res, delim );
22 if( tok ) {
23 terms[words] = strdup( tok );
24 words += 1;
25 }
26 while( tok = strtok( NULL, delim ) ) {
27 terms[words] = strdup( tok );
28 words += 1;
29 }
30 } /* end while( 1 ) */
31}
Curiously, this version isn’t actually shorter than the one using getchar(),
but it is arguably easier to understand, because there is less pointer
arithmetic and the logic is simpler.
That being said, it is no accident that I forgot about strtok() on my
previous pass: it is not a routine that I am comfortable with. Not only
does it maintain state between invocations (rare for a C function) and
behaves differently on subsequent calls (not idempotent), it also mangles
its input (and will therefore fail mysteriously when invoked on a constant
string). Its Linux man page suggests a certain queasiness, and contains
some actual ambiguity in regards to the semantics of the delim argument:
it is not entirely clear whether any one of the characters in the supplied
string serves as a delimiter (this is in fact the case), or whether only
the fixed combination of the entire argument separates tokens.