Part of Advent of Code Golf 2021 event. See the linked meta post for details.
Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the original AoC one for clarity.
\$n\$ people numbered \$1, 2, \cdots, n\$ are standing in line in the order of their corresponding numbers. They "dance", or swap places, according to some predefined instructions. There are two kinds of instructions called Exchange and Partner:
- Exchange(m,n): The two people standing at m-th and n-th positions swap places.
- Partner(x,y): The two people numbered x and y swap places.
For example, if there are only five people
12345 and they are given instructions E(2,3) and P(3,5) in order, the following happens:
- E(2,3): The 2nd and 3rd people swap places, so the line becomes
- P(3,5): The people numbered 3 and 5 swap places, so the line becomes
Let's define a program as a fixed sequence of such instructions. You can put as many instructions as you want in a program.
Regardless of the length of your program, if the whole program is repeated a sufficient number of times, the line of people will eventually return to the initial state \$1,2,3,\cdots,n\$. Let's define the program's period as the smallest such number (i.e. the smallest positive integer \$m\$ where running the program \$m\$ times resets the line of people to the initial position). The states in the middle of a program are not considered.
For example, a program
E(2,3); P(3,5); E(3,4) has the period of 6:
E(2,3) P(3,5) E(3,4) 1. 12345 -> 13245 -> 15243 -> 15423 2. 15423 -> 14523 -> 14325 -> 14235 3. 14235 -> 12435 -> 12453 -> 12543 4. 12543 -> 15243 -> 13245 -> 13425 5. 13425 -> 14325 -> 14523 -> 14253 6. 14253 -> 12453 -> 12435 -> 12345
Now, you want to write a program for \$n\$ people so that it has the period of exactly \$m\$. Is it possible?
Input: The number of people \$n\$ and the target period \$m\$
Output: A value indicating whether it is possible to write such a program or not. You can choose to
- output truthy/falsy using your language's convention (swapping is allowed), or
- use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.
Standard code-golf rules apply. The shortest code in bytes wins.
n, m 1, 1 2, 2 3, 6 3, 3 8, 15 8, 120 16, 28 16, 5460
1, 2 2, 3 3, 4 6, 35 6, 60 8, 16 16, 17