The weekly challenge 300 - Task 1: Beautiful Arrangement

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-300/#TASK1
 3 #
 4 # Task 1: Beautiful Arrangement
 5 # =============================
 6 #
 7 # You are given a positive integer, $int.
 8 #
 9 # Write a script to return the number of beautiful arrangements that you can construct.
10 #
11 # A permutation of n integers, 1-indexed, is considered a beautiful arrangement
12 # if for every i (1 <= i <= n) either of the following is true:
13 #
14 # 1) perm[i] is divisible by i
15 # 2) i is divisible by perm[i]
16 #
17 ## Example 1
18 ##
19 ## Input: $n = 2
20 ## Output: 2
21 ##
22 ## 1st arrangement: [1, 2]
23 ##     perm[1] is divisible by i = 1
24 ##     perm[2] is divisible by i = 2
25 ## 2nd arrangement: [2, 1]
26 ##     perm[1] is divisible by i = 1
27 ##     i=2 is divisible by perm[2] = 1
28 #
29 ## Example 2
30 ##
31 ## Input: $n = 1
32 ## Output: 1
33 #
34 ## Example 3
35 ##
36 ## Input: $n = 10
37 ## Output: 700
38 #
39 ############################################################
40 ##
41 ## discussion
42 ##
43 ############################################################
44 #
45 # First, we find all permutations, then we check for each one whether it is a
46 # beautiful one. Once done, we return the result.
47 
48 use strict;
49 use warnings;
50 use Algorithm::Combinatorics qw(permutations);
51 
52 beautiful_arrangement(2);
53 beautiful_arrangement(1);
54 beautiful_arrangement(10);
55 
56 sub beautiful_arrangement {
57    my $int = shift;
58    print "Input: $int\n";
59    my $found = 0;
60    my $iter = permutations([1..$int]);
61    while(my $p = $iter->next) {
62       my $is_beautiful = 1;
63       foreach my $i (1..$int) {
64          if($p->[$i-1] % $i and $i % $p->[$i-1] ) {
65             $is_beautiful = 0;
66             last;
67          }
68       }
69       $found++ if $is_beautiful;
70    }
71    print "Output: $found\n";
72 }