PWC198 - Max Gap

TL;DR

Here we are with TASK #1 from The Weekly Challenge #198. Enjoy!

The challenge

You are given a list of integers, @list.

Write a script to find the total pairs in the sorted list where 2 consecutive elements has the max gap. If the list contains less then 2 elements then return 0.

Example 1

Input:  @list = (2,5,8,1)
Output: 2

Since the sorted list (1,2,5,8) has 2 such pairs (2,5) and (5,8)

Example 2

Input: @list = (3)
Output: 0

The questions

I’d only ask if a gap of 0 can still be considered a… gap and counted accordingly.

The solution

This is one of those occasions in which we can have a simple, clean sweep over the (sorted) data and then return a value, without the need of going back multiple times. The only strike to efficiency here is the sorting part.

The algorithm is: sweep the sorted list and keep track of the “widest” gap so far, as well as a count of how many times we saw it so far. If a new “best” (i.e. wider) gap appears, we reset the counter to 1 and update the widest gap seen so far. At the end of the sweep, we’re left with the widest gap in the lot, as well as with the count of how many times it appeared.

Raku:

#!/usr/bin/env raku
use v6;
sub MAIN (*@args) {
   @args = 2, 5, 8, 1 unless @args;
   put max-gap(@args);
}

sub max-gap (@list) {
   my $widest-gap = -1;
   my $count = 0;
   my @sorted = @list.sort: { $^a <=> $^b };
   for 1 ..^ @sorted -> $i {
      my $gap = @sorted[$i] - @sorted[$i - 1];

      # order of the following tests matters, do not change!
      ++$count                        if $gap == $widest-gap;
      ($count, $widest-gap) = 1, $gap if $gap >  $widest-gap;
   }
   return $count;
}

Perl:

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

say max_gap(@ARGV ? @ARGV : (2, 5, 8, 1));

sub max_gap (@list) {
   @list = sort { $a <=> $b } @list;
   my $widest_gap = -1;
   my $count = 0;
   for my $i (1 .. $#list) {
      my $gap = $list[$i] - $list[$i - 1];

      # order of the following tests matters, do not change!
      ++$count                          if $gap == $widest_gap;
      ($count, $widest_gap) = (1, $gap) if $gap >  $widest_gap;
   }
   return $count;
}

As indicated in the code, I’m been a bit too clever here, relying purely on post-poned checks instead of doing a proper if ... elsif ... else sequence of checks. This works when the checks have the order shown, but would break miserably if we just inverted the two check lines.

This urged me to put the comment, even though this is just some code-then-toss stuff. I guess this is an example of how not to code checks; at least I’m happy that it made me feel uneasy.

That’s all folks, cheers and stay safe!


Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!