RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various sorts of list filtering. (Note that this closes today.)

Task 1: Consecutive Odds

You are given an array of integers.

Write a script to print 1 if there are THREE consecutive odds in the given array otherwise print 0.

For every language except Perl, I turn that to true/false, because why not? The logic is the same across all languages. Raku:

sub consecutiveodds(@a) {

Set up the odds counter.

    my $i = 0;

For each number in the sequence,

    for (@a) -> $v {

if it's odd,

        if ($v % 2 == 1) {

I have one more odd-in-sequence than I did last time.

            $i++;

If I have three odds-in-sequence,

            if ($i >= 3) {

stop here.

                return True;
            }

If it isn't odd,

        } else {

I have no odds-in-sequence.

            $i = 0;
        }
    }

And if I never got to three having run off the end of the list, return the other result.

    return False;
}

Another approach would be to mod2 the whole list, then take three-element windows onto it and check them individually, but I find the above pretty straightforward and reasonably efficient.

Task 2: Widest Valley

Given a profile as a list of altitudes, return the leftmost widest valley. A valley is defined as a subarray of the profile consisting of two parts: the first part is non-increasing and the second part is non-decreasing. Either part can be empty.

The logic is a bit less obvious than some of these problems have been. Here's my Rust version, which falls into three stages.

fn widestvalley(a: Vec<usize>) -> Vec<usize> {

First, look through the list and combine consecutive multiples into (value, count) tuples. (Well, if I were writing only in Rust I'd probably use tuples; here for portability I just have separate vectors av and ac.)

    let mut av = Vec::new();
    let mut ac = Vec::new();
    let mut l = 0;
    for &v in &a {
        if v == l {
            *ac.last_mut().unwrap() += 1;
        } else {
            av.push(v);
            ac.push(1);
            l = v;
        }
    }

Then I go looking for valley starts and ends - i.e. isolated highest points. The first and last distinct values always count as these; so does any value higher than both its neighbours. (Beware of languages that don't have short-circuiting evaluation, such as Lua and PostScript, because the offset indices won't be valid.) The start value of such a point is the index in a of the first such value in its group; the end value is the index of the last. (c is therefore the index into a that we're artificially incrementing.)

    let mut s = Vec::new();
    let mut e = Vec::new();
    let mut c = 0;
    for i in 0..=av.len() - 1 {
        if i == 0
            || i == av.len() - 1
            || (av[i - 1] < av[i] && av[i] > av[i + 1])
        {
            s.push(c);
            e.push(c + ac[i] - 1);
        }
        c += ac[i];
    }

Finally, each valley runs from an s-value to the next e-value (i.e. including the full width of both peaks). Look through each of these, and if it's wider than we've had before, make it the output.

    let mut out = Vec::new();
    for i in 0..=s.len() - 2 {
        if e[i + 1] - s[i] + 1 > out.len() {
            out = a[s[i] ..= e[i+1]].to_vec();
        }
    }
    out
}

Full code on github.