Beautiful Code

Chapter 33. Writing Programs for “The Book”

Brian Hayes

The mathematician paul erdös often spoke of the book, a legendary volume (not to be found on the shelves of any earthly library) in which are inscribed the best possible proofs of all mathematical theorems. Perhaps there is also a Book for programs and algorithms, listing the best solution to every computational problem. To earn a place in those pages, a program must be more than just correct; it must also be lucid, elegant, concise, even witty.

We all strive to create such gems of algorithmic artistry. And we all struggle, now and then, with a stubborn bit of code that just won’t shine, no matter how hard we polish it. Even if the program produces correct results, there’s something strained and awkward about it. The logic is a tangle of special cases and exceptions to exceptions; the whole structure seems brittle and fragile. Then, unexpectedly, inspiration strikes, or else a friend from down the hall shows you a new trick, and suddenly you’ve got one for The Book.

In this chapter I tell the story of one such struggle. It’s a story with a happy ending, although I’ll leave it to readers to decide whether the final program deserves a place in The Book. I wouldn’t be brash enough even to suggest the possibility except that this is one of those cases where the crucial insight came not from me but from a friend down the hall—or, rather, from a friend across the continent.

The Nonroyal Road

The program I’ll be talking about comes from ...