Peter
Peter Campbell Smith

132 and 123

Weekly challenge 196 — 19 December 2022

Week 196: 19 Dec 2022

Task 2

Task — Range list

You are given a sorted unique integer array, @array. Write a script to find the start and end of all subsequences of consecutive numbers within the list.

Examples


Example 1
Input: @array = (1,3,4,5,7)
Output: [3,5]

Example 2
Input: @array = (1,2,3,6,7,9)
Output: [1,3], [6,7]

Example 3
Input: @array = (0,1,2,4,5,6,8,9)
Output: [0,2], [4,6], [8,9]

Analysis

Let's iterate through @array and have two persistent variables: $start, the value at the start of a consecutive subsequence and a state boolean variable $in_slice which indicates whether we are in a consecutive subsequence or not - initialised to false.

So if $j is the index:

  • if not $in_slice, see if $array[$j + 1] == $array[$j] + 1, and if so set $start = $j and set $in_slice to true
  • else if $in_slice, see if $array[$j] + 1 == $array[$j] + 1, and if not, record the end of a slice and set $in_slice to false

This works fine, except that at the very last array element, $array[$j + 1] won't exist. Obviously we could check for this, but I avoided the issue by adding an element at the end of array equal to the supplied last one + 2, and iterating $j only up to the second last element. This is a bit messy and I'm looking forward to someone having a more elegant solution.

Try it 

Try running the script with any input:



example: 1, 3, 5, 6, 7, 9

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-12-19
# PWC 196 task 2

use v5.28;
use utf8;
use warnings;

my (@tests, $test, @array, $start, $in_slice, $output, $j);

# Mohammad's examples
@tests = ([1,3,4,5,7], [1,2,3,6,7,9], [0,1,2,4,5,6,8,9], [1,3,5,7,9,11]);

# loop over tests
TEST: for $test (@tests) {
    @array = @$test;
    
    # initialise
    $in_slice = 0;
    $output = '';
    say qq[\nInput:  \@array = (] . join(', ', @array) . ')';

    # add a number at the end of @array which is 2 more than the last one
    push @array, $array[scalar @array - 1] + 2;
    
    # loop over elements in @array
    for ($j = 0; $j < (scalar @array) - 1; $j ++) {
        
        # if we're not already in a sequence and the next element is one more than this, start a sequence
        unless ($in_slice) {
            if ($array[$j] == $array[$j + 1] - 1) {
                $start = $array[$j];
                $in_slice = 1;
            }
        
        # if we are already in a sequence, end it if the following element isn't one more than this
        } else {
            if ($array[$j] != $array[$j + 1] - 1) {
                $output .= qq[[$start, $array[$j]], ];
                $in_slice = 0;
            }
        }
    }
    if ($output) {
        say qq[Output: ]. substr($output, 0, -2);
    } else {
        say qq[Output: no consecutive sequence found];
    }
}

Output


Input:  @array = (1, 3, 4, 5, 7)
Output: [3, 5]

Input:  @array = (1, 2, 3, 6, 7, 9)
Output: [1, 3], [6, 7]

Input:  @array = (0, 1, 2, 4, 5, 6, 8, 9)
Output: [0, 2], [4, 6], [8, 9]

Input:  @array = (1, 3, 5, 7, 9, 11)
Output: no consecutive sequence found

 

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