Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #157059 > unrolled thread

Programming challenge

Back to article view | Back to comp.lang.c

Contents

  Programming challenge jacobnavia <jacob@jacob.remcomp.fr> - 2020-12-08 00:04 +0100
    Re: Programming challenge Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-12-07 23:33 +0000
      Re: Programming challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-08 23:52 -0800
      Re: Programming challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-13 21:35 -0800
        Re: Programming challenge Anton Shepelev <anton.txt@gmail.com> - 2020-12-14 11:55 +0300
          Re: Programming challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-14 08:45 -0800
          Re: Programming challenge Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-12-18 07:19 +0000
    Re: Programming challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-08 01:36 +0000
      Re: Programming challenge Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-08 02:49 +0000
        Re: Programming challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-08 14:51 +0000
          Re: Programming challenge Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-08 17:32 +0000
        Re: Programming challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-12 19:31 -0800
      Re: Programming challenge jacobnavia <jacob@jacob.remcomp.fr> - 2020-12-08 08:17 +0100
        Re: Programming challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-08 14:15 +0000

#157059 — Programming challenge

Here is my answer to the programming contest of Mr Rentsch. Sorry, it is 
just straight C, no gotos, and fairly easy to follow. Thanks to Bart for 
pointing me to a bug in it. Since I haven't seen any other answers I 
suppose I win by default...
Sad, it was an interesting exercise.

I tried to keep it:
1) SMALL. t is just around 1K size of instructions in the ARM machine
2) Structured programming (no gotos)
3) Smallest number of variables: An input file and the current character.
4) Everything is in the main() function.

jacob

-----------------------------------------------------------------------
#include <stdio.h>
#include <ctype.h>
/* This program will eliminate comments from a C source file given
    in the command line. It returns 5 if an abnormal eof was found
    in a single line comment, 6 if EOF was found in a multi-line
    comment, 7 if EOF appeared within a string, 8 if EOF occurred
    within a character quote sequence. If all is OK the result is zero.
*/
int main(int argc,char *argv[])
{
     if (argc < 2) { // print usage
         fprintf(stderr,"Usage: nocomments <file>\n");
         return 3;
     }
     FILE *f=fopen(argv[1],"r");
     // Note that this file is never closed. We rely on the operating
     // system to close it for us.
     if (f == NULL) { // Error can't open
         fprintf(stderr,"Impossible to open %s\n",argv[1]);
         return 4;
     }
     int c = fgetc(f);
     while (c != EOF) { // Until the end of the file
         // There are 3 characters that have a special action required:
         // 1) The / character that could introduce a comment
         // 2) The " character that introduces a string
         // 3) the ' character that introduces a character constant
         if (c == '/') { // test for a comment
             c = fgetc(f);
             if (c == EOF) return 5;
             if (c == '/') { // this is a comment until the end of the line
                 while (c != '\n' && c != EOF) {
                     c = fgetc(f); // ignore everything
                 }
                 if (c == EOF) return 5;
                 putchar(c); // Put the new line char
             }
             else if (c == '*') { // Multi line comment
                 while (c != EOF) {
                     c = fgetc(f);
                     if (c == EOF) return 6;
                     else if (c == '*') {
                         c = fgetc(f);
                         if (c == '/') break; // Ends multi-line comment
                 /* If we have just read a '*' we know we should look
                    for a slash. But if we just go on, we will read the
                    slash without knowing that it was preceeded by a '*'
                 */
                         if (c == '*') {
                             ungetc(c,f);
                         }
                     }
                 }
                 if (c == EOF) return 6;
             // We do NOT echo the final '/':  it belongs to the comment
             }
             else if (c == '\\') {
                 c = fgetc(f);
                 if (c == '\n') { // Line splitting borderline case
                     c = fgetc(f);
                     if (c== '/') {
                         while (c != EOF && c != '\n') {
                             c = fgetc(f);
                         }
                         if (c == EOF) return 5;
                     }
                     else { putchar('\\'); }
                 }
                 putchar(c);
             }
             else { // That was a lone /
                 putchar('/');
                 putchar(c);
             }
         }
         else if (c == '"') { // String
             putchar(c);
             c = fgetc(f);
             while (c != EOF && c != '"') {
                 putchar(c);
                 if (c == '\\') {
                     c = fgetc(f);
                     if (c == EOF) return 7;
                     putchar(c);
                 }
                 c = fgetc(f); // Read the next char of the string
             }
             if (c == EOF) return 7;
             putchar(c); // put the closing double quote
         }
         else if (c == '\'') { // Character constant
             putchar(c);
             c = fgetc(f);
             while (c != '\'' && c != EOF) {
                 if (c == '\\') { // escaped char
                     putchar(c);
                     c = fgetc(f);
                     if (c == EOF) return 8;
                 }
                 putchar(c); // Not an escaped char, just a normal one
                 c = fgetc(f);
             }
             if (c == EOF) return 8;
             else putchar(c); // Put the closing quote
         }
         else putchar(c); // All other characters are echoed back
         c = fgetc(f);   // Read next character of the source file
     }
     return 0; // No errors
}

[toc] | [next] | [standalone]

#157062

On Tue, 08 Dec 2020 00:04:56 +0100, jacobnavia wrote:

> Here is my answer to the programming contest of Mr Rentsch. Sorry, it is
> just straight C, no gotos, and fairly easy to follow. Thanks to Bart for
> pointing me to a bug in it. Since I haven't seen any other answers I
> suppose I win by default...
> Sad, it was an interesting exercise.
[snip]

Someone should update the CLC wiki with all these solutions.
Could they be fit under 
  https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23
or maybe go into their own category.

-- 
Lew Pitcher
"In Skills, We Trust"

[toc] | [prev] | [next] | [standalone]

#157129

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Tue, 08 Dec 2020 00:04:56 +0100, jacobnavia wrote:
>
>> Here is my answer to the programming contest of Mr Rentsch.  Sorry, it is
>> just straight C, no gotos, and fairly easy to follow.  Thanks to Bart for
>> pointing me to a bug in it.  Since I haven't seen any other answers I
>> suppose I win by default...
>> Sad, it was an interesting exercise.
>
> [snip]
>
> Someone should update the CLC wiki with all these solutions.
> Could they be fit under
>   https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23
> or maybe go into their own category.

Interesting suggestion.  I will try to look at this further
in the next day or two and post some sort of update here.

[toc] | [prev] | [next] | [standalone]

#157261

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Tue, 08 Dec 2020 00:04:56 +0100, jacobnavia wrote:
>
>> Here is my answer to the programming contest of Mr Rentsch.  Sorry, it is
>> just straight C, no gotos, and fairly easy to follow.  Thanks to Bart for
>> pointing me to a bug in it.  Since I haven't seen any other answers I
>> suppose I win by default...
>> Sad, it was an interesting exercise.
>
> [snip]
>
> Someone should update the CLC wiki with all these solutions.
> Could they be fit under
>   https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23
> or maybe go into their own category.

I have looked at this in more detail now.  I have three main
reactions.

(1) My sense is these new solutions belong in a different
category, because the original problem (K&R chapt 1 ex 23)
was more modest.  Is it possible to create a new category
that links in some way with the existing solutions page?

(2) I don't know my way around the CLC wiki website very well
(hardly at all in fact).  It would be nice to get help from
someone who does.  Are there any administrators currently active?

(3) In any case I will not be putting any code on the wiki,
except possibly my own, to be sure I don't run afoul of the
site's copyright policy, and also out of general consideration
for others' sense of proprieties.

[toc] | [prev] | [next] | [standalone]

#157262

Tim Rentsch about:
https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23

> My sense is these new solutions belong in a different
> category, because the original problem (K&R chapt 1 ex 23)
> was more modest.

I agree.  I think that is a poorly written page. Each
solution should be preceeded by a list of its bugs or
limitations, so that the reader may know what to expect of
it.

> Is it possible to create a new category that links in some
> way with the existing solutions page?

The simplest thing would be to add a "See also" notice to
the beginning or end of the page

> I don't know my way around the CLC wiki website very well
> (hardly at all in fact).  It would be nice to get help
> from someone who does.  Are there any administrators
> currently active?

Looks like it is the same engine that Wikipedia uses, so the
documentation & help should be available here:

   https://www.mediawiki.org/wiki/MediaWiki

Whoever is proficient in Wikipedia can work in CLC Wiki.  I
have edited Wikipedia pages, but found its markup language
exceedingly cumbersome. It is not a truly plain-text
language, for it does not support line continuations and
cannot handle all hard line breaks properly.

> In any case I will not be putting any code on the wiki,
> except possibly my own, to be sure I don't run afoul of
> the site's copyright policy, and also out of general
> consideration for others' sense of proprieties.

I see no problem, for the code is already publicly available
here in Usenet.  If the page is created, I will gladly add
my solution to it.

P.S.: I should like to create a page to my pattern-matching
      exercise, too.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#157265

Anton Shepelev <anton.txt@gmail.com> writes:

> Tim Rentsch about:
> https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23
>
>> I don't know my way around the CLC wiki website very well
>> (hardly at all in fact).  [...]
>
> Looks like it is the same engine that Wikipedia uses, so the
> documentation & help should be available here:
>
>    https://www.mediawiki.org/wiki/MediaWiki

Thank you for the link.

>> In any case I will not be putting any code on the wiki,
>> except possibly my own, to be sure I don't run afoul of
>> the site's copyright policy, and also out of general
>> consideration for others' sense of proprieties.
>
> I see no problem, for the code is already publicly available
> here in Usenet.  [...]

I don't know what the clc-wiki expects, or if what they expect
is consistent with the relevant law.  Even if the law allows it,
and even if clc-wiki considers it okay, I still wouldn't put up
something written entirely by someone else without their express
and specifically explicit permission.  (And maybe not even then,
but that is a necessary prerequisite.)

[toc] | [prev] | [next] | [standalone]

#157381

On Mon, 2020-12-14, Anton Shepelev wrote:
> Tim Rentsch about:
> https://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_23

...
>> I don't know my way around the CLC wiki website very well
>> (hardly at all in fact).  It would be nice to get help
>> from someone who does.  Are there any administrators
>> currently active?
>
> Looks like it is the same engine that Wikipedia uses, so the
> documentation & help should be available here:
>
>    https://www.mediawiki.org/wiki/MediaWiki
>
> Whoever is proficient in Wikipedia can work in CLC Wiki.  I
> have edited Wikipedia pages, but found its markup language
> exceedingly cumbersome. It is not a truly plain-text
> language, for it does not support line continuations and
> cannot handle all hard line breaks properly.

Where can I read about the definition of true plain-text languages?

FWIW, I find the Mediawiki markup language ok, but not great.  The
whole system, with templates, categories, history, "what links here",
discussion pages and so on is great.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#157068

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Here is my answer to the programming contest of Mr Rentsch.

You don't seem to handle \<newline> continuations properly.

> Sorry, it
> is just straight C, no gotos, and fairly easy to follow. Thanks to
> Bart for pointing me to a bug in it. Since I haven't seen any other
> answers I suppose I win by default...

I'm sure I've seen others.  Not checked the times on posts so maybe
there were none (other than Kaz's) when you posted.  But give it time...
People have other stuff to do, and some will be motivated by seeing
solutions.

> Sad, it was an interesting exercise.

I prefer the exercise I solved!  (But then I would, wouldn't I?)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#157075

On 2020-12-08, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> jacobnavia <jacob@jacob.remcomp.fr> writes:
>
>> Here is my answer to the programming contest of Mr Rentsch.
>
> You don't seem to handle \<newline> continuations properly.
>
>> Sorry, it
>> is just straight C, no gotos, and fairly easy to follow. Thanks to
>> Bart for pointing me to a bug in it. Since I haven't seen any other
>> answers I suppose I win by default...
>
> I'm sure I've seen others.  Not checked the times on posts so maybe
> there were none (other than Kaz's) when you posted.  But give it time...
> People have other stuff to do, and some will be motivated by seeing
> solutions.

This has been interesting.

As a result, I have become convinced to use pure goto for this kind of
thing in the future instead of a state machine with a switch (state),
which then handles character cases in the various states.

I have used that pattern countless times.

My original s2getc routine (get char from translation stage 2, taking
care of backslash continuations) looks like this:

int s2getc(void)
{
  int ch;

entry:
  ch = getchar();
  if (ch != '\\')
    goto end;

  ch = getchar();
  if (ch == '\n')
    goto entry;

  if (ch == EOF) {
    ch = '\\';
    goto end;
  }

  ungetc(ch, stdin);
  ch = '\\';

end:
  return ch;
}

Under the state machine approach, it just gets longer, with no benefit: it's
still just goto in disguise:

int s2getc(void)
{
  enum { init, bslash, end } state = init;
  int ch;

  while (state != end) {
    ch = getchar();
    switch (state) {
    case init:
      if (ch == '\\')
        state = bslash;
      else
        state = end;
      break;
    case bslash:
      switch (ch) {
      case '\n':
        state = init;
        break;
      default:
        ungetc(ch, stdin);
        ch = '\\';
        /* fallthrough */
      case EOF:
        state = end;
        break;
      }
      break;
    case end:
      abort();
    }
  }

  return ch;
}

The nice thing about the state machine approach is that it has the character
reading and termination test in one place. The goto graph has lots of calls to
the input routine, and checks for EOF in many places.
The state transition actions, like getting an input symbol, can be put into a
function, though. Repeating a function call isn't necessarily so bad.

Looking at Jacob's solution, I don't find it as readable as the state
machine approach, and it's not his fault: it's a good example of that approach.
It's that whole approach.

It shares the disadvantages of the goto approach (multiple calls to fgetc
scattered throughout the code), without the simple graph structure.

My goto code mostly has a regular structure consisting of blocks that look like
this:

   label: // meaningful!
     ch = getchar();
     // test ch for various cases and goto elsewhere
     // default goto somewhere

You could crank this out after having drawn a bubble-and-arrow diagram.
A bubble and arrow diagram could be compiled into this directly.

More importantly, it easily maps *backwards* to an understandable
bubble-and-arrow diagram.  Possibly automatically.

-- 
TXR Programming Language: http://nongnu.org/txr

[toc] | [prev] | [next] | [standalone]

#157090

Kaz Kylheku <563-365-8930@kylheku.com> writes:

> On 2020-12-08, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> jacobnavia <jacob@jacob.remcomp.fr> writes:
>>
>>> Here is my answer to the programming contest of Mr Rentsch.
>>
>> You don't seem to handle \<newline> continuations properly.
>>
>>> Sorry, it
>>> is just straight C, no gotos, and fairly easy to follow. Thanks to
>>> Bart for pointing me to a bug in it. Since I haven't seen any other
>>> answers I suppose I win by default...
>>
>> I'm sure I've seen others.  Not checked the times on posts so maybe
>> there were none (other than Kaz's) when you posted.  But give it time...
>> People have other stuff to do, and some will be motivated by seeing
>> solutions.
>
> This has been interesting.

I agree, but that's because we are both solving the wrong exercise!

> As a result, I have become convinced to use pure goto for this kind of
> thing in the future instead of a state machine with a switch (state),
> which then handles character cases in the various states.
>
> I have used that pattern countless times.
>
> My original s2getc routine (get char from translation stage 2, taking
> care of backslash continuations) looks like this:
>
> int s2getc(void)
> {
>   int ch;
>
> entry:
>   ch = getchar();
>   if (ch != '\\')
>     goto end;
>
>   ch = getchar();
>   if (ch == '\n')
>     goto entry;
>
>   if (ch == EOF) {
>     ch = '\\';
>     goto end;
>   }
>
>   ungetc(ch, stdin);
>   ch = '\\';
>
> end:
>   return ch;
> }
>
> int s2getc(void)
> {
>   enum { init, bslash, end } state = init;
>   int ch;
>
>   while (state != end) {
>     ch = getchar();
>     switch (state) {
>     case init:
>       if (ch == '\\')
>         state = bslash;
>       else
>         state = end;
>       break;
>     case bslash:
>       switch (ch) {
>       case '\n':
>         state = init;
>         break;
>       default:
>         ungetc(ch, stdin);
>         ch = '\\';
>         /* fallthrough */
>       case EOF:
>         state = end;
>         break;
>       }
>       break;
>     case end:
>       abort();
>     }
>   }
>
>   return ch;
> }

I'd write:

  int s2getc_nr(void)
  {
       int cur = getchar(), next;
       while (cur == '\\' && (next = getchar()) == '\n')
            cur = getchar();
       if (cur == '\\')
            ungetc(next, stdin);
       return cur;
  }

> The nice thing about the state machine approach is that it has the character
> reading and termination test in one place. The goto graph has lots of calls to
> the input routine, and checks for EOF in many places.
> The state transition actions, like getting an input symbol, can be put into a
> function, though. Repeating a function call isn't necessarily so bad.
>
> Looking at Jacob's solution, I don't find it as readable as the state
> machine approach, and it's not his fault: it's a good example of that approach.
> It's that whole approach.
>
> It shares the disadvantages of the goto approach (multiple calls to fgetc
> scattered throughout the code), without the simple graph structure.
>
> My goto code mostly has a regular structure consisting of blocks that look like
> this:
>
>    label: // meaningful!
>      ch = getchar();
>      // test ch for various cases and goto elsewhere
>      // default goto somewhere
>
> You could crank this out after having drawn a bubble-and-arrow diagram.
> A bubble and arrow diagram could be compiled into this directly.
>
> More importantly, it easily maps *backwards* to an understandable
> bubble-and-arrow diagram.  Possibly automatically.

I find mine easier to reason/think about.  But I am sure that depends on
prior experience -- I'm just used to that style.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#157093

On 2020-12-08, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> I'd write:
>
>   int s2getc_nr(void)
>   {
>        int cur = getchar(), next;
>        while (cur == '\\' && (next = getchar()) == '\n')
>             cur = getchar();
>        if (cur == '\\')
>             ungetc(next, stdin);
>        return cur;
>   }

Right; but in non-strawman examples, I'm usually doing more complicated
things, so I have justification in using a state machine formalism
with labeled states and transitions.

I'm effectively "hand compiling" a specification, which is in the form
of a state transition diagram or table.

In doing this exercise, I've found that just writing goto graph in the
code may be a nicer target for that hand compiling than, specifically,
the loop around a state switch structure.

It really is just extra clutter which expresses the same thing, with
nearly he same structure.

The lesson may be that we should use switch for "surprising" values,
like run-time inputs, and not something controlled by he program, like a
state variable. If you're finding yourself doing "state = ST42" in order
to induce a switch to branch to a case, maybe it should be a goto.

In he "goto graph", switch can be used for he run-time inputs:

Rather than:

  slash:
    ch = s2getc();
    if (ch == EOF)
      goto end;
    if (ch == '*')
      goto slashstar;
    if (ch == '/')
      goto slashslash;
    putchar('/');
    goto outstart;

this:

   slash:
     switch (s2getc()) {
     case EOF: goto end;
     case '*': goto slashstar;
     case '/': goto slashslash;
     default:
       putchar('/');
       goto outstart;
     }

I.e. use switch to pair inputs with goto transitions. Look at how we
don't need any cluttering break statements anywhere, keeping it clean.

   slash: // STATE

     switch (s2getc()) {
     //   SYM   ACTION                       NEXT STATE
     case EOF:                          goto end;
     case '*':                          goto slashstar;
     case '/':                          goto slashslash;
     default:   putchar('/');           goto outstart;
     }

The relation to a structure with while loops is a separate matter;
undoubtedly the above s2getc_nr is a nice alternative for that function,
where the state machine is overkill.

[toc] | [prev] | [next] | [standalone]

#157246

Kaz Kylheku <563-365-8930@kylheku.com> writes:

[...]

> This has been interesting.
>
> As a result, I have become convinced to use pure goto for this
> kind of thing in the future instead of a state machine with a
> switch (state), which then handles character cases in the various
> states.

Isn't it the case that all the programs you posted made extensive
use of goto?  If you never actually tried yourself any other
approaches it isn't surprising your opinion is stuck in the
same place.

[toc] | [prev] | [next] | [standalone]

#157076

Le 08/12/2020 à 02:36, Ben Bacarisse a écrit :
> You don't seem to handle \<newline> continuations properly.

Well, I do handle correctly
\
/ this will accepted as a comment!

I didn't bother with the possible
\
* Multi line comment?
*/

I am not sure that the standard requires this, but I did not check

[toc] | [prev] | [next] | [standalone]

#157084

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Le 08/12/2020 à 02:36, Ben Bacarisse a écrit :
>> You don't seem to handle \<newline> continuations properly.
>
> Well, I do handle correctly
> \
> / this will accepted as a comment!

That's not a comment.  Presumably you mean

/\
/ This is a comment

I knew you'd addressed that specific case, but why not all the other
cases of \<newline> handling?  It's an entirely general mechanism.

> I didn't bother with the possible
> \
> * Multi line comment?
> */
>
> I am not sure that the standard requires this, but I did not check

That's a odd comment coming from a C compiler writer!

-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web