This is my response to The Weekly Challenge #241.
Arithmetic Triplets
satisfying the following rules:
a) i < j < k
b) nums[j] - nums[i] == diff
c) nums[k] - nums[j] == diff
Input: @nums = (0, 1, 4, 6, 7, 10)
$diff = 3
Output: 2
Index (1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3
and 4 - 1 == 3.
Index (2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3
and 7 - 4 == 3.
Input: @nums = (4, 5, 6, 7, 8, 9)
$diff = 2
Output: 2
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2
and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2
and 7 - 5 == 2.
#! /usr/bin/env raku
unit sub MAIN ($diff where $diff ~~ UInt && $diff > 0, # [1]
*@nums where @nums.elems > 2 # [2]
&& all(@nums) ~~ Int # [2a]
&& ( [<] @nums ), # [2b]
:v(:$verbose));
my $end = @nums.end; # [3]
my $triplets = 0; # [4]
for 0 .. $end -2 -> $i # [5]
{
for $i+1 .. $end -1 -> $j # [5a]
{
for $j+1 .. $end -> $k # [5b]
{
if $diff == @nums[$j] - @nums[$i] == @nums[$k] - @nums[$j] # [6]
{
$triplets++; # [7]
say ":Indices: $i,$j,$k -> values: @nums[$i],@nums[$j],@nums[$k] \
[triplet]" if $verbose;
}
elsif $verbose
{
say ":Indices: $i,$j,$k -> values: @nums[$i],@nums[$j],@nums[$k]";
}
}
}
}
say $triplets; # [8]
[1] The difference, as a positive intger. Note the use of
the UInt (Unsigned Int) type, instead of the more permissive
Int. In this case it does not really matter which one we use (as
long it enforces integers), as the where clause handles the
restriction.
See
docs.raku.org/type/UInt for
more information about the Uint type.
[2] An array with three or more
elements, all of which are integers [2a], and they come in increasing
order [2b] courtesy of the. Reduction Metaoperator [] in
combination with < (the less than operator.)
See
docs.raku.org/language/operators#Reduction_metaoperators for more
information about the Reduction Metaoperator [].
[3] The index of the last element in the array. Note that
.end is a shortcut for .elems -1.
See
docs.raku.org/routine/end
for more information about end.
[4] The number of found triplets will end up here.
[5] Iterate over all the possible i, j and k indices,
satisfying the «a» rule: i < j < k.
[6] Do the triplet satisfy the «b» and «c» rules?
[7] If so, increase the triplet count.
[8] Print the result.
Running it:
$ ./arithmetic-triplets 3 0 1 4 6 7 10
2
$ ./arithmetic-triplets 2 4 5 6 7 8 9
2
Looking good.
With verbose mode:
$ ./arithmetic-triplets -v 3 0 1 4 6 7 10
:Indices: 0,1,2 -> values: 0,1,4
:Indices: 0,1,3 -> values: 0,1,6
:Indices: 0,1,4 -> values: 0,1,7
:Indices: 0,1,5 -> values: 0,1,10
:Indices: 0,2,3 -> values: 0,4,6
:Indices: 0,2,4 -> values: 0,4,7
:Indices: 0,2,5 -> values: 0,4,10
:Indices: 0,3,4 -> values: 0,6,7
:Indices: 0,3,5 -> values: 0,6,10
:Indices: 0,4,5 -> values: 0,7,10
:Indices: 1,2,3 -> values: 1,4,6
:Indices: 1,2,4 -> values: 1,4,7 [triplet]
:Indices: 1,2,5 -> values: 1,4,10
:Indices: 1,3,4 -> values: 1,6,7
:Indices: 1,3,5 -> values: 1,6,10
:Indices: 1,4,5 -> values: 1,7,10
:Indices: 2,3,4 -> values: 4,6,7
:Indices: 2,3,5 -> values: 4,6,10
:Indices: 2,4,5 -> values: 4,7,10 [triplet]
:Indices: 3,4,5 -> values: 6,7,10
2
$ ./arithmetic-triplets -v 2 4 5 6 7 8 9
:Indices: 0,1,2 -> values: 4,5,6
:Indices: 0,1,3 -> values: 4,5,7
:Indices: 0,1,4 -> values: 4,5,8
:Indices: 0,1,5 -> values: 4,5,9
:Indices: 0,2,3 -> values: 4,6,7
:Indices: 0,2,4 -> values: 4,6,8 [triplet]
:Indices: 0,2,5 -> values: 4,6,9
:Indices: 0,3,4 -> values: 4,7,8
:Indices: 0,3,5 -> values: 4,7,9
:Indices: 0,4,5 -> values: 4,8,9
:Indices: 1,2,3 -> values: 5,6,7
:Indices: 1,2,4 -> values: 5,6,8
:Indices: 1,2,5 -> values: 5,6,9
:Indices: 1,3,4 -> values: 5,7,8
:Indices: 1,3,5 -> values: 5,7,9 [triplet]
:Indices: 1,4,5 -> values: 5,8,9
:Indices: 2,3,4 -> values: 6,7,8
:Indices: 2,3,5 -> values: 6,7,9
:Indices: 2,4,5 -> values: 6,8,9
:Indices: 3,4,5 -> values: 7,8,9
2
Input: @int = (11, 8, 27, 4)
Output: (11, 4, 8, 27))
Prime factors of 11 => 11
Prime factors of 4 => 2, 2
Prime factors of 8 => 2, 2, 2
Prime factors of 27 => 3, 3, 3
We need the prime factors. Happily Part 5 of my «Centenary Sequences with Raku» article comes to the rescue... (Scroll down to the «Factors» section for the «factors» program.)
File: prime-order
#! /usr/bin/env raku
unit sub MAIN (*@int where all(@int) ~~ UInt # [1]
&& all(@int) > 0 # [1]
&& @int.elems == @int.unique.elems > 2, # [1a]
:v(:$verbose));
my %factor-count; # [2]
for @int -> $int # [3]
{
my @factors = factors($int); # [4]
%factor-count{$int} = @factors.elems; # [5]
say ":Int $int -> factors: { @factors.join(",") } -> count: \
{ @factors.elems }" if $verbose;
}
say @int.sort({ %factor-count{$^a} <=> %factor-count{$^b} || $^b <=> $^a });
# [6]
sub factors ($number is copy) # [7]
{
return (1) if $number == 1; # [8]
return ($number) if $number.is-prime; # [9]
my @factors; # [10]
for (2 .. $number div 2).grep( *.is-prime) -> $candidate # [11]
{
while $number %% $candidate # [12]
{
@factors.push: $candidate; # [13]
$number /= $candidate; # [14]
}
}
return @factors; # [15]
}
[1] Zero or more positive integers. They must be unique, i.e. have the same number of elements if we try to remove duplicates [1a]
[2] We are going to sort the values on the number of factors, and it is smart to cache these values so that the sort function can look them up (instead of computing them) all the time.
[3] Iterate over the integers.
[4] Get the factors (so that verbose mode can print them, if we so desire).
[5] Save the count for later.
[6] Sort the numbers, first on the number of factors (increasing order), and secondly on the number itself (decreasing number) if the counts are equal, and print the result.
[7] Procedure arguments are read only by default, so we use is copy
so that we can change the value itself (in [14]).
[8] The number one is not a prime, but we support it anyway.
[9]
See
docs.raku.org/routine/is-prime
for more information about is-prime.
[10] The prime factors will end up here.
[11] Iterate over the primes from 2 up to the number itself divided by 2. (As the largest prime cannot be larger than the number divided by 2, unless the number itself is a prime - and that was handled by [8]).
[12] As long as the candidate is a (prime) divisor,
[13] Add the candidate to the divisor list.
[14] Divide away the the divisor. (/= is the divide and assign
operator.)
[15] Return the divisors.
Running it:
$ ./prime-order 11 8 27 4
(11 4 27 8)
Looking good.
With verbose mode:
$ ./prime-order -v 11 8 27 4
:Int 11 -> factors: 11 -> count: 1
:Int 8 -> factors: 2,2,2 -> count: 3
:Int 27 -> factors: 3,3,3 -> count: 3
:Int 4 -> factors: 2,2 -> count: 2
(11 4 27 8)
And that's it.