K&R Exercise 1-21 - Mental incomprehension

Question

The "impossible" K&R exercise.

"Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops, say every n columns. Should n be a variable or a symbolic parameter?"

The problem I'm having is, I'm unsure about how to even do this correctly. I know it's not very explanatory, but that's pretty much the problem here. Most of the examples I've seen have counted a number of blanks, and replaced those series with a tab, but this isn't what its asking, I reckon I understand what its asking, but currently feel unable to do this.

Could anyone help :)

Edit: The code I've written so far can be found here.

Answer 1

My understanding is that you don't really have to know what the problem is or how to solve it in order to answer this question. The question seems to asking whether you understand when to use variables instead of "symbolic parameters". I'm not actually sure what is meant by "symbolic parameter"; it seems to be outdated nomenclature.

Having said that, solving the first part of the question (replacing spaces with tabs) is rather straight forward. Think division and remainders.

Answer 2

I took a very cursory look at your code, and nothing is jumping out at me as blatantly wrong.

So my advice would be to either single-step through a few input examples in a debugger, examining variable values as you go, or add a whole bunch of debugging print statements. In either case, your goal is to find the point where the state of the program starts to deviate from what you expected or intended.

Answer 3

I agree with your assessment. It won't be enough to replace every n blanks with a tab; for example, if n == 4, "hi blank blank blank blank" should not be replaced by "hi tab", but rather by "hi tab blank blank".

It sounds like what you need to do is keep track of the current position as you're reading in each line, and use this information to determine how many tabs you need. Does this help? Please let me know if you need more details!

As for the "variable vs. symbolic parameter" part, either would definitely be viable, but I can think of one significant advantage to using a variable: you can run the program for different values of n without recompiling.

Answer 4

If your question is "What is this asking me to do?" I think I can help by paraphrasing the original question (posing the same question in a different way).

Write a program that takes as input text with spaces and produces as output visually equivalent text using tabs to the maximum extent possible.

For example, with tabstops every 8 characters, and showing spaces as '.' and tabs as '-';

input;
".foo:...bar;......#comment"
output;
".foo:-bar;-..#comment"

input;
".......-foo:.....bar;......#comment"
output;
"-foo:-.bar;-...#comment"

Write the program so that tabstop parameter n can be varied, i.e. allow values of n other than 8. Be prepared to justify your decision to make n a constant, or alternatively a variable.

Edit I had a look at your code and I think it is more complex than it needs to be. My advice is to do it a character at a time. There's no need to buffer a whole line. Maintain a column count as you read each character ('\n' resets it to zero, '\t' bumps it by 1 or more, other characters increment it). When you see a space (or tab), don't emit anything right away, start your entabbing process, emit zero or more tabs and then spaces later (at '\n' or a non whitespace character, whichever comes first).

A final hint is that a state machine can make this kind of algorithm a lot easier to write, validate, test and read.

Edit 2 In a shameless attempt to get the OP to accept my answer, I have now gone ahead and actually coded a solution myself, based on the hints I offered above and my comment in the discussion.

// K&R Exercise 1-21, entab program, for Stackoverflow.com
#include <stdio.h>
#define N 4     // Tabstop value. Todo, make this a variable, allow
                //  user to modify it using command line

int main()
{
    int col=0, base_col=0, entab=0;

    // Loop replacing spaces with tabs to the maximum extent
    int c=getchar();
    while( c != EOF )
    {

        // Normal state
        if( !entab )
        {

            // If whitespace goto entab state
            if( c==' ' || c=='\t' )
            {
                entab = 1;
                base_col = col;
            }

            // Else emit character
            else
                putchar(c);
        }

        // Entab state
        else
        {

            // Trim trailing whitespace
            if( c == '\n' )
            {
                entab = 0;
                putchar( '\n' );
            }

            // If not whitespace, exit entab state
            else if( c!=' ' && c!='\t' )
            {
                entab = 0;

                // Emit tabs to get close to current column position
                //  eg base_col=1, N=4, col=10
                //  base_col + 3 = 4 (1st time thru loop)
                //  base_col + 4 = 8 (2nd time thru loop)
                while( (base_col + (N-base_col%N)) <= col )
                {
                    base_col += (N-base_col%N);
                    putchar( '\t' );
                }

                // Emit spaces to close onto current column position
                // eg base_col=1, N=4, col=10
                //  base_col -> 8, and two tabs emitted above
                //  base_col + 1 = 9 (1st time thru this loop)
                //  base_col + 1 = 10 (2nd time thru this loop)
                while( (base_col + 1) <= col )
                {
                    base_col++;
                    putchar( ' ' );
                }

                // Emit buffered character after tabs and spaces
                putchar( c );
            }
        }

        // Update current column position for either state
        if( c == '\t' )
            col += (N - col%N); // eg col=1, N=4, col+=3
        else if( c == '\n' )
            col=0;
        else
            col++;

        // End loop
        c = getchar();
    }
    return 0;
}

Answer 5

I am currently plowing KnR and came across this page:

Answers to Exercises

Your exercise are located under:

• Solutions

  • Chapter 1 - A Tutorial Introduction

    • Ex No 21 Pg No 34

      users.powernet.co.uk/eton/kandr2/krx121.html

Hopefully you find this useful.

Sincerely, Morpfh

1: http://users.powernet.co.uk/eton/kandr2/index.html "The C Programming Language", 2nd edition, Kernighan and Ritchie - Answers to Exercises

Answer 6

In the top rated answer above, the program is overly complex. In an attempt to simplify that part of the answer, I've attached a much simpler code hopefully written in the style of K&R (mostly by incrementing inline with ++).

include

define TAB 4

int main(){

char newsentence[255],c;
int spacecount = 0, oldsentencepointer = 0, newsentencepointer = 0;

printf("Give me a sentence please:\n");

while ((c = getchar()) != '\n') {
    if ((oldsentencepointer != 0) && (oldsentencepointer % TAB == 0) && (spacecount > 0))
       {
        newsentencepointer -= spacecount;         //if at tabstop, and spaces and not
                                                    first, go back to 1st space, set tab.
        newsentence[newsentencepointer++] = '\t';
        spacecount = 0;
        }

    if (c == ' ') {
        newsentence[newsentencepointer++] = ' ';
        spacecount++;                       //keep track of spaces before tab stop
    }

    else if (c == '\t') {
        newsentence[newsentencepointer++] = '\t' ;
        oldsentencepointer = TAB;   //set old pointer to TAB (does not matter if actual,
                                      only cadence important)
        continue;                   //continue from here so as not to increment 
                                      old sentence counter.
        }

    else {
        newsentence[newsentencepointer++] = c ;   //write whatever was old into new.
        spacecount = 0;                           //reset space counter.
        }

    oldsentencepointer++;

}

newsentence[newsentencepointer] = '\0';    //cap it off.

puts(newsentence);

return 0;

}

Answer 7

There is an even more concise solution, although it does not employ the best code practices available (abusing short circuit evaluation, awkward control flow via continue, somewhat weird "space" loop).

#include <stdio.h>

#define TS 8

int main(int arg, char *argv[]) {
    int counter = 0, space_counter = 0, c;
    while ((c = getchar()) != EOF) {
        ++counter;
        if (c == ' ' && ++space_counter && (counter % TS) == 0) {
            space_counter = 0;
            c = '\t';
        } else if (c == '\t') {
            counter = space_counter = 0;
        } else if (c != ' ') {
            while (space_counter--)
                putchar(' ');
            space_counter = 0;
            if (c == '\n')
                counter = 0;
        } else {
            continue; /* don't call putchar(c) */
        }
        putchar(c);
    }
    return 0;
}

Except for blanks, every character that is read is printed verbatim. Blanks are counted instead. If the program encounters a non-blank character, it prints as many blanks as it has counted before, resetting that counter afterwards. If it encounters a blank, it checks via a second counter (printed characters since the beginning of the line/last tabstop) if the cursor is on a tabstop. If it is, a tab is printed, otherwise the blank is just counted.

A tab in the input is dealt with resetting the space counter and outputting the tab, eliminating any superfluous blanks in the process.

Answer 8

I'm a bit late, but here's how I solved it myself. It's a different approach than what has been shared above, so please share any comments/feedback if you have any.

Check out my public gist on Github for the source code. There's comments on the code, and the approach is explained on the top of the file, but I'll copy and paste it here just so that the logic is clear from the get-go.

Approach:

• We'll keep track of number of spaces encountered (between nontab/nonspace characters)

• We'll keep track of characters (that aren't tabs/blanks/newlines) per input line

• We'll evaluate the "gaps" generated by spaces by:

  • Evaluating whether the number of spaces in between those characters.

  • A gap will be "big enough" when the number of spaces is >= TABSIZE

  • Then, for all the left over spaces in our "buffer", we'll print them out individually

Finally, we print out the character that was read in (which was not a tab/blank)

As well as updating space count and character count if necessary.

I'm still a novice programmer in all senses, so I am not sure of how it would compare vs the other solutions posted in here, but the logic seems easier to follow (at least for me).

Hope this helps someone later on!

Answer 9

Let me provide another one that at least handled cases that provided top level answer. It handles one string only though.

Suppose the tabulation is the things that included at least 2 spaces.

1. Let's track number of trailing spaces. \
2. If the last symbol and the current symbol is space, there is could be a tabulation. \
3. When the number of trailing spaces is equal to tabulation stop: set the main counter to counter - tabulation stop - 1 (as we work with array), then assign the position to \t
4. After shift the counter variable, other symbols will be written as usual

/*
Write a program that takes as input text with spaces
and produces as output visually equivalent text using tabs to the maximum extent possible.

f.e. tab=4

input:
".foo:...bar;......#comment"
output:
".foo:-bar;-..#comment"

input:
".......-foo:.....bar;......#comment"
output:
"-foo:-.bar;-...#comment"
*/

#include <stdio.h>

#define MAXLINE 24
#define TABSTOP 4

int entab(char s[]);

int main() {
    char s[MAXLINE];

    entab(s);
    printf("%s\n", s);

    return 0;
}

int entab(char s[]) {
    int i;
    int j;
    char c;

    for (i = 0, j = 1; i < MAXLINE - 1 && ((c = getchar()) != '\n'); ++i) {
        // entab state
        if (i > 0 && s[i - 1] == ' ' && c == ' ') {
            ++j;
            if (j == TABSTOP) {
                i -= TABSTOP - 1;
                j = 1;
                s[i] = '\t';
            } else
                s[i] = c;
        }
        // Normal state
        else
            s[i] = c;
    }
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';

    return 0;
}