Robbie Hatley's Perl Solutions to The Weekly Challenge #198

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle, usually with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

This week (2023-01-01 through 2023-01-07) is weekly challenge #198.

For a change, part 1 was the more thought-provoking of the two puzzles this week: "Given a list of integers, write a script to find the total pairs of consecutive elements of the sorted list which have max gap. If the list contains less then 2 elements then return 0."

Clearly the first step is to make a sorted version of the list; but how to proceed from there? I considered using a hash of gaps then using some funky key sorting; but then it occurred to me that no such thing was necessary, and that I only needed two scalar variables: one to record "max gap seen so far" and one to record "count of pairs with that gap". This works because each time a new "max gap" is found the old count becomes irrelevant and the count variable can be reset to 1. Like so:

for (@arrays){
   my @array  = @{$_};
   my @sorted = sort {$a<=>$b} @array;
   my $gap = 0; # Gap.
   my $max = 0; # Max gap.
   my $cnt = 0; # Count of pairs with max gap.
   for ( my $i = 0 ; $i < $#sorted ; ++$i ) {
      $gap = $sorted[$i+1]-$sorted[$i];
      if    ( $gap  < $max ) {;}                 # Do nothing.
      elsif ( $gap == $max ) {++$cnt;}           # Increment count.
      elsif ( $gap  > $max ) {$max=$gap;$cnt=1;} # New max, new count.
      else {die "Cthulhu wgah'nagl fhtagn.\n";}} # This can't happen.
   say '';
   say "array   = @array";
   say "max gap = $gap";
   say "count   = $cnt";}

(Note: That "else" clause can never execute. But if it does, it will print something suitably ominous.)

(Note: I've recently gone over to using Python-style Perl formatting: no braces on left side; braces appear at right ends of lines only. I think this gives Perl code a fresh, easier-to-read look. The only downsides I've found are occasional brace mismatch errors, and this method doesn't play well with right-line-end comments. But other than that, it works fine.)

Part 2 of this week's challenge is actually simpler for a change: "Given an integer $n, write a script to print the count of primes less than $n."

While there are mathematical ways of estimating that count without having to actually generate or look-up any primes, such methods are not entirely accurate. That leaves the two brute-force options: generate primes, or import a lookup table. I elected to simply generate primes. To speed things up, I use only odd candidates (because all positive even integers except for 2 are composite) and only odd divisors (because if an integer is divisibe by a composite, it's also divisible by that composite's prime factors, all of which are odd except for 2, which we already know can't be a factor of an odd number). Like so:

for (@array){
   say '';                                  # Print blank line,
   my $n = $_;                              # Number.
   say "number = $n";                       # Announce number.
   my $c = 0;                               # Count.
   if ( $n >= 3 ){                          # If number is 3-or-more,
      $c = 1;                               # then increment counter,
      say "2 is prime"}                     # because 2 is a prime number < $n.
   for ( my $x = 3 ; $x < $n ; $x+=2 ){     # Other than 2, consider only odds.
      my $l = int $x**0.5;                  # Limit for divisor.
      my $f = 0;                            # Divisibility flag.
      for ( my $d = 3 ; $d <= $l ; $d+=2 ){ # For each odd divisor, 3 to limit,
         if ( 0 == $x%$d){                  # if number is divisible by divisor,
            $f = 1;                         # number is not prime, so there is
            next;}}                         # no need to try any more divisors.
      if ( !$f ){                           # If number has no divisors,
         ++$c;                              # increment prime count
         say "$x is prime"}}                # and print prime.
   say "There are $c primes less than $n";} # Announce count.

(Using same Pythonesque no-braces-on-left formatting.)

That's it for 198; looking forward to 199 this coming Sunday.

-- 
Cheers,
Robbie Hatley