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

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

After doing a lot of the problems on codingbat.com

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

Contents

  After doing a lot of the problems on codingbat.com chad <cdalten@gmail.com> - 2020-02-25 06:55 -0800
    Re: After doing a lot of the problems on codingbat.com Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-27 20:02 +0300
      Re: After doing a lot of the problems on codingbat.com James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-27 11:41 -0800
        Re: After doing a lot of the problems on codingbat.com Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-02-27 14:48 -0700
        Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-27 23:17 +0000
          Re: After doing a lot of the problems on codingbat.com James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-27 16:40 -0800
            Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-28 01:08 +0000
              Re: After doing a lot of the problems on codingbat.com Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-02-28 01:37 -0800
              Re: After doing a lot of the problems on codingbat.com James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-28 06:21 -0800
                Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-28 16:15 +0000
                  Re: After doing a lot of the problems on codingbat.com James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-28 10:37 -0800
                    Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-28 19:22 +0000
                  Re: After doing a lot of the problems on codingbat.com David Brown <david.brown@hesbynett.no> - 2020-03-01 14:54 +0100
                    Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-03-01 15:36 +0000
                      Re: After doing a lot of the problems on codingbat.com David Brown <david.brown@hesbynett.no> - 2020-03-01 17:08 +0100
            Re: After doing a lot of the problems on codingbat.com Richard Damon <Richard@Damon-Family.org> - 2020-02-27 21:57 -0500
            Really??? (Was: After doing a lot of the problems on codingbat.com) gazelle@shell.xmission.com (Kenny McCormack) - 2020-02-28 13:06 +0000
              Re: Really??? (Was: After doing a lot of the problems on codingbat.com) chad <cdalten@gmail.com> - 2020-02-28 05:47 -0800
              Re: Really??? (Was: After doing a lot of the problems on codingbat.com) James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-28 05:59 -0800
            Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-28 14:04 +0000
              Re: After doing a lot of the problems on codingbat.com Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-28 17:50 +0000
                Re: After doing a lot of the problems on codingbat.com Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-28 20:59 +0300
                  Re: After doing a lot of the problems on codingbat.com Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-28 22:37 +0000
                Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-29 00:17 +0000
                  Re: After doing a lot of the problems on codingbat.com Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-29 01:01 +0000
          Re: After doing a lot of the problems on codingbat.com Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-04-02 19:22 -0700
      Re: After doing a lot of the problems on codingbat.com Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-02-27 14:52 -0500
        Re: After doing a lot of the problems on codingbat.com Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-27 20:42 +0000
          Re: After doing a lot of the problems on codingbat.com David Brown <david.brown@hesbynett.no> - 2020-02-27 22:59 +0100
        Re: After doing a lot of the problems on codingbat.com Bart <bc@freeuk.com> - 2020-02-27 20:48 +0000
        Re: After doing a lot of the problems on codingbat.com Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-03-27 20:06 -0700
      Re: After doing a lot of the problems on codingbat.com chad <cdalten@gmail.com> - 2020-02-27 15:28 -0800

Page 2 of 2 — ← Prev page 1 [2]

#150337

Bart <bc@freeuk.com> writes:
<cut>
> Fortran loops are a good example. They are necessarily limited in what
> they do, and that makes it very easy to reason about compared with the
> myriad variations that can be introduced with C's for as I showed in
> my other post.

You've forgotten how hard to reason about they were!  Fortran's DO was a
mess.

-- 
Ben.

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

#150338

Ben Bacarisse:

> You've forgotten how hard to reason about they were!
> Fortran's DO was a mess.

Perhaps Modula and Pascal loops are better examples?

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

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

#150345

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Ben Bacarisse:
>
>> You've forgotten how hard to reason about they were!
>> Fortran's DO was a mess.
>
> Perhaps Modula and Pascal loops are better examples?

Yes.  I'd say pretty much any other language that has a counted loop
would be a better example!

-- 
Ben.

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

#150347

On 28/02/2020 17:50, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> <cut>
>> Fortran loops are a good example. They are necessarily limited in what
>> they do, and that makes it very easy to reason about compared with the
>> myriad variations that can be introduced with C's for as I showed in
>> my other post.
> 
> You've forgotten how hard to reason about they were!  Fortran's DO was a
> mess.
> 

What have I forgotten? As I recall they looked like this:

     DO 100 I=1,10
     ....
100 CONTINUE

What can go wrong with that? (Other than the label being located before 
the loop, or in the middle of another, but that was a general issue with 
spaghetti code.)

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

#150348

Bart <bc@freeuk.com> writes:

> On 28/02/2020 17:50, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>> <cut>
>>> Fortran loops are a good example. They are necessarily limited in what
>>> they do, and that makes it very easy to reason about compared with the
>>> myriad variations that can be introduced with C's for as I showed in
>>> my other post.
>>
>> You've forgotten how hard to reason about they were!  Fortran's DO was a
>> mess.
>>
>
> What have I forgotten? As I recall they looked like this:
>
>     DO 100 I=1,10
>     ....
> 100 CONTINUE
>
> What can go wrong with that? (Other than the label being located
> before the loop, or in the middle of another, but that was a general
> issue with spaghetti code.)

And loads of other things.  If you want to be reminded of how messy the
definition is, read up on what a do loop with extended range is.  If I
recall correctly, it's only about three dense paragraphs.

-- 
Ben.

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

#150969

Bart <bc@freeuk.com> writes:

> On 27/02/2020 19:41, James Kuyper wrote:
>
>> On Thursday, February 27, 2020 at 12:02:53 PM UTC-5, Anton Shepelev wrote:
>>
>>> chad:
>>>
>>>> I've come to this horrible realization that I don't
>>>> understand a for loop as well as what I thought I did.
>>>
>>> Just don't abuse the for loop, cramping all kinds of
>>> unrelated code into its control expressions. ...
>>
>> I'm in full agreement with that.
>>
>>> ... Always use\
>>> it as a loop with a counter:
>>
>> But I can't agree that there's anything wrong with using any of the
>> following constructs:
>>
>> for(unsigned mask = 0x8000; mask;  mask >>=1)
>>
>> for(Node* node=head; node;  node = node->next)
>>
>> The first three user-controlled parts of a for-statement should be
>> reserved for loop-control, but there's many different ways to handle
>> loop control.
>
>     unsigned mask = 0x8000h
>     while (mask) {
>         body;
>         mask >>= 1;
>     }
>
>     Node * node = head;
>     while (node) {
>         body;
>         node = node->next;
>     }

It appears someone has a severe case of Old Dog syndrome.

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

#150306

Anton Shepelev wrote:

> chad:
> 
>> I've come to this horrible realization that I don't
>> understand a for loop as well as what I thought I did.
> 
> Just don't abuse the for loop, cramping all kinds of
> unrelated code into its control expressions.  Always use\
> it as a loop with a counter:
[snip]

Good advice to someone who doesn't understand how to use a for() loop.

However, once chad gets past the basic understanding, there's a lot more you 
can do with for() than just count loops

You can
 - find the end of a string
   char *ptr;
   for (ptr = "string" ; *ptr ; ++ptr) continue;

- or count the number of characters
   char *ptr;
   size_t nchars;
   for (ptr = "string", nchars = 0 ; *ptr ; ++ptr) ++nchars;

 - or traverse a linked list
   struct list { struct list *next; int valu; } *root = NULL;
   /* ... */
  for (struct list *node = root; node; node = node->next)
  {
    /* do something with this node */
  }

- or even perform a binary search through an ordered array
int *binsearch(int key, int array[], size_t nelement)
{
  size_t lowpt = 0,             /* lowest index in search range */
         midpt,                 /* midpoint index; where to search */
         highpt = nelement - 1; /* highest index in search range */

  /* LOOP through search UNTIL match found OR no elements left to search */
  for (midpt = (lowpt+highpt)/2;                /* start in the middle */
       array[midpt] != key && highpt > lowpt;   /* not found AND in bounds*/
       midpt = (lowpt+highpt)/2)                /* compute new midpoint */
  { /* ============================ **
    ** array[midpt] was NOT a match **
    ** ============================ */
    if (key > array[midpt])
      lowpt = midpt + 1;        /* narrow search to between here and high */
    else
      highpt = midpt - 1;       /* narrow search to beween low and here */
  }

  /* loop terminates when entry found OR no more array to search */

  return (array[midpt] == key ? array+midpt : NULL);
}

A good programmer doesn't limit themselves to using for() strictly as a 
counted loop.

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

#150307

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

> Anton Shepelev wrote:
>
>> chad:
>> 
>>> I've come to this horrible realization that I don't
>>> understand a for loop as well as what I thought I did.
>> 
>> Just don't abuse the for loop, cramping all kinds of
>> unrelated code into its control expressions.  Always use\
>> it as a loop with a counter:
> [snip]
>
> Good advice to someone who doesn't understand how to use a for() loop.
>
> However, once chad gets past the basic understanding, there's a lot more you 
> can do with for() than just count loops
>
> You can
>  - find the end of a string
>    char *ptr;
>    for (ptr = "string" ; *ptr ; ++ptr) continue;

     char *ptr = strchr("string", 0);

> - or count the number of characters
>    char *ptr;
>    size_t nchars;
>    for (ptr = "string", nchars = 0 ; *ptr ; ++ptr) ++nchars;

     size_t nchars = strlen("string");

Obviously you know about these function, but it's way better to give
examples that aren't re-inventing the wheel.  Pointer scanning is a
common use of a 'for' loop but I'd choose a task that isn't a library
function:

    size_t count = 0;
    for (const char *ptr = str; *ptr; ptr++)
         if (*ptr == ' ')
             count += 1;

>  - or traverse a linked list
>    struct list { struct list *next; int valu; } *root = NULL;
>    /* ... */
>   for (struct list *node = root; node; node = node->next)
>   {
>     /* do something with this node */
>   }
>
> - or even perform a binary search through an ordered array
> int *binsearch(int key, int array[], size_t nelement)
> {
>   size_t lowpt = 0,             /* lowest index in search range */
>          midpt,                 /* midpoint index; where to search */
>          highpt = nelement - 1; /* highest index in search range */

This function can't search and empty array.  For that reason, I prefer
to keep the search in a half-open interval [low, high).

>   /* LOOP through search UNTIL match found OR no elements left to search */
>   for (midpt = (lowpt+highpt)/2;                /* start in the middle */
>        array[midpt] != key && highpt > lowpt;   /* not found AND in bounds*/
>        midpt = (lowpt+highpt)/2)                /* compute new midpoint */
>   { /* ============================ **
>     ** array[midpt] was NOT a match **
>     ** ============================ */
>     if (key > array[midpt])
>       lowpt = midpt + 1;        /* narrow search to between here and high */
>     else
>       highpt = midpt - 1;       /* narrow search to beween low and here */
>   }
>
>   /* loop terminates when entry found OR no more array to search */
>
>   return (array[midpt] == key ? array+midpt : NULL);
> }

For me, this is a step too far.  The double midpt calculation and test
for both array[midpt] != key and array[midpt] == key would make me
investigate alternatives.  I think I've always ended up using a while
loop for this sort of search.

> A good programmer doesn't limit themselves to using for() strictly as a 
> counted loop.

Ack.

-- 
Ben.

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

#150310

On 27/02/2020 21:42, Ben Bacarisse wrote:
> Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:
<snip>
> For me, this is a step too far.  The double midpt calculation and test
> for both array[midpt] != key and array[midpt] == key would make me
> investigate alternatives.  I think I've always ended up using a while
> loop for this sort of search.
> 
>> A good programmer doesn't limit themselves to using for() strictly as a
>> counted loop.
> 
> Ack.
> 


To me, a "for" loop does :

1. Set up the start of an iterator.
2. Check for an end condition.
3. Make a step from the start towards the end.

If it is not obvious what each of these steps are, how they work, and 
that they /do/ work, then there is too much in the "for" clauses which 
should be moved before the "for" loop or inside it.

I've got to know that iteration moves forward from a start to an end - 
that every round of the loop makes progress, and that you will reach an 
end.  (My code almost invariably has a "while (true)" main loop, due to 
the nature of my target systems, but that's a different matter.)

If the clauses need to be spread over several lines - either due to 
their length, or to leave space for comments - then they are highly 
unlikely to be "obvious".

I'm fine with pointer steps and the like in "for" loop clauses.  But I 
don't like doing much calculation in them.

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

#150308

On 27/02/2020 19:52, Lew Pitcher wrote:
> Anton Shepelev wrote:
> 
>> chad:
>>
>>> I've come to this horrible realization that I don't
>>> understand a for loop as well as what I thought I did.
>>
>> Just don't abuse the for loop, cramping all kinds of
>> unrelated code into its control expressions.  Always use\
>> it as a loop with a counter:
> [snip]
> 
> Good advice to someone who doesn't understand how to use a for() loop.
> 
> However, once chad gets past the basic understanding, there's a lot more you
> can do with for() than just count loops
> 
> You can
>   - find the end of a string
>     char *ptr;
>     for (ptr = "string" ; *ptr ; ++ptr) continue;
> 
> - or count the number of characters
>     char *ptr;
>     size_t nchars;
>     for (ptr = "string", nchars = 0 ; *ptr ; ++ptr) ++nchars;
> 
>   - or traverse a linked list
>     struct list { struct list *next; int valu; } *root = NULL;
>     /* ... */
>    for (struct list *node = root; node; node = node->next)
>    {
>      /* do something with this node */
>    }
> 
> - or even perform a binary search through an ordered array
> int *binsearch(int key, int array[], size_t nelement)
> {
>    size_t lowpt = 0,             /* lowest index in search range */
>           midpt,                 /* midpoint index; where to search */
>           highpt = nelement - 1; /* highest index in search range */
> 
>    /* LOOP through search UNTIL match found OR no elements left to search */
>    for (midpt = (lowpt+highpt)/2;                /* start in the middle */
>         array[midpt] != key && highpt > lowpt;   /* not found AND in bounds*/
>         midpt = (lowpt+highpt)/2)                /* compute new midpoint */
>    { /* ============================ **
>      ** array[midpt] was NOT a match **
>      ** ============================ */
>      if (key > array[midpt])
>        lowpt = midpt + 1;        /* narrow search to between here and high */
>      else
>        highpt = midpt - 1;       /* narrow search to beween low and here */
>    }
> 
>    /* loop terminates when entry found OR no more array to search */
> 
>    return (array[midpt] == key ? array+midpt : NULL);
> }
> 
> A good programmer doesn't limit themselves to using for() strictly as a
> counted loop.
> 

That's great for them. For anyone else trying to read the code, every 
for-loop needs to be analysed to see which of these categories it fits it:

   (1) Endless loop
   (2) Repeat-N-time loop that doesn't use the loop index
   (3) Repeat-N-time loop that uses the loop index
   (4) Simple iteration from A to B (either inclusive or exclusive)
       stepped by C, and either counting up or down
   (5) Simple while-loop
   (6) Anything slightly different (eg. using a float loop index)
   (7) Everything else

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

#150868

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

[...]

> there's a lot more you can do with for() than just count loops
> [examples]
>
> - or even perform a binary search through an ordered array
> int *binsearch(int key, int array[], size_t nelement)
> {
>   size_t lowpt = 0,             /* lowest index in search range */
>          midpt,                 /* midpoint index;  where to search */
>          highpt = nelement - 1; /* highest index in search range */
>
>   /* LOOP through search UNTIL match found OR no elements left to search */
>   for (midpt = (lowpt+highpt)/2;                /* start in the middle */
>        array[midpt] != key && highpt > lowpt;   /* not found AND in bounds*/
>        midpt = (lowpt+highpt)/2)                /* compute new midpoint */
>   { /* ============================ **
>     ** array[midpt] was NOT a match **
>     ** ============================ */
>     if (key > array[midpt])
>       lowpt = midpt + 1;        /* narrow search to between here and high */
>     else
>       highpt = midpt - 1;       /* narrow search to beween low and here */
>   }
>
>   /* loop terminates when entry found OR no more array to search */
>
>   return (array[midpt] == key ? array+midpt : NULL);
> }

    int *
    search( int a[], unsigned n, int key ){
        return  n < 1            ?   0
            :   n == 1           ?   *a == key ? a : 0
            :   a[ n/2 ] > key   ?   search( a,     n/2,   key )
            :                        search( a+n/2, n-n/2, key );
    }

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

#150315

On Thursday, February 27, 2020 at 9:02:53 AM UTC-8, Anton Shepelev wrote:
> chad:
> 
> > I've come to this horrible realization that I don't
> > understand a for loop as well as what I thought I did.
> 
> Just don't abuse the for loop, cramping all kinds of
> unrelated code into its control expressions.  Always use\
> it as a loop with a counter:
> 

There are a few winner problems on codingbat where a for loop really doesn't work. But it does work using a while loop. From what I can tell via the debugger, the for loop increments then enters the loop. While a while loop can enter a loop and the increment. 

And this distinction appears to matter for the following problem..

https://codingbat.com/prob/p170829

And I quote

"Given a string and a non-empty word string, return a version of the original String where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.

plusOut("12xy34", "xy") → "++xy++"
plusOut("12xy34", "1") → "1+++++"
plusOut("12xy34xyabcxy", "xy") → "++xy++xy+++xy"
"

I tried to attack this using a for loop, and it doesn't quite work for the test cases given on this site. But it does work for all the test cases if I use a while loop.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web