Re: Challenging problem
Nameless wrote:
This is correct, Markus. It was simply a comparison between
the two versions -- no more, no less. How anyone could
interpret it differently is beyond me, but I suppose
anything is possible if one is vindictive enough.
I have no reason to be vindic* ; not AFAIK.
It has maybe escaped both you and Markus, but when two utterances
are put one after another, it is usual for readers to find a connection
between the two.
My apologies for the nonsense regarding choicepoints.
Apologies accepted. This was just terminology and we know both about
other (sic) people who make rather strange claims about Prolog programs
posted on their homepage, mainly because they confuse terminology and
also principles.
Still, I don't understand why you don't apologise for the more
fundamental thing related to complexity. Or do you still cling onto
the "slightly better than O(N^2)" statement/query ?
Your earlier comment about the space requirements of the
O(N) version has some merit. That version reserves memory
according to N's size; it creates N arguments irrespective
of the actual start position and length of N's recurring
period. In many cases this will be grossly excessive. It is
fast, though -- when it works! I imagine that is why
Joachim saw fit to post his alternative solution.
Maybe one should think of Joachim's solution as a first step to
an optimal (in space and time) algorithm. There is not only black
and white, there is also (sometimes) sparkling yellow !
The truth is, though, that it still remains a challenging
problem for sufficiently large Ns. Challenging for those
that like academic problems, that is. For surely, even
efficient and reasonably fast solutions would be of no
practical use.
Why be so negative ? Many initially academic problem solutions are now
governing our daily life.
Thanks again for your positive and friendly input.
You are welcome.
Bart Demoen
.
