15
\$\begingroup\$

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 13245.
  • P(3,5): The people numbered 3 and 5 swap places, so the line becomes 15243.

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 rules apply. The shortest code in bytes wins.

Test cases

Truthy:

n, m
1, 1
2, 2
3, 6
3, 3
8, 15
8, 120
16, 28
16, 5460

Falsy:

1, 2
2, 3
3, 4
6, 35
6, 60
8, 16
16, 17
Improve this question
\$\endgroup\$

10 Answers 10

Reset to default
10
\$\begingroup\$

Pari/GP, 59 bytes

(n,m)->[[lcm(Vec(concat(p,q)))==m|q<-s]|p<-s=partitions(n)]

Try it online!

Let x and y loop over the integer partitions of n. Takes the LCM of all elements in x and y, and checks if it equals m. Outputs a list of lists, which is truthy when at least one element is truthy.

For a detailed explanation, please read (and upvote) xnor's answer on Puzzle SE.

Here I only list some facts about permutations (please read this Wikipedia page for the definition of the terms):

Here by "permutation" I mean a permutation of the set \$\{1,\dots,n\}\$.

  1. Every permutation can be written as a product of 2-cycles (swapping two elements).
  2. So a "program" in this question can be seen as left multiplying a permutation \$X\$, and right multiplying another permutation \$Y\$. Let \$(X,Y)\$ denote such a program. Applying the program \$k\$ times is just left multiplying \$X^k\$ and right multiplying \$Y^k\$. The "period" of \$(X,Y)\$ is the smallest \$k>0\$ such that \$X^kY^k=\operatorname{id}\$. Here \$\operatorname{id}\$ is the permutation that changes nothing.
  3. Every permutation can be written as a product of disjoint cycles.
  4. If we write a permutation \$X\$ as a product of disjoint cycles, then the order of \$X\$ (i.e., the smallest \$k>0\$ such that \$X^k=\operatorname{id}\$) is the LCM of the lengths of these cycles. The cycle lengths corresponds to an integer partition of \$n\$.
  5. If \$k\$, \$l\$ are the orders of permutations \$X\$, \$Y\$ respectively, then the period of the program \$(X,Y)\$ is a divisor of \$\operatorname{lcm}(k,l)\$, but not necessarily equals \$\operatorname{lcm}(k,l)\$.
  6. But when \$k\$ and \$l\$ are coprime, the period of \$(X,Y)\$ does equal \$\operatorname{lcm}(k,l)=k\ l\$. A proof can be found in xnor's answer on Puzzle SE.
  7. If \$k\$ is the order of some permutation, \$s\$ a divisor of \$k\$, then there exists a permutation with order \$s\$. This can be seen from the fact that, if \$k\$ is the order of a cycle \$C\$, \$s\$ a divisor of \$k\$, then \$C^{k/s}\$ has order \$s\$.
  8. If \$\operatorname{lcm}(k,l)=m\$, \$u\$ a divisor of \$m\$, then we can always find \$s\mid k\$, \$t\mid l\$ such that \$s\$ and \$t\$ are coprime, \$s\ t=u\$.
  9. So if \$k\$, \$l\$ are the orders of permutations \$X\$, \$Y\$ respectively, we can always find a program \$(X',Y')\$ (not necessarily the same as \$(X,Y)\$) with period \$\operatorname{lcm}(k,l)\$.
  10. So the possible periods of programs are exactly these \$\operatorname{lcm}(k,l)\$, where \$k\$ and \$l\$ run over the LCM's of integer partitions of \$n\$.
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 10 bytes

Åœãε˜.¿}Iå

First input is \$n\$, second is \$m\$.

Port of @alephalpha's Pari/GP answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Ŝ       # Get all lists of positive integers that sum to the first (implicit)
         # input `n`
  ã      # Use the cartesian power to create all possible pairs of these lists
   ε     # Map over each pair of lists:
    ˜    #  Flatten it to a single list
     .¿  #  Pop and push the LCM (Least Common Multiple)
   }Iå   # After the map: check if the second input `m` is in this list
         # (after which this is output implicitly as result)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 209, 187 (@pxeger), 180 179 bytes (merge)

lambda n,m:any(sum(g(m))-n<=s<=n for s in h(g(m)))
g=lambda a,p=2,e=0:a%p and[p**e][:e]+g(a,p+1)or g(a//p,p,e+1)if a+e>1else[]
h=lambda p,S=0:p and h(p[1:],S)+h(p[1:],S+p[0])or[S]

Try it online!

Older versions

lambda n,m:any(sum(g(m))-n<=s<=n for s in h(g(m)))
g=lambda a,p=2,e=0:a+e>1 and(a%p and[p**e][:e]+g(a,p+1)or g(a//p,p,e+1))or[]
h=lambda p,S=0:p and h(p[1:],S)+h(p[1:],S+p[0])or[S]

Try it online!

lambda n,m:(c:={x**g(m).count(x)for x in g(m)})!=1in(sum(c)-n<=s<=n for s in h(c))
g=lambda a,p=2:a%p and g(a,p+1)or[p]+g(a//p,p)if a>1else[]
h=lambda c:sum([h(c-{x})for x in c],[sum(c)])

^ ^ ^ ^ ^ ^ Big thanks @pxeger!

Attempt This Online!

g=lambda a,p=2:a>1 and(a%p and g(a,p+1)or[p]+g(a//p,p))or[]
def h(c):
 yield sum(c)
 for x in c:
  yield from h(c-{x})
def f(n,m):
 c={x**g(m).count(x)for x in{*g(m)}}
 return any(sum(c)-n<=s<=n for s in h(c))

Try it online!

Explanation

We can think of the two kinds of swaps as "multiplying from the left or right". The significance of this is that we can flip any adjacent pair of different kind swaps without changing the outcome and the space of possible chains of swaps is the same as one arbitrary permutation from the left and one from the right.

We therefore need to know the period of any n-permutation. This can be derived from the cycle representation. The period is just the lcm of the cycle lengths. And the combined (left and right) period is the lcm of the left and right lcms EDIT This is not generally true. What is, however, true is that cancellation can only affect shared prime factors. Indeed. let A and B the left and right permutations with periods m and n. If A^x B^x = 1 with x < lcm(m,n) and m has a prime factor p that is neither in n nor in x then by taking the n-th power we get A^(xn) = 1 contradicting the assumption that the period be a multiple of p.

Implementation

Straight forward: g extracts the prime factors. The main function f groups them into powers and h determines whether these powers can be distributed over two times n elements.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ h can be h=lambda c:sum([h(c-{x})for x in c],[sum(c)]) \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 1:57
  • \$\begingroup\$ {*g(m)} can just be g(m) since the output is already uniquified by being in a set comprehension \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 1:58
  • \$\begingroup\$ g can be g=lambda a,p=2:a%p and g(a,p+1)or[p]+g(a//p,p)if a>1else[] \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 2:01
  • \$\begingroup\$ f can be lambda n,m:(c:={x**g(m).count(x)for x in g(m)})!=1in{sum(c)-n<=s<=n for s in h(c)} \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 2:08
  • 2
    \$\begingroup\$ Thanks a lot! @pxeger. Actually, I was busy myself while you were working, so the current best does not yet include your golfs. I'll see what can be salvaged/transplanted. \$\endgroup\$
    – loopy walt
    Dec 14, 2021 at 2:30
3
\$\begingroup\$

Ruby, 136 106 bytes

->n,m{z=([*0..n]*n).combination(n).select{|x|x.sum==n};z.product(z).any?{|a,b|m==(a+b-[0]).reduce(&:lcm)}}

Try it online!

Port of Kevin Crujssen's 05AB1E answer, which was a port of alephalpha's Pari/GP answer, but explained in terms an engineer can understand. :-)

This is very slow because of the brute force partitioning: instead of trying to be clever, I just get all combinations of n numbers between 0 and n, and filter by sum, then remove the 0s when calculating lcm.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Lol. If you ignore all the additional fluff, alephalpha's first sentence sums it up pretty well tbh: "Let x and y loop over the integer partitions of n. Takes the LCM of all elements in x and y, and checks if it equals m. If this is true for at least one pair (x, y), returns true." :) \$\endgroup\$
    – Kevin Cruijssen
    Dec 14, 2021 at 10:42
3
\$\begingroup\$

Charcoal, 64 60 59 bytes

ＮθＮηＦ…·²ηＷ¬﹪ηι«⊞υ×ι⎇﹪∨Πυ¹ι¹⊟υ≧÷ι绬‹θ⌊ＥＸ²Ｌυ⌈Ｅ²↨¹Φυ⁼λ﹪÷ιＸ²ξ²

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for possible, nothing if not. Explanation: Based on @xnor's Puzzling.SE answer.

ＮθＮη

Input n and m.

Ｆ…·²ηＷ¬﹪ηι«⊞υ×ι⎇﹪∨Πυ¹ι¹⊟υ≧÷ιη»

Decompose m into its prime power factors e.g. 120=3*5*8.

¬‹θ⌊ＥＸ²Ｌυ⌈Ｅ²↨¹Φυ⁼λ﹪÷ιＸ²ξ²

Check whether the factors can be partitioned into two sets neither sum of which exceeds n, or expressed more golfily, the minimum possible maximum sums of two complementary sets of factors does not exceed n. In the case of 3*5*8 the sets are {},{3,5,8} maximum sum 16, {3},{5,8} maximum sum 13, {5},{3,8} maximum sum 11, and {8},{3,5} maximum sum 8. The minimum of these is 8, so n needs to be at least 8 for an m of 120.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 107 bytes

Expects (m)(n) and returns \$0\$ for true or \$1\$ for false.

Based on alephalpha's algorithm.

m=>F=(n,i=a=[1],p=1,g=q=>v%p?g(q,v+=q):v)=>n?i>n||F(n-i,i,g(v=i++))&F(n,i,p):a.every(x=>g(v=x)-m,a.push(p))

Try it online!

Commented

m =>              // outer function taking the period m
F = (             // inner recursive function taking:
  n,              //   n   = number of people
  i =             //   i   = current value for integer partition
  a = [1],        //   a[] = list of LCMs
  p = 1,          //   p   = previous LCM
  g = q =>        //   g is a helper function taking q
  v % p ?         //   and computing LCM(p, q)
    g(q, v += q)  //   it must be called with v = q
  :               //
    v             //
) =>              //
n ?               // if n is not equal to 0:
  i > n ||        //   abort if i > n
  F(              //   otherwise do a 1st recursive call:
    n - i,        //     where i is subtracted from n,
    i,            //     i is left unchanged
    g(v = i++)    //     and p is updated to LCM(p, i)
  ) &             //
  F(              //   then do a 2nd recursive call:
    n,            //     where n is left unchanged,
    i,            //     i is incremented (this is done above)
    p             //     and p is left unchanged
  )               //
:                 // else (n = 0):
  a.every(x =>    //   test whether all x in a[]
    g(v = x) - m, //   are such that LCM(p, x) ≠ m
    a.push(p)     //   and append p to a[]
  )               //
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

R, 139 134 129 bytes

Edit: -5 bytes thanks to pajonk

function(n,m)all(apply(expand.grid(rep(list(0:n),2*n)),1,function(v){while(sum(v[1:n])==n&sum(v)==2*n&any(T%%v[v>0]))T=T+1;m-T}))

Try it online!

Approach based on alephalpha's answer: upvote that!
Returns TRUE if the loop is impossible, or FALSE if the loop is possible.

Generates all pairs of integer partitions of n by first creating a huge array of twice all combinations of 0...n, and then testing the LCM of rows whose first and second halves each sum to n. So runs out of memory for any n greater than 5.

R, 204 178 176 bytes

Edit: -2 bytes thanks to pajonk

function(n,m,q=p(n),`[`=`for`){i[q,j[q,{k=1;while(any(k%%c(i,j)))k=k+1;F=F+!m-k}]];F}
p=function(x,y=x[1])c(list(x),if(y>1)unlist(lapply(2:y-1,function(i)p(c(i,y-i,x[-1]))),F))

Try it online!

Previous version with more-efficient (but significantly longer) integer partition function, allowing it to actually run on test cases with n>5 (although still times-out on TIO for n=16 and higher).
Returns 0 (falsy) if the loop is not possible, or a non-zero integer (truthy) if the loop is possible.

recursive function p gets all integer partitions (with some duplicates)

p=function(x,y=x[1])c(list(x),if(y>1)unlist(lapply(2:y-1,function(i)p(c(i,y-i,x[-1]))),F))

function l calculates the LCM of its vector argment

l=function(v){k=1;while(any(k%%v))k=k+1;k}

So, finally, function possible_loop uses these to check if the loop is possible:

possible_loop=function(n,m,q=p(n)){for(i in q)for(j in q)F=F+!m-l(c(i,j);F}
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Well done, that's some heavy golfing. Here' some more: -2 bytes with redefining for. \$\endgroup\$
    – pajonk
    Dec 14, 2021 at 20:17
  • 1
    \$\begingroup\$ @pajonk - Thanks! In the meantime I found a different - shorter but much less efficient - approach, too... \$\endgroup\$
    – Dominic van Essen
    Dec 15, 2021 at 8:03
  • \$\begingroup\$ -5 bytes by flipping TRUE/FALSE and getting rid of leftover e=. \$\endgroup\$
    – pajonk
    Dec 15, 2021 at 9:17
  • \$\begingroup\$ @pajonk - Thanks (and of course you're right about e= being a 'leftover'!) \$\endgroup\$
    – Dominic van Essen
    Dec 15, 2021 at 9:39
2
\$\begingroup\$

TypeScript Types, 526 bytes

//@ts-ignore
type a<A,B,Q=[]>=A extends[...B,...infer X]?a<X,B,[...Q,0]>:[Q,A];type b<A,B,N=[]>=A extends[0,...infer A]?b<A,B,[...N,...B]>:N;type c<A,B>=[]extends A|B?Exclude<A|B,[]>:c<B,a<A,B>[1]>;type d<A,N=[0]>=A extends[infer M,...infer A]?d<A,b<a<M,c<M,N>>[0],N>>:N;type e<T,A=[],N=[0]>=T extends[0,...infer U]?|e<U,[...A,N],[0]>|e<U,A,[...N,0]>:[...A,N];type f<T,N=[]>=T extends N["length"]?N:f<T,[...N,0]>;type M<M,N,P=e<f<M>extends[0,...infer T]?T:0>,Q=P,O=P extends P?Q extends Q?d<[...P,...Q]>:0:0>=f<N>extends O?1:0

Try It Online!

Port of Kevin Crujssen's 05AB1E answer, which was a port of alephalpha's Pari/GP answer, but explained in terms an engineer can understand. :-)

Ungolfed / Explanation

// Returns [A / B, A % B]
type DivMod<A, B, Q = []> = A extends [...B, ...infer X] ? DivMod<X, B, [...Q, 0]> : [Q, A]

type Mult<A, B, N = []> = A extends [0, ...infer A] ? Mult<A, B, [...N, ...B]> : N

// Returns the GCD of A and B using the Euclidean algorithm
type Gcd<A, B> = [] extends A | B ? Exclude<A | B, []> : Gcd<B, DivMod<A, B>[1]>

// Returns the LCM of all the elements of A
type Lcm<A, N=[0]> = A extends [infer M, ...infer A] ? Lcm<A, Mult<DivMod<M, Gcd<M, N>>[0], N>> : N

// Returns a union of all integer partitions of T+1
type Partitions<
  T,
  // All previous numbers
  Arr = [],
  // The most recent number
  N = [0]
> =
  // U = T - 1
  T extends [0, ...infer U]
    // Return both:
    ? 
      // The paritions if we end N here
      | Partitions<U, [...Arr, N], [0]>
      // The paritions if we add one to N here
      | Partitions<U, Arr, [...N, 0]>
    // T is zero
    : [...Arr, N]

// Converts a number literal into a tuple representation
type NumToTuple<T, N = []> = T extends N["length"] ? N : NumToTuple<T, [...N, 0]>

type Main<
  M,
  N,
  P = Partitions</* M - 1 */ NumToTuple<M> extends[0,...infer T]?T:0>,
  Q = P,
  // Map over the cross of P and Q and compute the LCMs
  Ns = P extends P ? Q extends Q ? Lcm<[...P, ...Q]> : 0 : 0
> =
  // Return 1 if N is in Ns
  NumToTuple<N> extends Ns ? 1 : 0
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Rust, 345 305 bytes

|n,m|{fn p(n:u64)->Vec<Vec<u64>>{let mut v=vec![];if n>0{v.push(vec![n]);for i in 1..n{for mut x in p(n-i).drain(..){x.push(i);x.sort();if!v.contains(&x){v.push(x)}}}}v}let q=p(n);for i in 0..q.len(){for j in i..q.len(){if(1..).find(|v|q[i].iter().chain(&q[j]).all(|a|v%a<1))==Some(m){return true}}}false}

Try it online!

Also a port of @alephalpha's answer. A good chunk of it is just implementing partitioning and LCM.

  • -40 bytes by replacing the LCM implementation
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 51 bytes

!Outer[LCM,l=LCM@@@IntegerPartitions@#,l]~FreeQ~#2&

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.