RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved looking for patterns in arrays. (Note that this closes today. Merry Christmas!)

Task 1: Pattern 132

You are given a list of integers, @list.

Write a script to find out subsequence that respect Pattern 132. Return empty array if none found.

Pattern 132 is a sequence (a[i], a[j], a[k]) such that i < j < k and a[i] < a[k] < a[j].

The obvious answer here is nested loops and I see no reason not to be obvious. Some languages don't like breaking out of loops, but Raku isn't one of them.

sub pattern132(@l) {
    my @o = [];
    OLOOP:
    for (0..@l.elems-3) -> $a {
        for ($a+1..@l.elems-2) -> $b {
            if (@l[$a] < @l[$b]) {
                for ($b+1..@l.elems-1) -> $c {
                    if (@l[$b] > @l[$c] && @l[$a] < @l[$c]) {
                        @o = [@l[$a], @l[$b], @l[$c]];
                        last OLOOP;
                    }
                }
            }
        }
    }
    return @o;
}

Task 2: Range List

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)

The most fiddly bit here was skipping one entry in a list, and that's not even technically necessary. Rust:

fn rangelist(l: Vec<isize>) -> Vec<Vec<isize>> {
    let mut o = Vec::new();
    let mut start = l[0];
    let mut prev = start;

For each entry in the list except the first:

    for &v in l.iter().skip(1) {

If current isn't one more than previous, the previous one might have been an end of sequence.

        if v != prev + 1 {

Was prev (set for every entry) greater than start (set only for new sequences)? Then it was an end of sequence; note it.

            if prev > start {
                o.push(vec![start, prev]);
            }

Whether it was nor not, set start to current as it might be the beginning of a new sequence.

            start = v;
        }

Whether or not we did any of that, set prev ready for the next pass round the loop.

        prev = v;
    }

And at the end, log any sequence that was still ongoing. (Perhaps it would be cleaner to push a dummy value on the end of the list.)

    if prev > start {
        o.push(vec![start, prev]);
    }
    o
}

Full code on github.