4
\$\begingroup\$

This is Exercise 1-21 of K&R (2nd edition).

I've seen someone else's post about it but it doesn't solve the problem the way my code does, and I wasn't sure whether I was allowed to post my code as an answer and ask for feedback (it just seemed better to create a new thread and ask for advice here, didn't wanna pollute the other user's topic but if that's what I am supposed to do please let me know and I'll reply over there).

In any way, here's the approach I took to solve the problem:

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.

Here's the code:

#include <stdio.h>

//Entab: replaces string of blanks by the min # of spaces & tabs
//Same tab spots as for detab (8)
//Given performance to tabs.

#define TABSIZE 8

//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)
//Update space count and character count if necessary.

int main()
{
    int c, nc, ns;

    nc = ns = 0;
    while((c = getchar()) != EOF)
    {
        //if this character was a space
        if(c == ' ') {
            //increase the space count
            ++ns;
        }
        //else if the character read in is not a space
        else {

            //while one or more spaces are still "in buffer"
            while(ns > 0)
            {
                //decide whether gap in between chars is long enough for a space
                if(ns >= TABSIZE - nc)
                {
                    //if it is, then place a tab, and remove that amount of spaces
                    putchar('\t');
                    ns -= TABSIZE;
                }
                //else, if the gap is not big enough for spaces, just print them out individually
                else
                {
                    putchar(' ');
                    --ns;
                }
            }

            //if read a newline, reset char count
            //if not, increase it by one for the char we just read in
            //as well as update the total space count to 0
            if(c == '\n')
                nc = ns = 0;
            else if(c != '\t')
                ++nc;

            //finally, put this "nonspace/nontab" character just read
            //after the gap we just covered
            putchar(c);
        }
    }
}

Also, keep in mind that I am just revisiting C's K&R and I am aware that some of it may be outdated, but I'm doing my best to use what's still "useful" of the book and discard what may not be.

I'm using these notes to accompany my travels through C.

\$\endgroup\$
  • 1
    \$\begingroup\$ IMHO, tabs->spaces would be more useful than spaces->tabs. Not least because it may be costing you money. :) \$\endgroup\$ – Edward Feb 16 '18 at 0:22
  • 1
    \$\begingroup\$ @Edward detab() is K&R exercise 1-20. \$\endgroup\$ – 200_success Feb 16 '18 at 1:01
4
\$\begingroup\$

A good implementation of this problem. You've avoided some of the hurdles (such as remembering to store the result of getchar() in an int if you want to compare against EOF).

Most of what I say will be about style and readability.

Be consistent with your braces

We have a few different styles here:

int main()
{

Brace on its own line. I like that for function definitions (though others differ).

    while((c = getchar()) != EOF)
    {

Another brace getting its own line.

        if(c == ' ') {
            //increase the space count
            ++ns;
        }
        //else if the character read in is not a space
        else {

Here, the brace shares the same line as the if. And the else shares a line with only one of the braces.

            if(c == '\n')
                nc = ns = 0;
            else if(c != '\t')
                ++nc;

Here, we have no braces at all. While that's legal, it's a good idea to always include braces (and I was reminded so recently, when I posted my own code for review!).

I would write the above like this:

int main()
{
    while((c = getchar()) != EOF) {
        if(c == ' ') {
            ++ns;
        } else {
            // not a space
            if(c == '\n') {
                nc = ns = 0;
            } else if(c != '\t') {
                ++nc;
            }

Alternatively, as:

int main()
{
    while((c = getchar()) != EOF)
    {
        if(c == ' ')
        {
            ++ns;
        }
        else
        {
            // not a space
            if(c == '\n')
            {
                nc = ns = 0;
            }
            else if(c != '\t')
            {
                ++nc;
            }

Naming

It's quite conventional to use c for a variable holding the current character. But nc and ns are less obvious. You could change the names; alternatively, add comments where they are declared:

    int nc = 0;                 /* number of characters read in this line */
    int ns = 0;                 /* number of consecutive spaces seen */

Comments

Generally the comments are pretty good. I think you've over-commented a few things that are obvious to an experienced C programmer, but that's natural as you are learning - with experience, you'll recognise parts that are not idiomatic and concentrate your comments there, where they are most needed.

My personal taste is to avoid duplicating the code, so I wouldn't write "else" in the comment when it immediately follows an else in the code - I hope the samples below demonstrate what I mean.

Simplify loops

This loop is quite complex:

        //while one or more spaces are still "in buffer"
        while (ns > 0) {
            //decide whether gap in between chars is long enough for a space
            if (ns >= TABSIZE - nc) {
                //if it is, then place a tab, and remove that amount of spaces
                putchar('\t');
                ns -= TABSIZE;
            } else {
            // the gap is not big enough for spaces, just print them out individually
                putchar(' ');
                --ns;
            }
        }

We can replace with two simpler loops:

            //while one or more spaces are still "in buffer"
            while (ns >= TABSIZE - nc) {
                // place a tab, and remove as many spaces
                putchar('\t');
                ns -= TABSIZE;
            }
            while (ns > 0) {
                // use spaces
                putchar(' ');
                --ns;
            }

Finally

I'm not sure whether you've actually got the logic correct. Remember that a tab jumps to the next tab stop - it may be equivalent to less than 8 spaces. Have you tested with a variety of inputs (including tabs in input, and e.g. a run of 4 or 5 spaces after some non-space characters)?

The logic might be simpler if we keep track of current read column and current output column - at the end of a run of spaces we then just need to do the correct action to make the output column match the input column (using tabs where possible).

As a hint, if the current (0-based) column number is n, then a tab will advance the column number by TABSIZE - n % TABSIZE positions.

\$\endgroup\$
  • \$\begingroup\$ I had the % operand/something like that in the code but for some reason I removed it, I'll try to implement that to see if it gets rid of one or two cases where my program hasn't worked. I agree with advice on style and comments, I over-commented it to make sure that my approach was well understood, but I see how it was unnecessarily cluttered. And for the 2 simpler loops vs complex loop, I actually had my code set up like that, exactly like that, but I switched to this approach of one complex loop since I thought it would be more efficient this way. How can I see which is faster? \$\endgroup\$ – Matias Lago Feb 16 '18 at 1:44
  • \$\begingroup\$ Honestly, I wouldn't worry about which version is faster - you could do some benchmarking, but the difference is likely to be too small to measure (as a proportion of the whole function). Instead, I recommend you keep it easy to read and modify, and get your speed increases by asking your compiler to optimise for you. \$\endgroup\$ – Toby Speight Feb 16 '18 at 9:01
  • \$\begingroup\$ Sounds about right, thanks for the help! I've updated my code thanks to your advice (on my Gist) and I've linked to thank you and chax. Perhaps when I get more advanced in the book I can figure out some ways to benchmark code like this. \$\endgroup\$ – Matias Lago Feb 16 '18 at 12:54
2
\$\begingroup\$

Good stuff::

Good uniform layout, although I found the vertical spacing a bit excessive

Although comment count is more than "just right", I rather see one error on this side.


Incorrect logic

A tab '\t' advances to the the tab, short for tabulate, position. Code like ns >= TABSIZE - nc needs to reckon in modular math , perhaps ns >= TABSIZE - nc%TABSIZE.

Incorrect logic

nc needs to update in the block if(ns >= TABSIZE - nc).

Tab detection

When code reads a '\t, it should function like [1-TABSIZE] spaces, depending on position. Code does not do that.


Minor

Trailing spaces missing

Spaces just before the end of the line or end-of-file are not printed nor tabulated. Coding goals unclear, yet I would expect spaces/tabs there too.

RAII

With variable that are assigned early, initialize them instead.

// int c, nc, ns;
// nc = ns = 0;
int nc = 0;
int ns = 0;
int c;

Narrow the code.

If the horizontal scroll bar appears, then code is too wide for review, unless specifically designed otherwise. With an auto-formatter, this is an easy adjustment.


Advanced

end-of-file vs. input error

getchar() returns EOF on end-of-file or rare input error. If code is adjusted to print trailing spaces, it may want to handle end-of-file different from error.

Check I/O return values

Return value from putchar(c); ignored. Rarely does it fail, yet robust code would check this too.

Other common controls characters

Form feed '\f' and vertical tab '\v' could be treated much like '\n'


Respect

I gained a new respect for OP's coding challenge as I tried to code a fixed solution and found it more tricky that anticipated. Below is not well tested and I will self-review it later, but wanted to post to give OP ideas.

#include <stdio.h>
int space_flush(int *pos, int space_count, int tabsize) {
  *pos %= tabsize;  // We only really care about the position within a tab
  int charaters_to_next_tab = tabsize - *pos;

  while (space_count >= charaters_to_next_tab) {
    space_count -= charaters_to_next_tab;
    charaters_to_next_tab = tabsize;
    if (putchar('\t') == EOF) {
      return EOF;
    }
    *pos = 0;
  }

  while (space_count > 0) {
    space_count--;
    if (putchar(' ') == EOF) {
      return EOF;
    }
    (*pos)++;
  }
  return 0;
}

int tabify(int tabsize) {
  int pos = 0;
  int space_count = 0;

  int c;
  while ((c = getchar()) != EOF) {
    if (c == ' ') {
      space_count++;
    } else if (c == '\t') {
      space_count += tabsize - pos % tabsize;
    } else {
      if (space_count > 0) {
        if (space_flush(&pos, space_count, tabsize)) {
          return EOF;
        }
      }
      space_count = 0;
      if (putchar(c) == EOF) {
        return EOF;
      }
      pos++;
      if (c == '\n' || c == '\r' || c == '\f' || c == '\v') {
        pos = 0;
      }
    }
  }
  if (ferror(stdin)) { // Above loop quit due to input error, return with error.
    return EOF;
  }
  return space_flush(&pos, space_count, tabsize);
}


#define TABSIZE 8
int main(void) {
  if (tabify(TABSIZE)) {
    fprintf(stderr, "Error\n");
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}

Since de-tabbing makes more money @Edward, how about:

int untabify(int tabsize) {
  unsigned pos = 0;
  int c;
  while ((c = getchar()) != EOF) {
    if (c == '\t') {
      int space_count = tabsize - pos % tabsize;
      if (printf("%*s", space_count, "") < 0) {
        return EOF;
      }
      pos = 0;
    } else {
      if (putchar(c) == EOF) {
        return EOF;
      }
      pos++;
      if (c == '\n' || c == '\r' || c == '\f' || c == '\v') {
        pos = 0;
      }
    }
  }
  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice, I'll try to run some modifications to how I ran the logic to see if I can get some cases where my logic failed to work. If I solve the problem completely, I'll try to post it as an answer with all different inputs that it could take, so that others can evaluate some inputs to see if the program is robust enough or not. \$\endgroup\$ – Matias Lago Feb 16 '18 at 1:46
  • \$\begingroup\$ I've updated my solution to use your feedback & improve logic, please let me know what you think of it! Made a special note to thank you for noticing the lack of the number of characters being updated. \$\endgroup\$ – Matias Lago Feb 16 '18 at 2:28
  • \$\begingroup\$ @MatiasLago Test cases are a good idea. yet rather than append to your post (code has a number of weaknesses and flaws), rollback to its previous sates. You can post your own answer or post a new review if truly needed. \$\endgroup\$ – chux Feb 16 '18 at 3:11
  • \$\begingroup\$ I'm not sure I follow what you mean, but I'd like to point out that I'm still in Chapter 1 of K&R, so I haven't seen much of what your solution does nor anyone else would be who would be at that stage. I just edited my code to include the improvements based on your suggestions and on the limited scope that I'm expected to solve it (based on the Chapter I'm in). \$\endgroup\$ – Matias Lago Feb 16 '18 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.