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.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.