by Arne Sommer

# Zero Divisibility with Raku

[208] Published 30. October 2022.

This is my response to The Weekly Challenge #188.

## Challenge #188.1: Divisible Pairs

You are given list of integers `@list` of size `\$n` and divisor `\$k`.

Write a script to find out count of pairs in the given list that satisfies the following rules.

```The pair (i, j) is eligible if and only if a) 0 <= i < j < len(list) b) list[i] + list[j] is divisible by k ``` Example 1: ```Input: @list = (4, 5, 1, 6), \$k = 2 Output: 2 ``` Example 2: ```Input: @list = (1, 2, 3, 4), \$k = 2 Output: 2 ``` Example 3: ```Input: @list = (1, 3, 4, 5), \$k = 3 Output: 2 ``` Example 4: ```Input: @list = (5, 1, 2, 3), \$k = 4 Output: 2 ``` Example 5: ```Input: @list = (7, 2, 4, 5), \$k = 4 Output: 1 ```

#### A Couple of Observations

• `\$n` is probably the same as `len(list)`
• The first example does not work out. Rule `a` gives this requirement: `0 <= 1 < j < 4`. This cannot be satisfied, as there is only one value in the list that is less than 4: i.e. 1. So the correct result is zero. (This is also the case for example 4 and 5.)

Let us program it anyway, and see what we get:

File: divisible-pairs ```#! /usr/bin/env raku unit sub MAIN (:v(:\$verbose)); say dip( (4, 5, 1, 6), 2); # [1] say dip( (1, 2, 3, 4), 2); say dip( (1, 3, 4, 5), 3); say dip( (5, 1, 2, 3), 4); say dip( (7, 2, 4, 5), 4); sub dip (@list, \$k) # [2] { my @combinations = @list.combinations(2); # [3] my \$n = @list.elems; # [4] my \$count = 0; say ":I :[{ @list.join(",") }] K:\$k N:\$n" if \$verbose; for @combinations -> @candidate # [5] { my (\$i, \$j) = @candidate; # [6] (\$i, \$j) = (\$j, \$i) if \$i > \$j; # [7] say ":Comb :[\$i,\$j]" if \$verbose; next unless 0 <= \$i < \$j < \$n; # [8] say ":Less :[\$i,\$j] -> { @list[\$i] },{ @list[\$j] }" if \$verbose; next unless (@list[\$i] + @list[\$j]) %% \$k; # [9] \$count++; say ":OK :[{ @candidate.join(",") }] | \$count" if \$verbose; } return \$count; } ```

[1] I have chosen to hard code the examples.

[2] and use a procedure to get the result.

[3] Get all the combinations of two values.

[4] The number of elements in the input list.

[5] Iterate over the combinations (from [3]).

[6] Assign the «i» and «j» values.

[7] `permutations` does not give us the inverse values, but we do not need both - as `i < j` will only be satisfied for one of them (if at all). So we swap the values if they are in the wrong order.

[8] Apply rule «a».

[9] Apply rule «b».

Running it:

```\$ ./divisible-pairs 0 1 0 1 0 ```

This surely is not what the challenge requested, but that was (in my view) wrong.

With verbose mode:

```\$ ./divisible-pairs -v :I :[4,5,1,6] K:2 N:4 :Comb :[4,5] :Comb :[1,4] :Comb :[4,6] :Comb :[1,5] :Comb :[5,6] :Comb :[1,6] 0 :I :[1,2,3,4] K:2 N:4 :Comb :[1,2] :Less :[1,2] -> 2,3 :Comb :[1,3] :Less :[1,3] -> 2,4 :OK :[1,3] | 1 :Comb :[1,4] :Comb :[2,3] :Less :[2,3] -> 3,4 :Comb :[2,4] :Comb :[3,4] 1 :I :[1,3,4,5] K:3 N:4 :Comb :[1,3] :Less :[1,3] -> 3,5 :Comb :[1,4] :Comb :[1,5] :Comb :[3,4] :Comb :[3,5] :Comb :[4,5] 0 :I :[5,1,2,3] K:4 N:4 :Comb :[1,5] :Comb :[2,5] :Comb :[3,5] :Comb :[1,2] :Less :[1,2] -> 1,2 :Comb :[1,3] :Less :[1,3] -> 1,3 :OK :[1,3] | 1 :Comb :[2,3] :Less :[2,3] -> 2,3 1 :I :[7,2,4,5] K:4 N:4 :Comb :[2,7] :Comb :[4,7] :Comb :[5,7] :Comb :[2,4] :Comb :[2,5] :Comb :[4,5] 0 ```

These results look ok.

## Challenge #188.2: Total Zero

You are given two positive integers `\$x` and `\$y`.

Write a script to find out the number of operations needed to make both `ZERO`. Each operation is made up either of the followings:

```x = \$x - \$y if \$x >= \$y or \$y = \$y - \$x if \$y >= \$x (using the original value of \$x) ```

Example 1: ```Input: \$x = 5, \$y = 4 Output: 5 ``` Example 2: ```Input: \$x = 4, \$y = 6 Output: 3 ``` Example 3: ```Input: \$x = 2, \$y = 5 Output: 4 ``` Example 4: ```Input: \$x = 3, \$y = 1 Output: 3 ``` Example 5: ```Input: \$x = 7, \$y = 4 Output: 5 ```

Off we go...

File: total-zero ```#! /usr/bin/env raku unit sub MAIN (:v(:\$verbose)); say total-zero(5, 4); # [1] say total-zero(4, 6); say total-zero(2, 5); say total-zero(3, 1); say total-zero(7, 4); sub total-zero (\$x is copy, \$y is copy) # [2] { my \$count = 0; # [3] while \$x + \$y # [4] { my \$x0 = \$x; # [5] my \$y0 = \$y; # [6] my \$action = 0; # [7] if \$x0 >= \$y0 { \$x -= \$y0; \$action++; } # [8] if \$y0 >= \$x0 { \$y -= \$x0; \$action++; } # [9] \$count++ if \$action; # [10] say ": x:\$x0 y:\$y0 -> x:\$x y:\$y [#:\$action]" if \$verbose; } return \$count; # [11] } ```

[1] I have chosen to hard code the examples.

[2] and use a procedure to get the result.

[3] The number of operations, i.e. the output.

[4] A loop until both variables reach zero. Adding them, gives False in Boolean context (as we have here), when the result is non-zero. Thus the loop goes on.

[5] The original value of \$x, as requested.

[6] Ditto for \$y, even if not actually required.

[7] As we have to count the number of operations, and each operation can consist of 1 or 2 changes (see [8] and [9]).

[8] The first one.

[9] The second one.

[10] We have one change if one or both of the operations above changed the values.

[11] Return the number of operations, so that the main program can print it.

Running it:

```\$ ./total-zero 5 3 4 3 5 ```

Looking good.

Verbose mode shows us what is going on:

```\$ ./total-zero -v : x:5 y:4 -> x:1 y:4 [#:1] : x:1 y:4 -> x:1 y:3 [#:1] : x:1 y:3 -> x:1 y:2 [#:1] : x:1 y:2 -> x:1 y:1 [#:1] : x:1 y:1 -> x:0 y:0 [#:2] 5 : x:4 y:6 -> x:4 y:2 [#:1] : x:4 y:2 -> x:2 y:2 [#:1] : x:2 y:2 -> x:0 y:0 [#:2] 3 : x:2 y:5 -> x:2 y:3 [#:1] : x:2 y:3 -> x:2 y:1 [#:1] : x:2 y:1 -> x:1 y:1 [#:1] : x:1 y:1 -> x:0 y:0 [#:2] 4 : x:3 y:1 -> x:2 y:1 [#:1] : x:2 y:1 -> x:1 y:1 [#:1] : x:1 y:1 -> x:0 y:0 [#:2] 3 : x:7 y:4 -> x:3 y:4 [#:1] : x:3 y:4 -> x:3 y:1 [#:1] : x:3 y:1 -> x:2 y:1 [#:1] : x:2 y:1 -> x:1 y:1 [#:1] : x:1 y:1 -> x:0 y:0 [#:2] 5 ```

We can actually optimise it:

File: total-zero ``` #! /usr/bin/env raku unit sub MAIN (:v(:\$verbose)); say total-zero(5, 4); say total-zero(4, 6); say total-zero(2, 5); say total-zero(3, 1); say total-zero(7, 4); sub total-zero (\$x is copy, \$y is copy) { my \$count = 0; while \$x + \$y { my \$x0 = \$x; my \$y0 = \$y; \$x -= \$y0 if \$x0 >= \$y0; \$y -= \$x0 if \$y0 >= \$x0; \$count++; say ": x:\$x0 y:\$y0 -> x:\$x y:\$y [#:\$count]" if \$verbose; } return \$count; } ```

The `\$action` variable has gone, as we have at least one change per iteration (as follows from the if-clauses; one change is done if one of them is lower than the other (which one depending on which one is lower), and both if they are equal.

The only case where we do not get ant changes is when both values are zero - in which case we have reached the goal, and the loop terminates.

Running it gives the same result, but the #-part of the verbose output has changed somewhat:

``` \$ ./total-zero2 -v : x:5 y:4 -> x:1 y:4 [#:1] : x:1 y:4 -> x:1 y:3 [#:2] : x:1 y:3 -> x:1 y:2 [#:3] : x:1 y:2 -> x:1 y:1 [#:4] : x:1 y:1 -> x:0 y:0 [#:5] 5 : x:4 y:6 -> x:4 y:2 [#:1] : x:4 y:2 -> x:2 y:2 [#:2] : x:2 y:2 -> x:0 y:0 [#:3] 3 : x:2 y:5 -> x:2 y:3 [#:1] : x:2 y:3 -> x:2 y:1 [#:2] : x:2 y:1 -> x:1 y:1 [#:3] : x:1 y:1 -> x:0 y:0 [#:4] 4 : x:3 y:1 -> x:2 y:1 [#:1] : x:2 y:1 -> x:1 y:1 [#:2] : x:1 y:1 -> x:0 y:0 [#:3] 3 : x:7 y:4 -> x:3 y:4 [#:1] : x:3 y:4 -> x:3 y:1 [#:2] : x:3 y:1 -> x:2 y:1 [#:3] : x:2 y:1 -> x:1 y:1 [#:4] : x:1 y:1 -> x:0 y:0 [#:5] 5 ```

And that's it.