This is my response to The Weekly Challenge #188.
@list of size $n and
divisor $k.
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
Input: @list = (4, 5, 1, 6), $k = 2
Output: 2
Input: @list = (1, 2, 3, 4), $k = 2
Output: 2
Input: @list = (1, 3, 4, 5), $k = 3
Output: 2
Input: @list = (5, 1, 2, 3), $k = 4
Output: 2
Input: @list = (7, 2, 4, 5), $k = 4
Output: 1
$n is probably the same as len(list)
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.
$x and $y.
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)
Input: $x = 5, $y = 4
Output: 5
Input: $x = 4, $y = 6
Output: 3
Input: $x = 2, $y = 5
Output: 4
Input: $x = 3, $y = 1
Output: 3
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.