04 January 2023

Mind the gap!

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