I’ve been doing the Weekly
Challenges. The
latest
involved list filtering and a perverse sort. (Note that this is
open until tomorrow.)
Task 1: Move Zero
You are given a list of integers, @list
.
Write a script to move all zero, if exists, to the end while
maintaining the relative order of non-zero elements.
Here I borrow an idea from atomic theory: a freshly-minted zero is just
the same thing as a zero that was in the list. So I construct the list
of non-zero values, then push onto the end the right number of zeroes.
Rust:
fn movezero(l: Vec<isize>) -> Vec<isize> {
let t = l.len();
Here are all the non-zeroes.
let mut o: Vec<isize> = l.into_iter().filter(|i| *i != 0).collect();
And here are the zeroes.
o.append(&mut vec![0; t-o.len()]);
o
}
In PostScript I took a different approach: fill an array of the right
length with zeroes, and then copy the non-zero values into the start
of it.
/movezero {
1 dict begin
/i exch def
[ i length { 0 } repeat ]
dup 0 i { 0 ne } filter putinterval
end
} bind def
Task 2: Wiggle Sort
You are given a list of integers, @list
.
Write a script to perform Wiggle Sort on the given list.
Wiggle sort would be such as list[0] < list[1] > list[2] < list[3]....
There can of course be multiple valid answers (e.g. [1, 2, 3]
could
be wigglesorted either as [1, 3, 2]
or as [2, 3, 1]
). So the first
step in testing was to write something to detect a wigglesorted list.
Perl:
sub is_wigglesorted($l) {
foreach my $i (0..scalar @{$l}-2) {
if ($i % 2 == 0) {
if ($l->[$i] >= $l->[$i+1]) {
return 0;
}
} else {
if ($l->[$i] <= $l->[$i+1]) {
return 0;
}
}
}
return 1;
}
Then it's a matter of doing the sort. This is mostly a matter of
taking the sorted list, splitting it in two at the midpoint, then
taking one value from each sublist in alternation. But this is rather
more fiddly if there's an odd number of values - not given in the
example cases but it seemed worth accounting for. Still Perl:
sub wigglesort($l) {
my @s = sort @{$l};
Get length and split point.
my $le = scalar @s;
my $p = int($le / 2);
Do the split.
my @a = @s[0 .. $p - 1];
my @b = @s[$p .. $#s];
my $i = 0;
my @o;
If we have an odd length, take the first value from b
and put it on
the output.
if ($le % 2 == 1) {
push @o,$s[$p];
@b = @s[$p + 1 .. $#s];
$i = 1;
}
Then alternate lists.
foreach my $j ($i .. $#s) {
if ($j % 2 == 0) {
push @o, pop @a;
} else {
push @o, pop @b;
}
}
return \@o;
}
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.