Michael G Schwern <[EMAIL PROTECTED]> writes:
> On Thu, Nov 29, 2001 at 03:17:39PM +0200, Ariel Scolnicov wrote:
> > > Yesterday, I saw an interesting related exercise. Write a program that
> > > reads the lines from a file and outputs the middle line. The kicker is
> > > that you can't use arrays.
>
> I'll interpret that as O(1) memory, O(n) time.
>
> > #!/usr/local/bin/perl -w
> > # Print middle line of file(s)
> > use strict;
> > open F,$ARGV[0] or die;
> > open G,$ARGV[0] or die;
> > my $l;
> > 1 while (defined(<F>) && defined($l=<G>) && defined(<F>));
> > print $l;
>
> That requires reading each line three times.
1.5, I reckon. F goes over the entire file once, and G goes over half
the file.
> Here's one where each
> line only need be read once:
>
> use File::ReadBackwards;
> open F, $ARGV[0] or die;
> tie *G, 'File::ReadBackwards', $ARGV[0] or die;
>
> while(1) {
> $front = <F>;
> last if $front eq $back;
> $back = <G>;
> last if $front eq $back;
> }
> print $front;
Very nice. "Seek and ye shall find"?
[...]
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | [EMAIL PROTECTED]
Compugen Ltd. | +++ THIS SPACE TO LET +++ \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
