getMaxWordLength().... Ben Bacarisse wins!

Discussion in 'C Programming' started by DFS, Jun 14, 2014.

  1. DFS

    DFS Guest

    My original:
    too much VB-inspired I see

    Barry Schwarz:
    his submission added a for loop to walk the list of delimiters one at a time

    Ben Bacarisse:
    no for loops, no local counter variables, no strlen(), uses pointer
    arithmetic?, uses strcspn() and strspn() C library functions



    //==========================================================================


    int getMaxWordLength_DFS(char *str, char *delim) {
    int i=0,j=0,maxWordLen=0;

    for(i=0;i<=strlen(str);i++) {
    if(str==delim[0] || str==delim[1] || str==delim[2] ||
    str=='\0') {
    if((i-j) > maxWordLen) {
    maxWordLen = (i-j);
    }
    j = i + 1;
    }
    }
    return maxWordLen;
    }


    //==========================================================================



    int getMaxWordLength_BarryS(const char *str, const char *delim) {
    int i=0, i2=0, j=0,maxWordLen=0;

    for(i=0;i<=strlen(str);i++) {
    for (i2 = strlen(delim); i2 >= 0; i2--) {
    if (str == delim[i2]) {
    if((i-j) > maxWordLen) {
    maxWordLen = (i-j);
    }
    j = i + 1;
    }
    }
    }
    return maxWordLen;
    }


    //==========================================================================


    int getMaxWordLength_BenB(const char *str, const char *delim) {
    size_t max = 0;
    while (*str) {
    size_t l = strcspn(str, delim);
    if (l > max) max = l;
    str += l + strspn(str, delim);
    }
    return max;
    }

    //==========================================================================




    Choose your prize, wisely:
    http://www.pinterest.com/pin/96897829457913032/
    http://purescans.com/bng/
     
    DFS, Jun 14, 2014
    #1
    1. Advertisements

  2. DFS

    Tim Rentsch Guest

    Did you notice the subtle almost-bug in it?

    Here is another approach, making use of the strcspn/strspn method -
    call is 'maximum_word_length( words, delimiters, 0 )' -

    int
    maximum_word_length( const char *s, const char *d, int longest ){
    const char *p = s + strcspn( s, d ), *next = p + strspn( p, d );
    return *s == 0 ? longest
    : maximum_word_length( next, d, p-s > longest ? p-s : longest );
    }
     
    Tim Rentsch, Jun 14, 2014
    #2
    1. Advertisements

  3. DFS

    Ike Naar Guest

    Are you hinting at

    str += l + strspn(str, delim);

    which could have been written as

    str += l;
    str += strspn(str, delim);

    so as to avoid scanning the non-delimiter part twice?
     
    Ike Naar, Jun 14, 2014
    #3
  4. DFS

    DFS Guest


    Interesting.

    Between this example and your Fibonacci post (which I'm noodling on), it
    seems you like to use recursive functions. What's the advantage versus
    for/while loops?
     
    DFS, Jun 14, 2014
    #4
  5. DFS

    Kaz Kylheku Guest

    The advantage is that the recursive version doesn't contain any assignment to
    variables. It is a pure evaluation that is close to a mathematical abstraction
    of the problem. Its linear recursive structure is closely related to the
    inductive proof method, which makes it easy to convince yourself that it's
    correct.
     
    Kaz Kylheku, Jun 15, 2014
    #5
  6. DFS

    DFS Guest


    ha!

    I can't tell if you're bullshitting, but it sounds good to me.
    Unfortunately, I think in loops, and it will be hard to break that habit.
     
    DFS, Jun 15, 2014
    #6
  7. That's the snag.
    You can always translate a loop to a recursive call, but then you obscure
    the difference between iteration over a set and recursion into a tree.
     
    Malcolm McLean, Jun 15, 2014
    #7
  8. DFS

    Jorgen Grahn Guest

    No, it's one of the traditional explanations why functional
    programming languages (Haskell, Erlang etc) are a good idea.

    /Jorgen
     
    Jorgen Grahn, Jun 15, 2014
    #8
  9. DFS

    DFS Guest


    Thanks.

    The first few paragraphs here explain it well:
    http://en.wikipedia.org/wiki/Functional_programming
     
    DFS, Jun 15, 2014
    #9
  10. DFS

    Richard Bos Guest

    IOW, he's bullshitting :p

    Richard
     
    Richard Bos, Jun 16, 2014
    #10
  11. DFS

    DFS Guest

    DFS, Jun 16, 2014
    #11
  12. DFS

    Richard Bos Guest

    Yes, and now correlate this with the discussion in the other thread...
    I'm sure it is possible to write a decent Fibonacci function in Haskell,
    but it certainly won't be as natural as the woefully inefficient one.
    And I'm certain that there are functional languages out there where it
    actually _isn't_ possible, and the functionally-natural, massively-
    recursive version is the only one you're allowed.

    Richard
     
    Richard Bos, Jun 16, 2014
    #12
  13. Your certainty would be more plausible if it were accompanied by an
    example.
     
    Keith Thompson, Jun 16, 2014
    #13
  14. You can always cherry-pick cases.

    The question is how the language scales up to real problems which programmers
    are trying to solve, not how elegantly you can write small functions which
    execute well-studied and known algorithms.
     
    Malcolm McLean, Jun 16, 2014
    #14
  15. DFS

    Tim Rentsch Guest

    Right, except it isn't just the non-delimiter portions that
    are scanned twice - both the delimiter portions and the
    non-delimiter portions are scanned twice, once with strspn
    and once with strcspn. (Of course one of those scans will
    always stop on the first character in each case, but it
    still may be called a "scan".) The problem isn't the
    unnecessary scanning but the confusion over which "words"
    are processed - if we were trying to compute an average word
    length, or minimum word length, the way str is updated here
    would produce bad results.
     
    Tim Rentsch, Jun 16, 2014
    #15
  16. DFS

    Tim Rentsch Guest

    I see you've gotten some other answers, but let me add
    my own perspective.

    Often it is the case that a recursive version will be more
    compact than an iterative version. Other things being equal
    (and I certainly don't mean to say they must be), more
    compact means less that needs to be understood.

    Often it is easier to reason about a recursive formulation,
    because there is no changing state that needs to be kept
    track of.

    IME the more control flow a function has, the more likely it is
    to be coded wrongly. Using recursion rather than iteration
    (when possible to do so reasonably) usually reduces the amount
    of control flow, especially if there is only a single 'return'
    statement (as in the example above). Conversely, when there is
    a loop with more complicated control flow, when that can be
    written as a recursive formulation it often simplifies
    complicated iterative flow into less convoluted recursive calls.
    In either case control flow in a recursive formulation is often
    easier to follow than the control flow in a corresponding
    iterative formulation.
     
    Tim Rentsch, Jun 16, 2014
    #16
  17. fib = 1 : 1 : zipWith (+) fib (tail fib)

    Now natural is in the eye of the beholder, and all program notations are
    unnatural to start with, but this says "fib is defined to be a list
    starting 1, 1 with the rest being the pair-wise additions fib and its
    tail (i.e. fib with the initial 1 missing)".

    If you get past the noise (Why is the '+' in parentheses? What in Earth
    is zipWith?) this is about as natural a definition as possible.

    Of course that's not a function, and making it one (f n = fib !! n) is
    not cheap on memory.

    To get this back on topic, you can combine the obvious definition with
    an automatically generated look up table ("memoization") to get a
    reasonable compromise:

    typedef unsigned long long number;

    number mfib(unsigned int n)
    {
    static number memo[92] = { 1, 1 };
    return n >= sizeof memo / sizeof memo[0] ? 0
    : memo[n] ? memo[n]
    : (memo[n] = mfib(n - 1) + mfib(n - 2));
    }

    <snip>
     
    Ben Bacarisse, Jun 16, 2014
    #17
  18. DFS

    Tim Rentsch Guest

    It won't be as hard as you think once you learn how.
     
    Tim Rentsch, Jun 16, 2014
    #18
  19. DFS

    Tim Rentsch Guest

    This last statement (ie, after the "And I'm certain") seems highly
    unlikely. Any language that allows the definition of recursive
    functions admits a fairly simple and efficient means of calculating
    fibonacci numbers using recursion. Did you have some example
    language(s) in mind, or was it meant as a general statement?
     
    Tim Rentsch, Jun 16, 2014
    #19
  20. DFS

    BartC Guest

    The task will usually determine whether a recursive approach makes sense.
    Processing tree structures for example. Usually you can tell, when an
    iterative method becomes unwieldy to write.

    The Fibonacci sequence isn't a good real-life example.

    A simple example which is related (in being numeric) but better (as it is
    genuinely useful) is the following code to calculate the integer power of a
    integer:

    #include <stdint.h>

    uint64_t upower(uint64_t a, int n) {

    if (n<=0)
    return 0; /* use 0 for fractional results */
    else if (n==0)
    return 1;
    else if (n==1)
    return a;
    else if ((n & 1)==0)
    return upower(a*a, n/2);
    else
    return upower(a*a, (n-1)/2)*a;
    }

    An iterative version (which doesn't just do n-1 multiplications) is not
    impossible, but the recursive method is more natural.
     
    BartC, Jun 16, 2014
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.