headers
Shlomi Fish | 6 May 2005 22:16
Picon
Gravatar

[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)

Permalink | Reply | 3 comments |
headers
Yitzchak Scott-Thoennes | 8 May 2005 20:27
Favicon
Gravatar

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?
Permalink | Reply | 1 comment |
headers
Shlomi Fish | 8 May 2005 20:56
Picon
Gravatar

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)

Permalink | Reply | 0 comments |
headers
Yitzchak Scott-Thoennes | 16 May 2005 01:55
Favicon
Gravatar

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, 755 bytes
Permalink | Reply | 0 comments |

Gmane