by Arne Sommer

# Persistently Running with Raku

[258] Published 12. October 2023.

This is my response to The Weekly Challenge #238.

## Challenge #238.1: Running Sum

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: ```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`:

File: running-sum-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`.

File: running-sum-gather ```#! /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...

## Challenge #238.2: Persistence Sort

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: ```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) ```
File: persistent-sort ```#! /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.