Re: middle line (was Re: Daily Perl FAQ...)

[ianb]

On 29 Nov 01 at 10:38:47PM, Greg Bacon wrote:
> In message <[EMAIL PROTECTED]>,
> Apparently I'm having trouble with precision thinking. :-(
> 
> Dmitry is understanding me best.  Let me take another crack:
> 
>     You have a finite sequence of unknown length, where each element in
>     the sequence is a string.  Output the middle element of the sequence
>     (for a reasonable definition of middle), traversing the sequence at
>     most once and without storing the elements in an array.
> 
>     Rather than implementing a stream and iterators or thunks, use a
>     file and Perl's readline operator to simulate the sequence.  No
>     seeking, reopening, rewinding, or other sissy-such. :-)

Is the magic word "recursion"?

Here's a golf-free implementation that takes the lower of a middle
pair as the middle. O(n) time and memory, I'm afraid.


Ian



#!/usr/bin/perl -w
use strict;

my $linecount;
thingy();

sub thingy
{
    my $line = <STDIN>;
    my $linenum = ++$linecount;
    thingy() if defined ($line);
    print($line), exit if ($linenum == int($linecount/2));
}