Peter
Peter Campbell Smith

Mind the gap!

Weekly challenge 198 — 2 January 2023

Week 198: 2 Jan 2023

Task 1

Task — Max gap

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.

Examples


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

Analysis

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 in $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.

Try it 

Try running the script with any input:



example: 1, 3, 6, 9

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2023-02-03
# PWC 198 task 1

use v5.28;
use utf8;
use warnings;

my (@tests, $test, @list, $gap, $max_gap, $j, $count, $explain);
@tests = ([2, 5, 8, 1], [3], [2, 8, 5, 1, 7], [1, 5, 9, 10, 14]);

# loop over tests
for $test (@tests) {
    
    # sort list numerically
    @list = sort {$a <=> $b} @$test;
    
    # intialise
    $count = 0;
    $max_gap = 0;
    $explain = '';
    
    # loop over consecutive pairs
    for $j (0 .. scalar(@list) - 2) {
        $gap = $list[$j + 1] - $list[$j];
        
        # new $max_gap
        if ($gap > $max_gap) {
            $max_gap = $gap;
            $count = 1;
            $explain = qq[($list[$j], $list[$j + 1]) and ];
            
        # additional pair with $max_gap 
        } elsif ($gap == $max_gap) {
            $count ++;
            $explain .= qq[($list[$j], $list[$j + 1]) and ];
            
        # $gap < $max_gap - ignore  
        } else {
            next;
        }
    }
    
    # format and say output
    say qq[\nInput:  (] . join(', ', @$test) . qq[)];
    $explain = '- ' . substr($explain, 0, -5) if $explain;
    say qq[Output: $count $explain];
}

Output


Input:  (2, 5, 8, 1)
Output: 2 - (2, 5) and (5, 8)

Input:  (3)
Output: 0 -

Input:  (2, 8, 5, 1, 7)
Output: 1 - (2, 5)

Input:  (1, 5, 9, 10, 14)
Output: 3 - (1, 5) and (5, 9) and (10, 14)

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain