with Raku

This is my response to The Weekly Challenge #238.

You are given an array of integers.

Write a script to return the running sum of the given array. The running sum can be calculated as sum[i] = num[0] + num[1] + …. + num[i].

Example 1:

Write a script to return the running sum of the given array. The running sum can be calculated as sum[i] = num[0] + num[1] + …. + num[i].

Example 1:

Input: @int = (1, 2, 3, 4, 5)
Output: (1, 3, 6, 10, 15)

Example 2:
Input: @int = (1, 1, 1, 1, 1)
Output: (1, 2, 3, 4, 5)

Example 3:
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...

You are given an array of positive integers.

Write a script to sort the given array in increasing order with respect to the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element. If any two numbers have the same count of steps, then print the smaller number first.

Example 1:

File: persistent-sort
Write a script to sort the given array in increasing order with respect to the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element. If any two numbers have the same count of steps, then print the smaller number first.

Example 1:

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)

Example 2:
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.