Just another Perl shrine PerlMonks

### Re: Re: Re: Comparing 2-D co-ordinates

by aging acolyte (Pilgrim)
 on Jul 31, 2003 at 15:35 UTC ( #279618=note: print w/replies, xml ) Need Help??

in reply to Re: Re: Comparing 2-D co-ordinates

Chris,

Thanks for helping clarify my problem. I want to find the set of discrete hits that gives me the best coverage (if that make sense?).

In your example above (ah the beauty of acsii graphics) I would like to pick the two shorter examples as combined they give me a higher overall coverage.

I apologise for any confusion that I am causing - I am having a bad day - too hot and sticky in here!

A.A.

Replies are listed 'Best First'.
Re: Re: Re: Re: Comparing 2-D co-ordinates
by BrowserUk (Pope) on Jul 31, 2003 at 16:07 UTC

Not as neat as my first attempt as this requires a sort, but then, maybe this one actually does what you want:)

```#! perl -slw
use strict;

my @data = map{ [ split "','", substr( \$_, 1, -2 ) ] } <DATA>;

my \$mask = ' ' x 10_000;
my \$max = 0;

# Sort the data to put longest ranges first (could be more efficient:)
@data = sort{
\$b->[2] - \$b->[1] <=> \$a->[2] - \$a->[1]
} @data;

for( @data ) {
# Calc range
my \$len = \$_->[2] - \$_->[1] +1;

# Test to see if this range is already covered?
if( substr( \$mask, \$_->[1], \$len ) !~ m[ ] ) {

\$_ = undef; # if so, delete
next;
}

substr( \$mask, \$_->[1], \$len ) = 'x' x \$len;

# Remeber the highest pos.
\$max = \$_->[2] if \$_->[2] > \$max;
}

# Trim the string

# Count coverage
my \$coverage = \$mask =~ tr[x][x];

# Calc. percentage
printf "cover = %.1f%% \n", \$coverage  / length(\$mask) *100;
print 'Using:';

# Display contributing ranges having discarded deleted elements.
print "@\$_" for  grep{ \$_ } @data;

__DATA__
'NM_176827','618','692'
'NM_176827','621','710'
'NM_176827','622','692'
'NM_176827','629','710'

Output

```P:\test>279587-3
cover = 13.0%
Using:
NM_176827 621 710
NM_176827 618 692

I've also got a version that does this using vec instead of substr, which saves 7/8 of the space, but runs much more slowly.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

Re**4: Comparing 2-D co-ordinates
by belg4mit (Prior) on Jul 31, 2003 at 15:47 UTC
You want the to take the smallest number of your original segments which, combined, cover as much of the range as possible, with no overlaps. This sounds like a solved problem. ie; check some algorythm books/websites

--
I'm not belgian but I play one on TV.

Create A New User
Node Status?
node history
Node Type: note [id://279618]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (8)
As of 2017-07-23 20:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (347 votes). Check out past polls.