getMaxWordLength().... Ben Bacarisse wins!

D

DFS

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/
 
T

Tim Rentsch

DFS said:
[snip]

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


//==========================================================================
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;
}

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

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 );
}
 
I

Ike Naar

DFS said:
[snip]

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


//==========================================================================
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;
}

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

Did you notice the subtle almost-bug in it?

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?
 
D

DFS

DFS said:
[snip]

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


//==========================================================================
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;
}

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

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 );
}


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?
 
K

Kaz Kylheku

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?

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.
 
D

DFS

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.


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.
 
M

Malcolm McLean

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.
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.
 
J

Jorgen Grahn

On 06/14/2014 07:50 PM, Kaz Kylheku wrote: ....
I can't tell if you're bullshitting, but it sounds good to me.

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

/Jorgen
 
R

Richard Bos

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

IOW, he's bullshitting :p

Richard
 
R

Richard Bos

DFS said:
ha!

I saw something cool written in a few lines of Haskell:

http://projects.haskell.org/diagrams/gallery/FibCalls.html

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
 
K

Keith Thompson

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.

Your certainty would be more plausible if it were accompanied by an
example.
 
M

Malcolm McLean

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.
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.
 
T

Tim Rentsch

Ike Naar said:
DFS said:
[snip]

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


//===============================================================
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;
}

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

Did you notice the subtle almost-bug in it?

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?

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.
 
T

Tim Rentsch

DFS said:
DFS said:
[snip]

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


//===============================================================
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;
}

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

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 );
}


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?

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.
 
B

Ben Bacarisse

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.

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>
 
T

Tim Rentsch

DFS said:
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.

It won't be as hard as you think once you learn how.
 
T

Tim Rentsch

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.

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?
 
B

BartC

Tim Rentsch said:
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.

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.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top