Find the gap
Our first task this week is to take a list of integers, sort it, and find all occurrences of the maximum gap between successive members of the list.
So let's start by sorting the list. You might - ok, some people might - think that this would work:
@list = sort @list;
but that's a trap we all fall into, because Perl treats the list items as text and therefore sorts 8, 9, 10 alphabetically as 10, 8, 9. So what we need is
@list = sort {$a <=> $b} @list;
which is a rather strange syntax that doesn't (I think) happen anywhere else in Perl.
Having done that we just need to loop over all the consecutive pairs of list members like this:
for $j (0 .. scalar(@list) - 2) {
$gap = $list[$j + 1] - $list[$j];
If $gap is larger than any we've seen already, then we make a note of it ($max_gap) and set the count to 1, or if it's equal to $max_gap we increment the count. And that's it done.
Lesser primes
We are asked to find the number of primes less than a supplied number.
Many previous weeks' tasks have involved primes, so I had an implementation of the Sieve of Eratosthenes to hand. It's then just a case of counting them.
@sieve = make_sieve($test - 1);
$output = 0;
for $j (2 .. $test - 1) { # ignore 1 and $test
$output ++ if $sieve[$j];
}
Even with $test equal to a million, this only takes a couple of seconds to run.
No comments:
Post a Comment