This is my response to The Weekly Challenge #306.
@ints.
Input: @ints = (2, 5, 3, 6, 4)
Output: 77
Odd length sub-arrays:
(2) => 2
(5) => 5
(3) => 3
(6) => 6
(4) => 4
(2, 5, 3) => 10
(5, 3, 6) => 14
(3, 6, 4) => 13
(2, 5, 3, 6, 4) => 20
Sum => 2 + 5 + 3 + 6 + 4 + 10 + 14 + 13 + 20 => 77
Input: @ints = (1, 3)
Output: 4
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int && all(@ints) > 0, # [1]
:v(:$verbose));
my $end = @ints.end; # [2]
my $sum = 0; # [3]
for 0 .. $end -> $start # [4]
{
for $start .. $end -> $stop # [5]
{
next unless ($stop - $start) %% 2; # [6]
my @slice = @ints[$start .. $stop]; # [7]
my $total = @slice.sum; # [8]
$sum += $total;
say ": Slice Indices:$start:$stop Values:({ @slice.join(",") }) \
Sum:$total Total:$sum" if $verbose;
}
}
say $sum; # [9]
[1] 1 or more values, all of which must be integers. (Negative values are allowed, though perhaps not sensible.)
[2] Get the index of the last element with end.
See docs.raku.org/routine/end for more information about end.
[3] The sum will be collected here.
[4] Iterate over all the possible start indices for the subarrays,
[5] and the end indices.
[6] Skip even length subarrays (where the length is divisible
- %% - by two).
See docs.raku.org/routine/%% for more information about the Divisibility Operator %%.
[7] Get the sum of the values in the subarray (also called an array slice).
[8] Add the sum to the total.
[9] Print the result.
Running it:
$ ./odd-sum 2 5 3 6 4
77
$ ./odd-sum 1 3
4
Looking good.
With verbose mode:
$ ./odd-sum -v 2 5 3 6 4
: Slice Indices:0:0 Values:(2) Sum:2 Total:2
: Slice Indices:0:2 Values:(2,5,3) Sum:10 Total:12
: Slice Indices:0:4 Values:(2,5,3,6,4) Sum:20 Total:32
: Slice Indices:1:1 Values:(5) Sum:5 Total:37
: Slice Indices:1:3 Values:(5,3,6) Sum:14 Total:51
: Slice Indices:2:2 Values:(3) Sum:3 Total:54
: Slice Indices:2:4 Values:(3,6,4) Sum:13 Total:67
: Slice Indices:3:3 Values:(6) Sum:6 Total:73
: Slice Indices:4:4 Values:(4) Sum:4 Total:77
77
$ ./odd-sum -v 1 3
: Slice Indices:0:0 Values:(1) Sum:1 Total:1
: Slice Indices:1:1 Values:(3) Sum:3 Total:4
4
@ints.
Input: @ints = (3, 8, 5, 2, 9, 2)
Output: 1
Step 1: pick 8 and 9 => (3, 5, 2, 1, 2)
Step 2: pick 3 and 5 => (2, 2, 1, 2)
Step 3: pick 2 and 1 => (1, 2, 2)
Step 4: pick 2 and 1 => (1, 2)
Step 5: pick 1 and 2 => (1)
Input: @ints = (3, 2, 5)
Output: 0
Step 1: pick 3 and 5 => (2, 2)
Step 2: pick 2 and 2 => ()
The «b» rule has the order wrong; it should be x - y,
as I find it natural to populate x before y. The result should be a
positive value, according to the examples, and my order swapping
ensures that.
Example 1 picks the value 8 before 9 in step 1, which will work with the given «b» rule. But in step 3 it picks 2 before 1, i.e. the highest first. On the other hand, this step is obviously wrong; it should have picked the values 2 and 2.
We do not really care about the array order (except perhaps for verbose mode), so I have chosen to sort the array. Then it is very easy to extract the highest value (from the start or end of the array, depending on the sort order).
File: last-element-sort
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int, # [1]
:v(:$verbose));
my @sorted = @ints.sort(-*); # [2]
say ":Sorted: { @sorted.join(",") }" if $verbose;
while @sorted.elems >= 2 # [3]
{
my $y = @sorted.shift; # [4]
my $x = @sorted.shift; # [4a]
if $x == $y # [5]
{
say ":Removed x:$x and y:$y -> ({ @sorted.join(",") })" if $verbose;
}
else # [6]
{
my $replace = $y - $x; # [6a]
@sorted.push: $replace; # [6b]
@sorted .= sort(-*); # [6c]
say ":Replaced x:$x and y:$y with $replace -> ({ @sorted.join(",") })"
if $verbose;
}
}
say @sorted.elems ?? @sorted.head !! 0; # [7]
[1] All the values must be integers. Note that I have chosen to allow
no values this time, and that will give 0 as output.
[2] Sort the values, with the highest first. The -* negates
the values whilst sorting them.
[3] As long as we have two or more values left to parse.
[4] Get the two biggest values. Note that I have swapped the order
of x and y, so that I could adhere to the «b» rule (y - x).
[5] Are they equal? If so do nothing (as we already have removed them from the array; in [4,4a]).
[6] Not equal? Get the replacement value [6a], add that value to (the end of) the array [6b], and sort the array [6c].
[7] Print the first value in the array (with head),
if we have anything left (actually just one value), and zero otherwise
See docs.raku.org/routine/head for more information about head.
Running it:
$ ./last-element-sort 3 8 5 2 9 2
1
$ ./last-element-sort 3 2 5
0
Looking good.
With verbose mode:
$ ./last-element-sort -v 3 8 5 2 9 2
:Sorted: 9,8,5,3,2,2
:Replaced x:8 and y:9 with 1 -> (5,3,2,2,1)
:Replaced x:3 and y:5 with 2 -> (2,2,2,1)
:Removed x:2 and y:2 -> (2,1)
:Replaced x:1 and y:2 with 1 -> (1)
1
$ ./last-element-sort -v 3 2 5
:Sorted: 5,3,2
:Replaced x:3 and y:5 with 2 -> (2,2)
:Removed x:2 and y:2 -> ()
0
Let us redo this, doing it as the challenge prescribes. I.e. without sorting to sorting.
File: last-element
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int,
:v(:$verbose));
while @ints.elems >= 2
{
my @x-index = @ints.max(:k); # [1]
my $x = @ints[@x-index[0]]; # [2]
sink @ints.splice(@x-index[0], 1); # [3]
if @x-index.elems > 1 # [4]
{
my @y-index = @ints.max(:k); # [4a]
sink @ints.splice(@y-index[0], 1); # [4b]
say ":Removed x:$x and y:$x -> ({ @ints.join(",") })" if $verbose;
}
else # [5]
{
my @y-index = @ints.max(:k); # [5a]
my $y = @ints[@y-index[0]]; # [5b]
my $replace = $x - $y; # [5c]
sink @ints.splice(@y-index[0], 1, $replace); # [5d]
say ":Removed x:$x, replaced y:$y with $replace -> ({ @ints.join(",") })"
if $verbose;
}
}
say @ints.elems ?? @ints.head !! 0;
[1] Get the index (the :k option) of the maximum value.
The result is a list of 1 or more indices, depending on how many times
this value occurs.
See docs.raku.org/routine/max for more information about max.
[2] Get the x value, using the first index from the array in [1].
[3]
Remove the x value from the array (with splice),
as this applies to both the «a» and «b» rules. The sink tells Raku
to discard the return value, which is the removed value.
See docs.raku.org/routine/sink for more information about sink.
See docs.raku.org/routine/splice for more information about splice.
[4] Is x and y identical (i.e. we got more than one index in [1]). Get the index again (as it may have shiftet position as a result of the removal of x) [4a]. Then remove the y value [4b]
[5] Not equal? Get the index of the newly highest value [5a] and the value itself [5b]. Calculate the replacement value [5c], and replace y [5d].
Running it:
$ ./last-element 3 8 5 2 9 2
1
$ ./last-element 3 2 5
0
Looking good.
With verbose mode:
$ ./last-element -v 3 8 5 2 9 2
: Removed x:9, replaced y:8 with 1 -> (3,1,5,2,2)
: Removed x:5, replaced y:3 with 2 -> (2,1,2,2)
: Removed x:2 and y:2 -> (1,2)
: Removed x:2, replaced y:1 with 1 -> (1)
1
$ ./last-element -v 3 2 5
: Removed x:5, replaced y:3 with 2 -> (2,2)
: Removed x:2 and y:2 -> ()
0
And that's it.