This is my response to The Weekly Challenge #300.
$int.
n integers, 1-indexed, is considered a beautiful
arrangement if for every i (1 <= i <= n) either of the following
is true:
perm[i] is divisible by i
i is divisible by perm[i]
Input: $n = 2
Output: 2
1st arrangement: [1, 2]
perm[1] is divisible by i = 1
perm[2] is divisible by i = 2
2nd arrangement: [2, 1]
perm[1] is divisible by i = 1
i=2 is divisible by perm[2] = 1
Input: $n = 1
Output: 1
Input: $n = 10
Output: 700
#! /usr/bin/env raku
subset PosInt of Int where * > 0; # [1a]
unit sub MAIN (PosInt $int, :v(:$verbose)); # [1]
my $count = 0; # [2]
PERM: for (1 .. $int).permutations -> @perm # [3]
{
for 1 .. $int -> $index # [4]
{
unless @perm[$index -1] %% $index || $index %% @perm[$index -1] # [5]
{
say ": Not beautiful: ({ @perm.join(",") })" if $verbose;
next PERM; # [5a]
}
}
$count++; # [6]
say ": + Beatutiful #$count: ({ @perm.join(",") })" if $verbose;
}
say $count; # [7]
[1] Ensure a positive integer with a custom type (set
up with subset in [1a]).
See docs.raku.org/routine/subset for more information about subset.
[2] The number of beautiful arrangements, initially none.
[3] Iterate over all the permutations.
[4] Iterate over all the indices (1-based) in the current permutation.
[5] If the value does not comply with one of the two rules, discard this
permutation (with next) [5a], as we have falsified it as beautiful.
[6] Failure to falsify is the same as success, here at least.
[7] Print the count.
Running it:
$ ./beautiful-arrangement 2
2
$ ./beautiful-arrangement 1
1
$ ./beautiful-arrangement 10
700
Looking good.
The first two with verbose mode:
$ ./beautiful-arrangement -v 2
: + Beatutiful #1: (1,2)
: + Beatutiful #2: (2,1)
2
$ ./beautiful-arrangement -v 1
: + Beatutiful #1: (1)
1
Some more, just for fun:
$$ ./beautiful-arrangement -v 3
: + Beatutiful #1: (1,2,3)
: Not beautiful: (1,3,2)
: + Beatutiful #2: (2,1,3)
: Not beautiful: (2,3,1)
: Not beautiful: (3,1,2)
: + Beatutiful #3: (3,2,1)
3
$ ./beautiful-arrangement -v 4
: + Beatutiful #1: (1,2,3,4)
: Not beautiful: (1,2,4,3)
: Not beautiful: (1,3,2,4)
: Not beautiful: (1,3,4,2)
: Not beautiful: (1,4,2,3)
: + Beatutiful #2: (1,4,3,2)
: + Beatutiful #3: (2,1,3,4)
: Not beautiful: (2,1,4,3)
: Not beautiful: (2,3,1,4)
: Not beautiful: (2,3,4,1)
: Not beautiful: (2,4,1,3)
: + Beatutiful #4: (2,4,3,1)
: Not beautiful: (3,1,2,4)
: Not beautiful: (3,1,4,2)
: + Beatutiful #5: (3,2,1,4)
: Not beautiful: (3,2,4,1)
: + Beatutiful #6: (3,4,1,2)
: Not beautiful: (3,4,2,1)
: Not beautiful: (4,1,2,3)
: + Beatutiful #7: (4,1,3,2)
: Not beautiful: (4,2,1,3)
: + Beatutiful #8: (4,2,3,1)
: Not beautiful: (4,3,1,2)
: Not beautiful: (4,3,2,1)
8
@ints of length n
containing permutation of the numbers in the range [0, n - 1].
set[i] = ints[i], ints[ints[i]], ints[ints[ints[i]]], ...,
subjected to the following rules:
set[i] starts with the selection
of elements ints[i]
set[i] should be ints[ints[i]],
and then ints[ints[ints[i]]], and so on
set[i]
set[i].
Input: @ints = (5, 4, 0, 3, 1, 6, 2)
Output: 4
ints[0] = 5
ints[1] = 4
ints[2] = 0
ints[3] = 3
ints[4] = 1
ints[5] = 6
ints[6] = 2
One of the longest sets set[k]:
set[0] = {ints[0], ints[5], ints[6], ints[2]} = {5, 6, 2, 0}
Input: @ints = (0, 1, 2)
Output: 1
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 0 && all(@ints) ~~ Int,
:v(:$verbose)); # [1]
die "Duplicates" unless [<] @ints.sort; # [2]
die "Missing zero" unless @ints.min == 0; # [3]
die "Missing n" unless @ints.max == @ints.elems -1; # [4]
my @set = 0,; # [5]
loop # [6]
{
my $index = @set.tail; # [7]
my $value = @ints[$index]; # [8]
last if $value eq any(@set); # [9]
@set.push: @ints[$index]; # [10]
say ": @set[]" if $verbose;
}
say @set.elems; # [11]
[1] Ensure that we get at least 1 integer.
[2] Duplicate walues are not allowed.
[3] Zero is the lowest value.
[4] n is the highest value.
[2,3,4] Ensures that we have all the integers from 0 to
n.
[5] The first index is zero. This is the last one shown in the in the sets in the examples, but adding it initially bootstraps the loop (so that [7] works the first iteration). As the challenge does not really care about this array, this reordering does notg matter. (It is easy to reorder the final array, if you consier this an error.)
[6] En eternal loop, until [9] kicks in (or out).
[7] Get the last value in the set array, with tail.
This is the index of the next value.
See docs.raku.org/routine/tail for more information about tail.
[8] Get the next value.
[9] Exit the loop when we have a duplicate value/index;
i.e. one alredy in the set. An any Junction makes this check
easy.
See docs.raku.org/routine/any for more information about any.
[10] Add the value to the set array.
[11] Print the number of values in the set array.
Running it:
$ ./nested-array 5 4 0 3 1 6 2
4
$ ./nested-array 0 1 2
1
Looking good.
With verbose mode:
$ ./nested-array -v 5 4 0 3 1 6 2
: 0 5
: 0 5 6
: 0 5 6 2
4
$ ./nested-array -v 0 1 2
1
It is easy to get all the values/indices:
$ ./nested-array -v 1 2 3 4 5 0
: 0 1
: 0 1 2
: 0 1 2 3
: 0 1 2 3 4
: 0 1 2 3 4 5
6
And that's it.