Month: December 2022

Wherein as learn that elide as we will, it’s still not over until it is over. We should never fail to thank Yogi Berra for that pearl of wisdom…

THE WEEKLY CHALLENGE – PERL & RAKU #196 Task 2

---

“Everywhere you go, there’s a soundtrack. You can’t really quite hear it. It’s just a little out of the range of hearing.”

— Linda Ronstadt

---

Range List

Submitted by: Mohammad S Anwar

You are given a sorted unique integer array, @array.

Write a script to find all possible Number Range i.e [x, y] represent range all integers from x and y (both inclusive).

Each subsequence of two or more contiguous integers

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

I had to read over this task description, and study the examples several times, before I finally got the gist of what was being requested here. I don’t know, perhaps I was just being foggy that day. Rephrased, we are given a list of ascending integers, and are asked to isolate out contiguous runs of sequential values that can be represented with ranges, and return just those ranges we find. Sounds good.

Kind of like an aide to skipping over the boring bits, if you will. “And then keep counting up for a while.”

Ranges, for the purposes of discussion, are assumed here to have the most restricted and basic definition: an expression denoting a list of sequential ascending values differing by one at each step. List comprehensions are very cool and all, but that’s not what we’re this is about.

No funny stuff.

Ok, so one immediately useful observation that we can make right off the bat is that ranges, defined this way, cannot overlap or even abut, as this will immediately stimulate a sort of reverse mitosis — the two disconnected ranges will spontaneously merge into one single larger element. So as we look for our ranges, we know they will have distinct boundaries.

And, to be clear, we are tasked to identify these runs and return a shorthand summary of each, a bracketed tuple of two terms, for the lower and upper bounds.

METHOD

So how do we recognize our ranges to isolate them?

The essential pattern to notice here is to find two sequential elements in the input array that increase by 1. So if we walk the list from left to right, then, given a value, if the next element along is one greater we can declare the two are contained within a range, and if the difference between the two is any other number they are not.

What we can do, then, is iterate over the indices of the target array from 0 to the second-to-last. We can also establish a working range, with low and high values initially undefined, to wait until it becomes useful.

Looking at the first index value, if the next index value along is one more we have a range, with a low of the current index and a high of the next. We can then fill in the data for a low and high bound. Moving to the next, if the difference is 1 again, and we have our working range already initialized, we extend this, making the new value the new high. If it is not in the range, however, the current range is closed as-is and kept, stored away or even printed immediately, and with the working range array wiped clean again. From that point we continue as we did at the beginning, seeking out the next range to find.

After evaluating the second-to-last index, our lookahead will have surveyed the complete list. If we still have a working range going, it is complete and so is added to the output, and obviously if that range is still in an undefined waiting state it is left off.

Proceeding this way we can process the whole array in a single pass from left to right.

PERL 5 SOLUTION

The puzzle on how to either initialize a new range of extend the upper bound is an interesting one. It turns out that after examining each state change, if the lookahead reveals the next element is one greater than the current, we always place the lookahead value in the second, upper bound. We only place the current position value in the lower bound if there is not an existing lower bound already, which happens when there is no current range found to extend. If we already have a working range, well, then we just keep the old lower bound as it was.

In the waiting, empty state the size of the the @working array will be 0, as it has no elements. We could use the line

$working[0] = $array[$_] if not @working;

to get the assignment done, as the 0 scalar evaluation of the array, negated, will cause the conditional to trigger.

But instead I’ve chosen to use a defined-OR assignment, as element [0] in the array will be undefined if we have no range yet. I think this is a little cleaner, and I like using that particular method of assignment. If we find the range conditional applies, we have two instructions following for assigning our lower and upper bound values, and then we move on to examining the next index, and with it its next lookahead position. It’s only when this conditional fails that we add the active, working range to an output list if it exists, closing it out and undefining its elements in the process. We create a new reference to hold the range so we can continue to use our existing array when we’re done.

There’s no similar push-if-defined statement to use here, or later where we add a remaining working range at the end, so we’ll use the scalar evaluation instead.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';



my @array = (0,1,2,4,5,6,8,9);
my @working;
my @ranges;

for (0..$#array-1) {
    if ($array[$_+1] - $array[$_] == 1) {
        $working[0] //= $array[$_  ];
        $working[1]   = $array[$_+1];
        next;
    }
    push @ranges, [ @working ] if @working;
    @working = ();
}

push @ranges, [ @working ] if @working;


say q([) . (join ',', $_->@*) . q(]) for @ranges;