with Raku

This is my response to The Weekly Challenge #197.

You are given a list of integers,

Write a script to move all zero, if exists, to the end while maintaining the relative order of

Example 1:

File: move-zero
`@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)

#! /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):

File: move-zero-unravel#! /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.

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

You are given a list of integers,

Write a script to perform

Wiggle sort would be such as list[0] < list[1] > list[2] < list[3]….

Example 1:

`@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]….

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)); # [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:

File: wiggle-sort#! /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.