This is my response to The Weekly Challenge #226.
Input: $string = 'lacelengh', @indices = (3,2,0,5,4,8,6,7,1)
Output: 'challenge'
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
@ints.
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)
Input: @ints = (0)
Output: 0
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.