This is my response to The Weekly Challenge #238.
Input: @int = (1, 2, 3, 4, 5)
Output: (1, 3, 6, 10, 15)
Input: @int = (1, 1, 1, 1, 1)
Output: (1, 2, 3, 4, 5)
Input: @int = (0, -1, 1, 2)
Output: (0, -1, 0, 2)
gather/take is ideal here, but let us start with a
more sequency approach, using map:
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ Int && @int.elems > 0); # [1]
my @running-sum = (^@int.elems).map({ [+] @int[0..$_] } ); # [2]
say '(' ~ @running-sum.join(", ") ~ ')'; # [3]
[1] One or more integers.
[2] Start with the indices (^@int.elems) and convert them
the sum (with [+], but a trailing .sum
would work just as well) of all the values from the start up to (and
including) that index (@int[0..$_]).
[3] Pretty print the result.
The problem with this approach is that we calculate the sum from the start (or left) for each element, thus doing a lot of additions. Instead of just adding the new value to the previous sum...
Running it:
$ ./running-sum-map 1 2 3 4 5
(1, 3, 6, 10, 15)
$ ./running-sum-map 1 1 1 1 1
(1, 2, 3, 4, 5)
$ ./running-sum-map 0 -1 1 2
(0, -1, 0, 2)
Looking good.
A real sequence would be nice. Here is a first try:
File: running-sum-state
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ Int && @int.elems > 0);
my $running-sum := (@int.first, * + @int[1 + state $index++] ... Inf); # [1]
say '(' ~ $running-sum[0 .. @int.end].join(", ") ~ ')'; # [2]
[1]
The first element (@int.first, followed
by the rule * + @int[1 + state $index++] that starts with
the previuos value in the sequence (the *) and adds that to
the next value from the input array, given by an explicit array index.
Note the use of a state variable to keep track of the
index.
See
docs.raku.org/routine/first
for more information about first.
See
docs.raku.org/syntax/state for
more information about the variable declarator state.
[2] The major problem with the sequence is the open end (the
Inf), as it will go on indefinitely. We want it to
end after going thorough the input array, so must add that limit
manually. It does not look good.
Running it gives the expected result:
$ ./running-sum-state 1 2 3 4 5
(1, 3, 6, 10, 15)
$ ./running-sum-state 1 1 1 1 1
(1, 2, 3, 4, 5)
$ ./running-sum-state 0 -1 1 2
(0, -1, 0, 2)
Setting the correct upper limit for the sequence solves this problem.
File: running-sum-seq
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ Int && @int.elems > 0);
my $running-sum := (@int.first, * + @int[1 + state $index++] ... @int.sum ); # [1]
say '(' ~ $running-sum.join(", ") ~ ')';
[1] The sequence will end after it has reached @int.sum, which
indeed is the last value.
Running it gives the expected result, yet again:
$ ./running-sum-seq 1 2 3 4 5
(1, 3, 6, 10, 15)
$ ./running-sum-seq 1 1 1 1 1
(1, 2, 3, 4, 5)
$ ./running-sum-seq 0 -1 1 2
(0, -1, 0, 2)
Note that the last sum is
evaluated twice, by @int.sum to set the limit, and by the
sequence itself.
Let us have a go at gather/take,
for the final take on this...
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ Int && @int.elems > 0);
my $running-sum := gather # [1]
{
my $sum = 0; # [2]
for @int -> $current # [3]
{
$sum += $current; # [3a]
take $sum; # [3b]
}
}
say '(' ~ $running-sum.join(", ") ~ ')';
[1] Set up the sequence with gather.
[2] The sum so far will be held here.
[3] Iterate over each input value; add the current value to the sum [3a],
and return (with take) the new sum [3b].
Running it:
$ ./running-sum-gather 1 2 3 4 5
(1, 3, 6, 10, 15)
$ ./running-sum-gather 1 1 1 1 1
(1, 2, 3, 4, 5)
$ ./running-sum-gather 0 -1 1 2
(0, -1, 0, 2)
Perfect...
Input: @int = (15, 99, 1, 34)
Output: (1, 15, 34, 99)
15 => 1 x 5 => 5 (1 step)
99 => 9 x 9 => 81 => 8 x 1 => 8 (2 steps)
1 => 0 step
34 => 3 x 4 => 12 => 1 x 2 => 2 (2 steps)
Input: @int = (50, 25, 33, 22)
Output: (22, 33, 50, 25)
50 => 5 x 0 => 0 (1 step)
25 => 2 x 5 => 10 => 1 x 0 => 0 (2 steps)
33 => 3 x 3 => 6 (1 step)
22 => 2 x 2 => 4 (1 step)
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ UInt # [1]
&& all(@int) > 0 # [1a]
&& @int.elems > 0, # [1b]
:v(:$verbose));
my %steps; # [2a]
for @int -> $int # [2]
{
%steps{$int} = steps($int); # [2a]
}
say '('
~ @int.sort({ %steps{$^a} <=> %steps{$^b} || $^a <=> $^b }).join(', ') # [3]
~ ')';
sub steps (Int $int is copy) # [4]
{
print ": $int" if $verbose;
my $steps = 0; # [5]
while $int >= 10 # [6]
{
my @digits = $int.comb; # [7]
$int = [*] @digits; # [8]
print " => { @digits.join(' x ') } => $int" if $verbose;
$steps++; # [9]
}
say " ($steps step{ 's' if $steps != 1})" if $verbose;
return $steps; # [10]
}
[1] One or more positive integers.
[2] Calculate the number of steps for each value.
I have chosen to cache the step values instead of using the procedure call in the sort comparison (in [3]), as that would have caused them to be computed «all the time».
[3] Print the sorted result.
[4] The procedure computing the number of steps, with is copy on the
input so that we can change the value (in [8]).
[5] The number of steps so far.
[6] As long as the result has more than one digit.
[7] Get the individual digits.
[8] Multiply the digits together.
[9] One more step.
[10] Return the result.
Running it gives the expected result, here with verbose mode:
$ ./persistent-sort -v 15 99 1 34
: 15 => 1 x 5 => 5 (1 step)
: 99 => 9 x 9 => 81 => 8 x 1 => 8 (2 steps)
: 1 (0 steps)
: 34 => 3 x 4 => 12 => 1 x 2 => 2 (2 steps)
(1, 15, 34, 99)
$ ./persistent-sort -v 50 25 33 22
: 50 => 5 x 0 => 0 (1 step)
: 25 => 2 x 5 => 10 => 1 x 0 => 0 (2 steps)
: 33 => 3 x 3 => 9 (1 step)
: 22 => 2 x 2 => 4 (1 step)
(22, 33, 50, 25)
The examples use one and two digit integers only, but the program handles as many digits as you want:
$ ./persistent-sort -v 115 199 1 1134
: 115 => 1 x 1 x 5 => 5 (1 step)
: 199 => 1 x 9 x 9 => 81 => 8 x 1 => 8 (2 steps)
: 1 (0 steps)
: 1134 => 1 x 1 x 3 x 4 => 12 => 1 x 2 => 2 (2 steps)
(1, 115, 199, 1134)
And that's it.