Front page | perl.fwp |
Postings from December 2001
middle line, redux
From:
Bernie Cosell
Date:
December 2, 2001 05:14
Subject:
middle line, redux
Message ID:
200112021314.fB2DEFD15265@mail.rev.net
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
pipe]
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\
--
Bernie Cosell Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com Pearisburg, VA
--> Too many people, too few sheep <--
-
middle line, redux
by Bernie Cosell