by Arne Sommer

# Zero Wiggle with Raku

 Published 31. December 2022.

This is my response to The Weekly Challenge #197.

## Challenge #197.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.

Example 1: ```Input: @list = (1, 0, 3, 0, 0, 5) Output: (1, 3, 5, 0, 0, 0) ``` Example 2: ```Input: @list = (1, 6, 4) Output: (1, 6, 4) ``` Example 3: ```Input: @list = (0, 1, 0, 2, 0 Output: (1, 2, 0, 0, 0) ```
File: move-zero ```#! /usr/bin/env raku unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*\$/); #  my @non-zero = @list.grep: * != 0; #  my @zero = @list.grep: * == 0; #  my @wiggly = (@non-zero, @zero).flat; #  say "(", @wiggly.join(", "), ")"; #  ```

 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.

 Get (with `grep`) the non-zero values,

 and the zeroes (also with `grep`).

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

 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`.

 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):

File: move-zero-unravel ```#! /usr/bin/env raku unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*\$/); sub unravel(@list, \$coderef) #  { my @match; my @nomatch; for @list -> \$elem #  { \$coderef(\$elem) #  ?? @match.push: \$elem.Int; # [4a] !! @nomatch.push: \$elem.Int; # [4b] } return @match, @nomatch; #  } my (\$non-zero, \$zero) = unravel(@list, { \$_ != 0 } ); #  my @wiggly = (\$non-zero.List, \$zero.List).flat; #  say "(", @wiggly.join(", "), ")"; ```

 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...

 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.

 Iterate over the values.

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

 Return the two arrays.

 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 ) 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

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 < list > list < list….

Example 1: ```Input: @list = (1,5,1,1,6,4) Output: (1,6,1,5,1,4) ``` Example 2: ```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.

File: wiggle-sort-even ```#! /usr/bin/env raku unit sub MAIN (*@list where @list.elems > 1 && @list.elems %% 2, :v(:\$verbose)); #  my \$half = @list.elems / 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 "(", (@low Z @high).flat.join(","), ")"; #  ```

 Ensure an even number of elements, using the divisibility operator `%%`.

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

 Get the number of elements to place in each sublist.

 Sort the values, in descending order.

 The second half (the lower values).

 The first half (the higher values).

 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:

File: wiggle-sort ```#! /usr/bin/env raku unit sub MAIN (*@list where @list.elems > 1, :v(:\$verbose)); #  my \$half = Int(@list.elems / 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(","), ")"; #  ```

 The `%% 2` part has gone.

 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.)

 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.