develooper Front page | perl.fwp | Postings from December 2001

middle line, redux

Bernie Cosell
December 2, 2001 05:14
middle line, redux
Message ID:
Would someone take a step back from the Perl intricacies and tell me if 
they even have an *algorithm* [much less a Perl program] that meets the 
problem's criteria.  I as got it:
   1) you can only read the file once, from beginning to end [no 
'seek'ing around or other hackery -- assume the file is a TCP stream or a 
   2) you can only use O(1) storage
   3) you must print out the 'middle' line of the file.

If you were allowed to read the file 1.5 times, there are many [simple!] 
algorithms that would meet *that* criterion, but of course that wouldn't 
work for a 'pipe' or the like [since you cannot 'reread' your pipe data 
unless you explicitly store it someplace, which blows the O(1) storage.

The recursive solutions don't work, of course, because elegant as they 
are, they use O(n) storage.

My intuition is that the problem is too constrained and that there 
*is*no* algorithm that meets all the criteria, but I'd be delighted to be 
proven wrong...


Bernie Cosell                     Fantasy Farm Fibers     Pearisburg, VA
    -->  Too many people, too few sheep  <--     Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About