No, it’s not really impossible; it’s just extremely difficult until you make a certain, particular mental leap, one which was long in coming for my idiot little brain.
However, some brief background: K & R is Kernighan and Ritchie, authors of the monumental The C Programming Language. When I say “monumental,” I don’t mean “huge,” because it’s not; it’s actually remarkably short, given that it describes the programming language which underlies just about every significant systems program of the modern computing age. As K & R themselves state in said wise tome:
We have tried to retain the brevity of the first edition. C is not a big language, and it is not well served by a big book.
Such wisdom! Such restraint! If only more programming book authors could conduct themselves with such brevity! As a student of the Thomists, themselves dedicated studentes brevitatis, I can’t help but admire this kind of sensibility.
K & R have, rightly, exercised enormous influence in the world of computing, particular in that of GNU/Linux. Now, GNU has one coding style, while Linux has another; it’s the same language, but each uses different styles. The primary difference is that the Linux style is wonderful, while the GNU style is awful[1]; the reason for this is that the Linux style respects K & R, while the GNU style neglects them, thus consigning itself to the nether regions of illegibility. As Linus Torvalds himself has noted,
First off, I’d suggest printing out a copy of the GNU coding standards, and NOT read it. Burn them, it’s a great symbolic gesture. . . . the preferred way [of coding is] shown to us by the prophets Kernighan and Ritchie . . . Heretic people all over the world have claimed that this [style is] inconsistent, but all right-thinking people know that (a) K&R are _right_ and (b) K&R are right.[2]
So, in other words, K & R are right. Period. Moving on.
In any case, one thing that K & R absolutely love to do is throw into their text, as if it’s a minor practice step, programs that are incredibly difficult to execute correctly. These exercises are described in a way which implies mere employment of what has already been discussed, and that much is technically true; however, they often require cognitive leaps quite beyond the text to that point. Doubtlessly K & R’s immense brilliance render these cognitive leaps hardly worth mentioning, mere flickers of their intellectual thumbs; for puny mortals such as myself, however, they’re more equivalent to running the Boston marathon. There are many such exercises; however, without a doubt the worst example of this that I’ve encountered thus far is the dreaded Exercise 1-21, the entab program.
It sounds benign enough:
Write a program entab that replaces strings of blans by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. [The program in Exercise 1-20; also difficult, but not murderously so.] When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
Hardly designing a rocket guidance system, is it? This one shouldn’t take more than half an hour.
Wrong. You couldn’t be more wrong. For hours I struggled, never successfully attaining this simple end. I’m even ashamed to say that I resorted to the answers site, just for ideas. But even those programs didn’t work. Seriously; I tried them. They don’t do what the exercise says they should do.
They do something, of course; they do what my initial attempt at the program did. They take any group of spaces equal to a tab and replace it with a tab. That’s great and all, but it’s not what the exercise requires.
Here’s an example. The programs at Heathfield’s are fine programs, but they don’t meet what the exercise requires. Here’s what they do; first line is the ruler, second the input, third the output:
|________|________|________|________|
|Now__________is____the______time
|Now\t__is____the_____time
For those of you who don’t know, that ‘\t’ means “tab,” the pipes (“|”) represent tab stops, and the underscores are there because they’re easier to see than spaces. In other words, these programs simply find sequences of eight spaces and replaces them with tabs. It takes no notice of where the tab stops actually are. All well and good. But the exercise doesn’t just want sequences of eight blanks replaced by tabs; it wants some sequences of less than eight blanks replaced, if that would yield the same spacing as the original input.
This second solution is much harder than the first (which I was able to achieve quite quickly, even with my tiny brain and limited programming acumen). I beat my head against the wall for a long time—then finally had an epiphany. I can make the program work!
If I’d sat down and planned out how to solve this problem, like a real programmer, instead of just started banging away at it the way I did, I would have solved this very quickly. But I didn’t, so I got started off on the wrong track, and because I already had a program in front of me, albeit one that didn’t work, I wasn’t able to see that I’d gone wrong from the very beginning.
The answer is that you need two variables, in addition to the string; one to keep the basic index on the line, and one that keeps track of the tab characters. If you know programming, look at the code and you’ll see what I mean. If you don’t, just take my word for it: two variables made all the difference.
And it works!
So, for your enlightenment (by “enlightenment,” I mean “amusement that it took someone so long to solve such a simple problem, and yet that someone is so excited about it”), here’s the code. I hope other anxious learners beating their heads against bricks with this problem will learn from my own egregious errors.
/* +AMDG */
/*
* A program that replaces a sequence of blanks by the
* minimum number of tabs and blanks necessary to achieve
* the same spacing. Gives preference to tabs when either a
* tab or a single blank would suffice to reach a tab stop.
*
* This program is released under the GNU General Public
* License, version 3.
*
*/
#include
#include
#define MAXLINE 10000
#define TABSTOP 8
int getline(char s[], int lim);
int tabreplace(char s[], int tabspot, int index);
int main(void)
{
int i; /* keep track of string index */
int j; /* keep track of tab stops */
char string[MAXLINE];
while(getline(string, MAXLINE) > 0) {
for(i=1,j=1; string[i] != ''; ++i,++j)
i -= tabreplace(string,j,i);
printf("%s",string);
}
return 0;
}
int tabreplace(char s[], int tabspot, int index)
{
int i;
int numspaces;
if (((tabspot % TABSTOP) == 0) && (s[index-1] == '_')) {
for (i = index-1; (s[i] == '_') && (i > (index-TABSTOP)); --i);
numspaces = (i>(index-TABSTOP)) ? index-i-1 : index-i;
if (numspaces > 0)
s[index-numspaces] = '\t';
for(i=index-numspaces+1; s[i] != ''; ++i)
s[i] = s[i+numspaces-1];
s[++i] = '';
return numspaces-1;
}
return 0;
}
int getline(char s[], int lim)
{
int c, i;
for (i=0; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
s[i] = c;
if (c == '\n')
s[i++] = c;
s[i] = '';
return i;
}
It works! I’m really excited. Technology, though often abused, is incredibly powerful; learning more about it is more powerful still.
Praise be to Christ the King!
1. Don’t worry; both produce programs of equal usability, all other things being equal. It’s just that reading GNU-styled code is crazily impossible to me, while reading Linux-styled code, given that it’s directly from the immortal K & R, is pure pleasure.
2. I’m citing with legal standards here; that is, brackets indicate not only inserted material, but also possibly excluded material. This unencumbers selective quotations significantly, removing the need for braces and ellipses; I’ve provided a link to the full text. So many interpolations and exclusions were required because Torvalds is being much more specific than I am here; the spirit of his remarks is the same.

