with Raku

This is my response to The Weekly Challenge #226.

You are given a string and an array of indices of same length as string.

Write a script to return the string after re-arranging the indices in the correct order.

Example 1:

Write a script to return the string after re-arranging the indices in the correct order.

Example 1:

Input: $string = 'lacelengh', @indices = (3,2,0,5,4,8,6,7,1)
Output: 'challenge'

Example 2:
Input: $string = 'rulepark', @indices = (4,7,3,1,0,5,2,6)
Output: 'perlraku'

This surely is a task for an array slice?

Let us have a go, and find out...

File: shuffle-string-slice#! /usr/bin/env raku
unit sub MAIN ($string where $string.chars > 0, # [1]
*@indices where @indices.elems == $string.chars); # [2]
my @string = $string.comb; # [3]
say @string[@indices].join; # [4]

[1] A string, with at least 1 character.

[2] A slurpy array with the same number of elements as characters in [1].

Note the missing check for non-negative integers, and that the indices cover all the positions (without duplicates and holes).

[3] Get the string as an array of individual characters.

[4] Get the characters in the correct order, with an array slice, and join that array to form a string that we print.

Running it:

$ ./shuffle-string-slice lacelengh 3 2 0 5 4 8 6 7 1
eclelhnga

Oops.

We have actually translated the indices the wrong way round. That is fixable, with a little more code.

And let us add the missing error checking this time.

File: shuffle-string#! /usr/bin/env raku
unit sub MAIN ($string where $string.chars > 0, # [1]
*@indices
where @indices.elems == @indices.unique.elems == $string.chars # [2]
&& all(@indices) ~~ UInt # [3]
&& all(@indices) < $string.chars); # [4]
my @string = $string.comb; # [5]
my @out; # [6]
for ^@string.elems -> $i # [7]
{
@out[@indices[$i]] = @string[$i] # [8]
}
say @out.join; # [9]

[1] As before.

[2] Note the added check for the same length after removing
duplicate indices with `unique`

.

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

.

[3] Ensure that the indices are non-negative with the
`Uint`

(Unsigned Int) type.

See
docs.raku.org/type/UInt for
more information about the `Uint`

type.

[4] Check that all the values are within the upper index limit. This and [2] and [3] ensures that we have all the indices we should have.

[5] As before.

[6] The unshuffled characters will end up here.

[7] Iterate over the indices.

[8] Copy the character from the input array, with the index found at the current position.

[9] Print the result, as a string.

Running it gives the expected result:

$ ./shuffle-string lacelengh 3 2 0 5 4 8 6 7 1
challenge
$ ./shuffle-string rulepark 4 7 3 1 0 5 2 6
perlraku

You are given an array of non-negative integers,

Write a script to return the minimum number of operations to make every element equal zero.

In each operation, you are required to pick a positive number less than or equal to the smallest element in the array, then subtract that from each positive element in the array.

Example 1:

File: zero-array
`@ints`

.
Write a script to return the minimum number of operations to make every element equal zero.

In each operation, you are required to pick a positive number less than or equal to the smallest element in the array, then subtract that from each positive element in the array.

Example 1:

Input: @ints = (1, 5, 0, 3, 5)
Output: 3
operation 1: pick 1 => (0, 4, 0, 2, 4)
operation 2: pick 2 => (0, 2, 0, 0, 2)
operation 3: pick 2 => (0, 0, 0, 0, 0)

Example 2:
Input: @ints = (0)
Output: 0

Example 3:
Input: @ints = (2, 1, 4, 0, 3)
Output: 4
operation 1: pick 1 => (1, 0, 3, 0, 2)
operation 2: pick 1 => (0, 0, 2, 0, 1)
operation 3: pick 1 => (0, 0, 1, 0, 0)
operation 4: pick 1 => (0, 0, 0, 0, 0)

#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ UInt, # [1]
:v(:$verbose));
my $operations = 0; # [2]
while @ints.sum > 0 # [3]
{
$operations++; # [4]
my $smallest = @ints.grep( * > 0).min; # [5]
my @new = @ints.map({ $_ > 0 ?? $_ - $smallest !! 0 }); # [6]
say ":Ints @ints[] -> smallest: $smallest -> @new[]" if $verbose;
@ints = @new; # [7]
}
say $operations; # [8]

[1] Ensure that all the values (if any, as none is ok) are of the
`UInt`

(Unsigned Int) type.

[2] The number of operations will end up here.

[3] As long as we have non-zero values in the array, using
`sum`

to add them all up.

[4] One operation.

[5] Find the smallest number (with `min`

), which is not
zero (with `grep`

).

[6] Subtract the smalelst number (from [5]) from each non-zero value.

[7] Copy the new array over the old one. (This extra step is used by verbose mode.)

[8] Print the number of steps.

Running it:

$ ./zero-array 1 5 0 3 5
3
$ ./zero-array 1
1
$ ./zero-array 2 1 4 0 3
4

Looking good.

With verbose mode:

$ ./zero-array -v 1 5 0 3 5
:Ints 1 5 0 3 5 -> smallest: 1 -> 0 4 0 2 4
:Ints 0 4 0 2 4 -> smallest: 2 -> 0 2 0 0 2
:Ints 0 2 0 0 2 -> smallest: 2 -> 0 0 0 0 0
3
$ ./zero-array -v 1
:Ints 1 -> smallest: 1 -> 0
1
$ ./zero-array -v 2 1 4 0 3
:Ints 2 1 4 0 3 -> smallest: 1 -> 1 0 3 0 2
:Ints 1 0 3 0 2 -> smallest: 1 -> 0 0 2 0 1
:Ints 0 0 2 0 1 -> smallest: 1 -> 0 0 1 0 0
:Ints 0 0 1 0 0 -> smallest: 1 -> 0 0 0 0 0
4

But...

All that special code to handle zeroes surely can be removed, if we remove the zeroes themselves? Let us find out...

File: zero-array-sans-zero#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ UInt,
:v(:$verbose));
my $operations = 0;
@ints = @ints.grep( * > 0 ); # [1]
while @ints.elems > 0 # [2]
{
my $smallest = @ints.min; # [3]
my @new = @ints.map({ $_ - $smallest }); # [3a]
say ":Ints @ints[] - smallest: $smallest -> @new[]" if $verbose;
$operations++;
@ints = @new.grep( * > 0 ); # [1a]
}
say $operations;

[1] We have to get rid of the zeroes twice, initially - and in the loop. This is not neat, but the simplifications of [3] and [3a] may be worth it.

[2] This is a quicker test than the first one (using `sum`

).

[3] Simpler code than before, as the zeroes have been removed before we come here.

Running it gives the expected result:

$ ./zero-array-sans-zero 1 5 0 3 5
3
$ ./zero-array-sans-zero 0
0
$ ./zero-array-sans-zero 2 1 4 0 3
4

You may have noticed that I have ignored the «pick a positive number less than or equal to the smallest element in the array» part, and gone for «equal to». This seems right at first glance, and actually pass muster. (As the number of operations required is the number of unique non-zero values in the input.)

This insight leads to the realisation that the program is highly overengineered:

File: zero-array-short#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ UInt);
say @ints.grep( * > 0).unique.elems; # [1]

[1] get rid of zeroes (if any) and duplicates (if any), and count the result (i.e. unique non-zero values).

Running it gives the correct result:

$ ./zero-array-short 1 5 0 3 5
3
$ ./zero-array-short 0
0
$ ./zero-array-short 2 1 4 0 3
4

And that's it.