1. Introduction
The Weekly Challenge, organized by Mohammad S. Anwar, is a friendly competition in which developers compete by solving a pair of tasks. It encourages participation from developers of all languages and levels through learning, sharing, and having fun.
Task 1: Beautiful Arrangement from The Weekly Challenge invites developers to find the number of beautifully arranged permutations from among all permutations generated from a positive integer.
In this post I discuss, and present my solution to, Task 1: Beautiful Arrangement, and end a brief conclusion.
The Weekly Challenge 300 deadline is Sunday, December 23, 2024 at 23:59 (UK Time). To avoid bias, consider reading this post after competing.
2. Task 1: Beautiful Arrangement
You are given a positive integer, $int.
Write a script to return the number of beautiful arrangements that you can construct from $int.
A permutation of n integers, 1-indexed, is considered a beautiful arrangement if for every i (1 either of the following is true:
The Weekly Challenge 300, Task 1: Beautiful Arrangement
Examples 1 and 2 present the expected outputs from given inputs.
Example 1
Input: $n = 2
Output: 2
For n = 2 and with i integers such that (1 there are two permutations (1, 2) and (2, 1). Output: 2 because both meet the beautiful arrangement requirements.
The permutation (1, 2) is a beautiful arrangement because all of its elements match the first condition:
The permutation(2, 1) is also a beautiful arrangement because all of its elements match either the first or second condition:
Example 2
Input: $n = 1
Output: 1
Example 3
Input: $n = 10
Output: 700
3. My solution to Task 1
from itertools import permutations
def generate_permutations(n)
iterable = list(range(1, n + 1))
return permutations(iterable)
def count_beautiful_arrangements(perms):
num_beautiful_arr = 0
for perm in perms:
is_beautiful_arr = True
for value_index, value in enumerate(perm):
if value % (value_index + 1) == 0:
continue
elif (value_index + 1) % value == 0:
continue
else:
is_beautiful_arr = False
break
if is_beautiful_arr == True:
num_beautiful_arr += 1
return num_beautiful_arr
My inelegant and unsophisticated solution utilizes two functions generate_permutations and count_beautiful_arrangements.
generate_permutations returns, for the parameter n, all permutations for the set where 1 .
count_beautiful_permutations returns, for the permutations iterable perms parameter, the total number of permutations in perms that match the beautiful arrangement conditions.
4. Conclusion
In this post I discussed Task 1: Beautiful Arrangement and I presented my solution. My 'inelegant and unsophisticated' solution works, but it has considerable room for improvement.
More...
The Weekly Challenge, organized by Mohammad S. Anwar, is a friendly competition in which developers compete by solving a pair of tasks. It encourages participation from developers of all languages and levels through learning, sharing, and having fun.
Task 1: Beautiful Arrangement from The Weekly Challenge invites developers to find the number of beautifully arranged permutations from among all permutations generated from a positive integer.
In this post I discuss, and present my solution to, Task 1: Beautiful Arrangement, and end a brief conclusion.
The Weekly Challenge 300 deadline is Sunday, December 23, 2024 at 23:59 (UK Time). To avoid bias, consider reading this post after competing.
2. Task 1: Beautiful Arrangement
You are given a positive integer, $int.
Write a script to return the number of beautiful arrangements that you can construct from $int.
A permutation of n integers, 1-indexed, is considered a beautiful arrangement if for every i (1 either of the following is true:
- permutation[i] is divisible by i
- i is divisible by permutation[i]
The Weekly Challenge 300, Task 1: Beautiful Arrangement
Examples 1 and 2 present the expected outputs from given inputs.
Example 1
Input: $n = 2
Output: 2
For n = 2 and with i integers such that (1 there are two permutations (1, 2) and (2, 1). Output: 2 because both meet the beautiful arrangement requirements.
The permutation (1, 2) is a beautiful arrangement because all of its elements match the first condition:
- At i = 1, permutation[1] = 1 satisfies the first condition, since one is divisible by one.
- At i = 2, permutation[2] = 2 satisfies the first conditions, since two is divisible by two.
The permutation(2, 1) is also a beautiful arrangement because all of its elements match either the first or second condition:
- At i = 1, permutation[1] = 2 satisfies the first condition, since two is divisible by one.
- At i = 2, permutation[2] = 1 satisfies the second condition, since two is divisible by one.
Example 2
Input: $n = 1
Output: 1
Example 3
Input: $n = 10
Output: 700
3. My solution to Task 1
from itertools import permutations
def generate_permutations(n)
iterable = list(range(1, n + 1))
return permutations(iterable)
def count_beautiful_arrangements(perms):
num_beautiful_arr = 0
for perm in perms:
is_beautiful_arr = True
for value_index, value in enumerate(perm):
if value % (value_index + 1) == 0:
continue
elif (value_index + 1) % value == 0:
continue
else:
is_beautiful_arr = False
break
if is_beautiful_arr == True:
num_beautiful_arr += 1
return num_beautiful_arr
My inelegant and unsophisticated solution utilizes two functions generate_permutations and count_beautiful_arrangements.
generate_permutations returns, for the parameter n, all permutations for the set where 1 .
- iterable = list(range(1, n + 1)) generates a list of integers where 1 .
- permutations(iterable), imported from the itertools module, generates all permutations of iterable.
count_beautiful_permutations returns, for the permutations iterable perms parameter, the total number of permutations in perms that match the beautiful arrangement conditions.
- The outer loop for perm in... iterates through each permutation.
- It starts with the assumption that perm is a beautiful arrangement (is_beautiful_arr = True).
- The inner loop for value_index, value in... checks if each element of perm matches either condition 1 or condition 2.
- If all elements match either condition, perm is counted as a beautiful arrangement.
- Otherwise, if any element matches neither condition 1 nor condition 2, then is_beautiful_arr is set to False, the loop breaks early and perm is not counted as a beautiful arrangement.
- The inner loop for value_index, value in... checks if each element of perm matches either condition 1 or condition 2.
4. Conclusion
In this post I discussed Task 1: Beautiful Arrangement and I presented my solution. My 'inelegant and unsophisticated' solution works, but it has considerable room for improvement.
More...