RogerBW's Blog

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.