Trying to find a particular anecdote about programming [closed]

Question

I remember this anecdote from shortly after I graduated college, so it was on the internet at least in 2014. The point of the anecdote was that two equally valid solutions to a problem can take drastically different approaches with different cost and difficulty and each have value as measured by different metrics. I can't recall, however, if I heard this spoken in a YouTube presentation (possibly at Strange Loop or Google IO) or if I read it on an online post, but I know I heard the story online.

The story went roughly like this:

A company needed to accomplish some task (perhaps finding the sum of all accounts who were overdue)

They hired a famous software architect with 40 years of experience

The architect gathered specs, built a definition of the problem, and worked for 6 months. When he was done he had written tens of thousands of lines of code including very elegant solutions to problems the likes of which the industry had never seen. And his code worked perfectly

Then another developer came along and solved the same problem in an hour with 6 lines of bash script

In the postscript of the story (perhaps discussing it afterwards) they mentioned that technically the bash script utilized other tools like awk, sed, and grep so you need to factor in the lines of code for those programs as well to find that this one-hour solution was technically less efficient and had more total code involved - yet it was solved faster and it worked just as well.

I'm hoping someone can help me find the source of this story

Answer 1

TL;DR: This story is recognisable as a mangled version of Donald Knuth’s solution to the ‘K most common words’ problem and Doug McIlroy’s review of it, in the June 1986 Communications of the ACM.

Literate programming

In the 1980s, Jon Bentley wrote a column called ‘Programming Pearls’ that appeared in the Communications of the ACM. He devoted the columns for May and June 1986 to a description of Donald Knuth’s ‘literate programming’ paradigm which he had used to develop the computer typesetting systems METAFONT and TeX. The May column described the principles of literate programming and Knuth’s ‘WEB’ software, and introduced the following challenge:

When I first read Knuth’s “Literate Programming” paper referenced under Further Reading, I was quite impressed by his approach. When I read the large programs referenced there, I was overwhelmed: for the first time, somebody was proud enough of a substantial piece of code to publish it for public viewing, in a way that is inviting to read. I was so fascinated that I wrote Knuth a letter, asking whether he had any spare programs handy that I might publish as a “Programming Pearl.”

But that was too easy for Knuth. He responded, “Why should you let me choose the program? My claim is that programming is an artistic endeavor and that the WEB system gives me the best way to write beautiful programs. Therefore I should be able to meet a stiffer test: I should be able to write a superliterate program that will be noticeably better than an ordinary one, whatever the topic. So how about this: You tell me what sort of program you want me to write, and I’ll try to prove the merits of literate programming by finding the best possible solution to whatever problem you pose—at least the best by current standards.”

He laid some ground rules for the task. The program had to be short enough to fit comfortably in a column, say, an afternoon’s worth of programming. It had to be a complete program (not just a fragment), and could not stress input and output (Knuth has boilerplate to handle that problem, but that isn’t of interest to most readers). Because his “Literate Programming” article is built around a program to print prime numbers, this assignment should avoid number-theoretic problems.

I chose a problem that I had assigned to several classes on data structures.

Given a text file and an integer K, you are to print the K most common words in the file (and the number of their occurrences) in decreasing frequency.

_{Jon Bentley (1986). ‘Literate Programming’. Communications of the ACM 29:5, pp. 365–368.}

Knuth’s solution

Jon Bentley gave over his June 1986 column to Knuth’s literate solution to the ‘K most common words’ problem. Knuth solved the problem by deploying a recently invented data structure, Frank Liang’s ‘hash trie’, a form of prefix tree with the representations of the nodes interleaved in an array in order to make the most efficent use of the available space:

Given a word in the buffer, we will want to look for it in a dynamic dictionary of all words that have appeared so far. We expect many words to occur often, so we want a search technique that will find existing words quickly. Furthermore, the dictionary should accommodate words of variable length, and (ideally) it should also facilitate the task of alphabetic ordering.

These constraints, suggest a variant of the data structure introduced by Frank M. Liang in his Ph.D. thesis [“Word Hy-phen-a-tion by Com-pu-ter,” Stanford University, 1983]. Liang’s structure, which we may call a hash trie, requires comparatively few operations to find a word that is already present, although it may take somewhat longer to insert a new entry. Some space is sacrificed—we will need two pointers, a count, and another 5-bit field for each character in the dictionary, plus extra space to keep the hash table from becoming congested—but relatively large memories are commonplace nowadays, so the method seems ideal for the present application.

_{Donald Knuth (1986). ‘Common Words’. Communications of the ACM 29:6, pp. 473–474.}

McIlroy’s review

Jon Bentley commissioned a review of Knuth’s solution from Doug McIlroy. McIlroy was impressed by Knuth’s virtuousity but critical of his engineering approach:

I found Don Knuth’s program convincing as a demonstration of WEB and fascinating for its data structure, but I disagree with it on engineering grounds. The problem is to print the K most common words in an input file (and the number of their occurrences) in decreasing frequency. Knuth’s solution is to tally in an associative data structure each word as it is read from the file. The data structure is a trie, with 26-way (for technical reasons actually 27-way) fan-out at each letter. To avoid wasting space all the (sparse) 26-element arrays are cleverly interleaved in one common arena, with hashing used to assign homes. Homes may move underfoot as new words cause old arrays to collide. The final sorting is done by distributing counts less than 200 into buckets and insertion-sorting larger counts into a list. […]

Knuth’s purpose was to illustrate WEB. Nevertheless, it is instructive to consider the program at face value as a solution to a problem. A first engineering question to ask is: how often is one likely to have to do this exact task? Not at all often, I contend. It is plausible, though, that similar, but not identical, problems might arise. A wise engineering solution would produce—or better, exploit—reusable parts.

_{Doug McIlroy, ‘A Review’. Communications of the ACM 29:6, pp. 478–479.}

McIlroy pointed out that the ‘K most common words’ problem could be solved using standard Unix tools via a short shell script:

The following shell script was written on the spot and worked on the first try. It took 30 seconds to handle a 10,000-word file on a VAX-11/750™.

(1)  tr -cs A-Za-z '
     ' |
(2)  tr A-Z a-z |
(3)  sort |
(4)  uniq -c |
(5)  sort -rn |
(6)  sed ${1}q

If you are not a Unix adept, you may need a little explanation, but not much, to understand this pipeline of processes. The plan is easy:

1. Make one-word lines by transliterating the complement (-c) of the alphabet into newlines (note the quoted newline), and squeezing out (-s) multiple newlines.

2. Transliterate upper case to lower case.

3. Sort to bring identical words together.

4. Replace each run of duplicate words with a single representative and include a count (-c).

5. Sort in reverse (-r) numeric (-n) order.

6. Pass through a stream editor; quit (q) after printing the number of lines designated by the script’s first parameter (${1}).

_{McIlroy, p. 479.}

I recommend reading both the May and June 1986 ‘Programming Pearls’ columns—they are classics of the computer programming literature, and Knuth’s solution remains a jewel of elegance and readability despite its impracticality.