Practicing algorithms in C or C++98 to make things harder

[Jamin2112]

Is it a good idea to do "coding drills" in C or C++98 just to make things harder? I've been doing that and it seems to help because there's so much more I need to think about in order to cover all the corner cases and make things compact. It's like practicing baseball with a weighted bat

so that swinging with a regular bat feels easier.

For instance, I just did

#include <iostream>

bool contains ( int * sarr, size_t n, int i) // checks whether the integer i is in the sorted array sarr of length n
{
  
    int * pa(sarr), * pb(sarr + n);
    if (pa == pb) return false;
    --pb;
    while (pa != pb && ((pb - pa) != 1))
    {
        int * pc = pa + (pb - pa)/2;
        if (*pc < i) pa = pc;
        else pb = pc;
    }
    if (*pa == i || *pb == i) return true;
    else return false;
}int main ()
{
    int A [] = {1, 1, 6, 10, 19, 22, 22, 22, 50};
    size_t n = sizeof(A)/sizeof(int);
    std::count << contains(A, n, 19) << std::endl; // should print 0
    std::count << contains(A, n, 22) << std::endl; // should print 1 
    return 0;
}

and, quite honestly, it took me like 10-15 minutes to do it because I have to think through all the pointer arithmetic and corner cases and try to make things compact (and it still isn't compact and probably is incorrect).

Maybe I have poor logical-mathematical ability, but I feel like it takes a lot of brain power just for me to stare at

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred)
{
    while (first!=last) {
         while (pred(*first)) {
             ++first;
         if (first==last) return first;
        }
        do {
             --last;
            if (first==last) return first;
         } while (!pred(*last));
       swap (*first,*last);
      ++first;
    }
    return first;
}

(http://www.cplusplus.com/reference/algorithm/partition/) and visualize how everything is happening.

In any event, I love that sort of stuff because when I go to work everything seems easier by comparison. It's like taking the weight off the bat.

Is all this "code golf" stuff actually worth my time, though? I'm a Junior .NET developer and want to make good money some day. Should I be spending all my free time absorbing more .NET knowledge?

 

[jedishrfu]

It's good to perfect your skills like this but real programming is more than just doing things fast.

Professionals work in a variety of languages and use cookbooks or the Internet to pull up examples of what they need to implement.

Other times we spend a great deal of time thinking about the best design and then working through the details. Sometimes we hit a wall, tear down what we built and try again with a better design eliminating the flaws of the prior design.

 

[Jamin2112]

Alright, critique the stuff I post in this thread.

#include <iostream>

bool contained ( char * str1, char * str2 )
{
// returns true or false depending on whether the string str1 is contained in str2
    if (!*str1) return true;
    while (*str2)
    {
          if (*str1 == *str2)
         {
               char * temp1(str1), * temp2(str2);
               while (*temp2 && (*temp1++ == *temp2++));
               if (!*temp1) return true;
         }
         else
         {
              ++str2;
         }
    }
    return false;
}

int main ()
{
    char sa [] = "abc";
    char sb [] = "rehabc132";
    std::cout << contained(sa, sb); // should print out 1
    return 0;
}

 

[Jamin2112]

Any idea why the following is causing problems?

#include <iostream>

void char_swap ( char * c1, char * c2 )
{
    char temp = *c1;
    *c1 = *c2;
    *c2 = temp;
}

void remove_whitespace ( char * S )
{
// removes whitespace from the string str (rather, moves empty characters to back)
    char * pa(S), * pb(S+strlen(S));
    if (pa == pb) return;
    else --pb;
    while (pa != pb)
   {
        if (*pa == ' ')
       {
            while (*pb == ' ' && pb != pa) --pb;
            if (pa != pb) swap(pa,pb);
        }
      ++pa;
    }
}

int main ()
{
    char myString [] = " a b c de";
    remove_whitespace(myString);
    std::cout << myString; // should print "abcde"
    return 0;
}

 

[Fooality]

Is it a good idea to do "coding drills" in C or C++98 just to make things harder? I've been doing that and it seems to help because there's so much more I need to think about in order to cover all the corner cases and make things compact. It's like practicing baseball with a weighted bat

...
Is all this "code golf" stuff actually worth my time, though? I'm a Junior .NET developer and want to make good money some day. Should I be spending all my free time absorbing more .NET knowledge?

I was just posting something to this effect on another thread.

I think it is worth it to a point. All these higher level languages do pointers and all that implicitly and use garbage collection, so you can get yourself in trouble if you are totally unable to drop down and think in terms of that level. For instance, you could have memory leaks in a high level language representation of a graph, where each node contains a pointer to its neighbor, if you don't delete them correctly (understanding that garbage collector deletes things not pointed to by anything.) But how far you go with it really depends on what you want to do. If you want to work with high performance stuff like real time video, its a must, and most languages I've seen for GPUs are C based. However if your dream is something like web development, it really isn't that important.

 

[Mark44]

Any idea why the following is causing problems?

#include <iostream>

void char_swap ( char * c1, char * c2 )
{
    char temp = *c1;
    *c1 = *c2;
    *c2 = temp;
}

void remove_whitespace ( char * S )
{
// removes whitespace from the string str (rather, moves empty characters to back)
    char * pa(S), * pb(S+strlen(S));
    if (pa == pb) return;
    else --pb;
    while (pa != pb)
   {
        if (*pa == ' ')
       {
            while (*pb == ' ' && pb != pa) --pb;
            if (pa != pb) swap(pa,pb);
        }
      ++pa;
    }
}

int main ()
{
    char myString [] = " a b c de";
    remove_whitespace(myString);
    std::cout << myString; // should print "abcde"
    return 0;
}

This won't even compile. You define a function named char_swap(), but call a function named swap(). After making a correction, I got it to run.

What problems are you having? I know, but if you're asking for help, it's your responsibility to provide details of the problems.

A few minutes with a debugger should help you figure out what's wrong.

 

[Carno Raar]

and, quite honestly, it took me like 10-15 minutes to do it because I have to think through all the pointer arithmetic and corner cases and try to make things compact (and it still isn't compact and probably is incorrect).

How can it be incorrect if it's properly covered by your test suite? (Well, it can be, but that's a separate issue!)

Let's look at the tests

std::cout<< contains(A, n,19)<< std::endl;// should print 0
std::cout<< contains(A, n,22)<< std::endl;// should print 1

Ok, that explains why you don't know if it works or not.

If you had to think though a corner case, write a test for it.

It looks you tried binary search (but hard to tell if your var names are just pa, pb... I'd expect start, end, mid etc). So, the MINIMAL tests I want to see for this are

• found in first position (corner case)
• found in last position (corner case)
• found in middle position (corner case)
• not found
• all of the above for arrays of length 0, length 1 and long even and odd lengths. Length 0 and 1 are corner cases, as are even and odd length arrays (due to how mid point is calculated).
• find some random numbers in random arrays of length 10+ just to make sure it's all ok

Your tests should produce a descriptive message on fail. "Should be 1" is bad. What should be 1? Which one of your tests failed? "Doesn't work if element is 1st item in even length array" is better.

Whether or not you check for stupid input (array not sorted?) is up to you and the domain you're working in. I wouldn't normally for this case, but in fields like embedded it would be borderline illegal to not make at least some check of your inputs.

I think this covers all of your code snippets above. Write proper tests.

Edit: I don't think you need to make things HARDER for yourself. You just need to have a solid foundation in developer working practices, and from there, just read and write code for a few years.

 

[D H]

Is it a good idea to do "coding drills" in C or C++98 just to make things harder?

As a general rule, no.

For instance, I just did

bool contains ( int * sarr, size_t n, int i) // checks whether the integer i is in the sorted array sarr of length n
{

    int * pa(sarr), * pb(sarr + n);
    if (pa == pb) return false;
    --pb;
    while (pa != pb && ((pb - pa) != 1))
    {
        int * pc = pa + (pb - pa)/2;
        if (*pc < i) pa = pc;
        else pb = pc;
    }
    if (*pa == i || *pb == i) return true;
    else return false;
}

Compare with

/**
* Determine if val is in the sorted array sarr of length len
*/
bool contains (const int * sarr, std::size_t len, int val)
{
   std::size_t search_len = len;
   std::size_t first = 0;

   // Find first element in sarr such that sarr[first] >= val ("the predicate").
   // Loop ends with first=len if no elements satisfy the predicate.
   while (search_len > 0) {
      std::size_t half_len = search_len / 2;

      // Exclude elements after midpoint if that element satisfies the predicate.
      if (val <= sarr[first + half_len]) {
         search_len = half_len;
      }
      // Otherwise exclude elements up to and including the midpoint.
      else {
         first += half_len + 1;
         search_len -= half_len + 1;
      }
   }

   return (first < len) && (sarr[first] == val);
}

Rather than focusing your efforts on being tricky, focus your efforts on writing code

• That works as advertised,
• That contains at least some comments, with key comments in a style amenable to automated documentation tools, and
• That you yourself could understand after setting it down for six months.

The first item means testing, and not just for a couple of tests on the "happy path." The happy path is where everything goes as planned. Unhappy path testing is general much harder than happy path testing, but in this case there are some obvious failure cases.

Automatable testing is even better. For example, here's a little test function for contains:

bool test_contains (const int * sarr, std::size_t len, int val, bool expect)
{
   bool is_in = contains (sarr, len, val);
   bool pass = is_in == expect;
   std::cout << "Test " << val << " " << is_in << " " << expect
             << " " << (pass ? "passes" : " fails") << '\n';
   return pass;
}

Note how the expectation is passed to the test driver rather than being embedded in a comment that says // should print 0. So how to use this?

int main () 
{
    int A [] = {1, 1, 6, 10, 19, 22, 22, 22, 50};
    size_t n = sizeof(A)/sizeof(int);
    int fail_count = 0;
    if (! test_contains(A, n,  1, 1)) ++fail_count; 
    if (! test_contains(A, n, 22, 1)) ++fail_count; 
    if (! test_contains(A, n, 50, 1)) ++fail_count; 
    if (! test_contains(A, n,  0, 0)) ++fail_count; 
    if (! test_contains(A, n, 19, 0)) ++fail_count; 
    if (! test_contains(A, n, 51, 0)) ++fail_count; 
    if (fail_count == 0) {
        std::cout << "All tests passed\n";
        return 0;
    } 
    else {
        std::cout << fail_count << " tests failed\n";
        return 1;
    }
}

The return code from main means this can be used as a part of a larger automated test suite. If some tests fail, the report will provide a way to zoom in on those problem cases. The hundreds of tests that pass? They pass. In regression test mode, I want to see a single indicate that says that every single test passed.

The above of course says that one test failed. (Actually, it says "1 tests failed". Some people get pedantic and fix the grammar. I don't bother with that anymore.) The problem is that 19 is in the sorted array. The bug is in the test code rather than in the code to be tested. That happens with great regularity.

Maybe I have poor logical-mathematical ability, but I feel like it takes a lot of brain power just for me to stare at <partition algorithm elided>.

Just because the authors of the C++ library wrote code in a certain way does not mean you should emulate that. Sometimes it means exactly the opposite. For example, the C++ library code contains identifier upon identifier with leading underscores. You should never, ever do that.

The library code is written with constraints that oftentimes do not pertain to typical user code. For example, any library function that uses forward iterators or bidirectional iterators has to be written to avoid random access or pay a potential penalty. Forward iterators can be incremented by one. Bidirectional iterators add decrement, but only by one. Incrementing or decrementing by twenty may require incrementing or decrementing by one twenty times.

The library code is also written a strong eye to performance, which oftentimes doesn't pertain to typical user code. Suppose you have a well-written, easily understood, and easily tested function that could be sped up by a factor of ten by means of tricky programming. There is no reason for the rewrite if that function is currently responsible for 0.5% of the CPU utilization. A 0.45% speedup -- no one's going to notice. People will notice if that dubious rewrite breaks things, or makes future maintenance and upgrades cost a whole lot more. It's a different story if that function is responsible for a substantial fraction of the CPU utilization. That's not the case in most cases.

Performance is an important metric when you aren't meeting your performance goals. Test, and optimize where the tests say you should optimize. Otherwise, focus your attention on everything but performance. Cheaper, better, faster: You can't have all three, and sometimes you can only have one.