Zero Wiggle with Raku

This is my response to The Weekly Challenge #197.

Challenge #197.1: Move Zero

Input:  @list = (1, 0, 3, 0, 0, 5)
Output: (1, 3, 5, 0, 0, 0)

Input: @list = (1, 6, 4)
Output: (1, 6, 4)

Input: @list = (0, 1, 0, 2, 0
Output: (1, 2, 0, 0, 0)

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*$/);
                                          # [1]
my @non-zero = @list.grep: * != 0;        # [2]
my @zero     = @list.grep: * == 0;        # [3]

my @wiggly   = (@non-zero, @zero).flat;   # [4]

say "(", @wiggly.join(", "), ")";         # [5]

[1] Ensure that we get at elast 1 element (which would be a very short list, but a list nevertheless), and that they are all nonnegative integers.

[2] Get (with grep) the non-zero values,

[3] and the zeroes (also with grep).

See docs.raku.org/routine/grep for more information about grep.

[4] Merge the two list, giving a new list consisting of the two sublists. Then we apply .flat to get one combined list.

See docs.raku.org/routine/flat for more information about flat.

[5] Print the result, on the requested form.

Running it:

$ ./move-zero 1 0 3 0 0 5
(1, 3, 5, 0, 0, 0)

$ ./move-zero 1 6 4
(1, 6, 4)

$ ./move-zero 0 1 0 2 0
(1, 2, 0, 0, 0)

We got the expected result.

But...

The way I did it is not neat.

I applied grep on the input, twice. Raku does not have an operator for splicing arrays, i.e. the reverse of the Z (zip) operator (which is used in second part of this weekly challenge).

But we can write one. Here it is, as a procedure called «uravel» (as «unZ» looks sillier):

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*$/);

sub unravel(@list, $coderef)                           # [2]
{
  my @match;
  my @nomatch;

  for @list -> $elem                                   # [3]
  {
    $coderef($elem)                                    # [4]
      ?? @match.push: $elem.Int;                       # [4a]
      !! @nomatch.push: $elem.Int;                     # [4b]
  }

  return @match, @nomatch;                             # [5]
}

my ($non-zero, $zero) = unravel(@list, { $_ != 0 } );  # [1]

my @wiggly = ($non-zero.List, $zero.List).flat;        # [6]

say "(", @wiggly.join(", "), ")";

[1] Pass the code to execute as the second argument, as a code block. $_ refers to the current value. The result is a list of non-zero values, followed by a list of the non non-zero (or zero) values.

Note the $ sigil on the variables we assign the two arrays to ($non-zero and $zero). If we use @, the first one will gobble up both arrays. We do not want that...

[2] A code block (or reference) is just a normal variable - until we execute the code (in [3a]) by appending a pair of parens. In this case with a parameter.

[3] Iterate over the values.

[4] Execute the code block. If the block returned True we add the value to the match list [4a], and the non-match list otherwise [4b]. Note the Int coercer, to get rid of leading zeroes.

See docs.raku.org/routine/Int for more information about the Int coercer.

[5] Return the two arrays.

[6] Note that flat does not affect arrays, so we must coerce them to lists (with List, before flattening the result).

See docs.raku.org/routine/flat more information about flat.

See docs.raku.org/routine/List for more information about List.

Running it gives the expected output, and the Int coercer did indeed get rid of the leading zeroes:

$ ./move-zero-unravel 1 0 00 000 2 03 4
(1, 2, 3, 4, 0, 0, 0)

$ ./move-zero 1 0 00 000 2 03 4
(1, 2, 03, 4, 0, 00, 000)

If we replace the operator in the code block (in [1]) with ==, the two output lists will swap places. This can be countered by swapping the two arrays in the declaration as well.

You an use any expression whatsoever in the code block, and you do not have to refer to the current value. E.g. { (True, False).pick } can be used to split the input list arbitrarily between the two output lists. Not very useful, probably...

Challenge #197.2: Wiggle Sort

Input: @list = (1,5,1,1,6,4)
Output: (1,6,1,5,1,4)

Input: @list = (1,3,2,2,3,1)
Output: (2,3,1,3,1,2)

Raku can give us the sorted lists:

> say (1,5,1,1,6,4).sort.reverse;  # -> (6 5 4 1 1 1)
> say (1,3,2,2,3,1).sort.reverse;  # -> (3 3 2 2 1 1)

Let us look at the first example:

(1,6,1,5,1,4)
 0 1 2 3 4 5 ## Index

We can see that the values with even indices (i.e. the values 6,5,4) are sorted in decreasing order.

The values with odd indeces are all the same (1,1,1), so we cannot deduce anything about the order from that. But the second example is helpful:

(2,3,1,3,1,2)
 0 1 2 3 4 5 ## Index 

The odd (oddly?) indexed values are: 2,1,1. This is the last part of the original list, after we sorted it.

The pattern can be described with this illustration:

We sort the values, in descending order. Then we split the list in two, and pick values from alternate lists (starting with the one with the lower values; shown in red above)

The two examples have an even number of integers, so let us pretend that this will always be the case. For now.

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 1 && @list.elems %% 2,
               :v(:$verbose));                # [1]

my $half   = @list.elems / 2;                 # [2]
my @sorted = @list.sort.reverse;              # [3]
my @low    = @sorted[$half .. Inf];           # [4]
my @high   = @sorted[^$half];                 # [5]

if $verbose
{
  say ":Sorted: @sorted[]";
  say ":Lower half: @low[]";
  say ":Higher half: @high[]";
}

say "(", (@low Z @high).flat.join(","), ")";  # [6]

[1] Ensure an even number of elements, using the divisibility operator %%.

See docs.raku.org/routine/%% for more information about the Divisibility Operator %%.

[2] Get the number of elements to place in each sublist.

[3] Sort the values, in descending order.

[4] The second half (the lower values).

[5] The first half (the higher values).

[6] Use the infix zip operator Z to merge the two sublists. The result is a list of Pair objects, so we apply flat to get a one dimentional list. Which we then print.

See docs.raku.org/routine/Z for more information about the infix zip operator Z.

Running it:

$ ./wiggle-sort-even 1 5 1 1 6 4
(1,6,1,5,1,4)

$ ./wiggle-sort-even 1 3 2 2 3 1
(2,3,1,3,1,2)

Looking good.

With verbose mode:

$ ./wiggle-sort-even -v 1 5 1 1 6 4
:Sorted: 6 5 4 1 1 1
:Lower half: 1 1 1
:Higher half: 6 5 4
(1,6,1,5,1,4)

$ ./wiggle-sort-even -v 1 3 2 2 3 1
:Sorted: 3 3 2 2 1 1
:Lower half: 2 1 1
:Higher half: 3 3 2
(2,3,1,3,1,2)

Let us remove the «even number of elements» assumption:

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 1, :v(:$verbose));  # [1]

my $half   = Int(@list.elems / 2);                            # [2]
my @sorted = @list.sort.reverse;
my @low    = @sorted[$half .. Inf];
my @high   = @sorted[^$half];

if $verbose
{
  say ":Sorted: @sorted[]";
  say ":Lower half: @low[]";
  say ":Higher half: @high[]";
}

say "(", roundrobin(@low, @high).flat.join(","), ")";         # [3]

[1] The %% 2 part has gone.

[2] If the number of elements is odd, we get a non-integer value. Coerce it to an integer to be safe. (If we do not, we will get the middle value included in both sublists.)

[3] The Z operator will bail out when it reaches the end of one of the lists. The roundrobin procedure will go on - and we use this to get the last element, the odd one out (- albeit with an even index).

See docs.raku.org/routine/roundrobin for more information about roundrobin.

Running it:

$ ./wiggle-sort -v 1 2 3 4 5
:Sorted: 5 4 3 2 1
:Lower half: 3 2 1
:Higher half: 5 4
(3,5,2,4,1)

Note that the «lower half» sublist must get one more element than the «upper half» sublist for this to work (as both the first and last values come from this list). And the program does indeed get this right.

And that's it.