Shlomi Fish | 6 May 22:16 2005
Picon

[QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.  
        Thanks.

Well, the previous quiz did not seem to be very popular. Even I started 
writing it, and then abandoned. I also reached the conclusion that I'd be 
better off adapting Template Toolkit or whatever for this.

In any case here's a fresh new quiz inspired by a question someone asked on 
the IRC. (Freenode #perl's channel today)

You are given a large number of ranges (A[i],B[i]) where B[i] > A[i] for every 
i, and A[i] and B[i] are real. The ranges are not supplied in any particular 
order. You are then given a sequence of real numbers X[0], X[1], X[2] one by 
one. For each number, you have to determine whether it falls inside at least 
one of the ranges. 

For bonus points, you need to supply the user with a set of the indices of 
matching ranges.

Phrasing it Perlishly:

Write the following functions:

1. my $handle = prepare_ranges_handle($array_ref);

$array_ref is an array ref of array refs each containing two elements, being 
the numbers of the ranges.

It returns $handle, which is a reference used for further querying.
(Continue reading)

Yitzchak Scott-Thoennes | 8 May 20:27 2005

Re: [QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

On Fri, May 06, 2005 at 11:16:36PM +0300, Shlomi Fish wrote:
> Well, the previous quiz did not seem to be very popular. Even I started 
> writing it, and then abandoned. I also reached the conclusion that I'd be 
> better off adapting Template Toolkit or whatever for this.

Maybe it would be good to prepare a sample solution ahead of time, to
filter out the ideas that *sound* interesting, but turn out not to
be...

> You are given a large number of ranges (A[i],B[i]) where B[i] > A[i] for every 
> i, and A[i] and B[i] are real. The ranges are not supplied in any particular 
> order. You are then given a sequence of real numbers X[0], X[1], X[2] one by 
> one. For each number, you have to determine whether it falls inside at least 
> one of the ranges. 

inside exclusively or inclusively?

Shlomi Fish | 8 May 20:56 2005
Picon

Re: [QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

On Sunday 08 May 2005 21:27, Yitzchak Scott-Thoennes wrote:
> On Fri, May 06, 2005 at 11:16:36PM +0300, Shlomi Fish wrote:
> > Well, the previous quiz did not seem to be very popular. Even I started
> > writing it, and then abandoned. I also reached the conclusion that I'd be
> > better off adapting Template Toolkit or whatever for this.
>
> Maybe it would be good to prepare a sample solution ahead of time, to
> filter out the ideas that *sound* interesting, but turn out not to
> be...
>
> > You are given a large number of ranges (A[i],B[i]) where B[i] > A[i] for
> > every i, and A[i] and B[i] are real. The ranges are not supplied in any
> > particular order. You are then given a sequence of real numbers X[0],
> > X[1], X[2] one by one. For each number, you have to determine whether it
> > falls inside at least one of the ranges.
>
> inside exclusively or inclusively?

Inside inclusively. Not that it matters too much. You can assume that all 
numbers supplied are not on the edge of a range.

Regards,

	Shlomi Fish

--

-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif@...
Homepage:        http://www.shlomifish.org/
(Continue reading)

Yitzchak Scott-Thoennes | 16 May 01:55 2005

Re: [QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

On Fri, May 06, 2005 at 11:16:36PM +0300, Shlomi Fish wrote:
> Well, the previous quiz did not seem to be very popular.

Nor this one :)

> $ret is a hash ref that should contain a field 'verdict' that is a boolean 
> specifying if any of the ranges contain $x. It may also contain 'match_set' 
> which points to a reference to a hash whose keys are the indexes of the 
> matching ranges.

I wonder why match_set would be a hash.  Oh well.

The really neat way to solve this would be to return a tied, lazy
verdict and match_set, that only do the work to the extent necessary,
but I opted for a simple solution instead.

I have the feeling that there's another optimization (other than
sorting by one of the endpoints) that doesn't depend on having some
clue about what kind of values are being dealt with, but couldn't
bring it to the top of my mind.

Attachment (qotw20050506.pl): application/x-perl, 851 bytes

Gmane