Codegolf - Aocg2021. День 14: Корректировка Продолжительности Танцевальной Программы.

Часть Появление Кодекса Гольфа 2021 событие. Подробности смотрите в связанном мета-сообщении.

Связано с AoC2017, день 16. Я использую формулировку из моя головоломка Puzzling SE, основанная на той же задаче AoC вместо исходного AoC для ясности.

---

\$n\$ человек с номерами \$1, 2, \cdots, n\$ стоят в очереди в порядке соответствующего им номера. Они «танцуют» или меняются местами по каким-то заранее заданным инструкциям. Существует два типа инструкций, называемых Exchange и Partner:

• Эxchange(m,n): два человека, стоящие на m-й и n-й позициях, меняются местами.
• Пartner(x,y): два человека с номерами x и y меняются местами.

Например, если всего пять человек.

 
 
 1, 2
2, 3
3, 4
6, 35
6, 60
8, 16
16, 17
 
 
 

and they are given instructions E(2,3) and P(3,5) in order, the following happens:

• E(2,3): 2-й и 3-й люди меняются местами, поэтому линия становится n, m 1, 1 2, 2 3, 6 3, 3 8, 15 8, 120 16, 28 16, 5460 .
• P(3,5): Люди с номерами 3 и 5 меняются местами, поэтому линия становится 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 .

Давайте определим программа как фиксированная последовательность таких инструкций. Вы можете поместить в программу столько инструкций, сколько захотите.

Независимо от длины вашей программы, если вся программа повторяется достаточное количество раз, очередь людей в конечном итоге вернется в исходное состояние \$1,2,3,\cdots,n\$. Давайте определим программу период как наименьшее такое число (т.е. наименьшее положительное целое число \$m\$, при котором запуск программы \$m\$ раз сбрасывает линию людей в исходное положение). Состояния в середине программы не учитываются.

Например, программа E(2,3); P(3,5); E(3,4) has the period of 6:

15243

Теперь вы хотите написать программу для \$n\$ людей, чтобы ее период имел ровно \$m\$. Является ли это возможным?

Вход: Количество людей \$n\$ и целевой период \$m\$

Выход: Значение, указывающее, можно ли написать такую ​​программу или нет. Вы можете выбрать

• выводите истину/ложь, используя соглашение вашего языка (обмен разрешен), или
• используйте два различных фиксированных значения для обозначения истинного (утвердительного) или ложного (отрицательного) соответственно.

Применяются стандартные правила. Выигрывает самый короткий код в байтах.

Тестовые случаи

Правда:

13245

Ложь:

12345

#код-гольф #код-гольф #математика #задача принятия решения #теория чисел #целочисленные разбиения

Париж/GP, 59 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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)])
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Попробуйте онлайн!

Позволять

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

и |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} цикл по целочисленным разделам // 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 . Takes the LCM of all elements in //@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 and possible_loop=function(n,m,q=p(n)){for(i in q)for(j in q)F=F+!m-l(c(i,j);F} , and checks if it equals l=function(v){k=1;while(any(k%%v))k=k+1;k} . Выводит список списков, который является правдивым, если хотя бы один элемент является правдивым.

Для подробного объяснения, пожалуйста, прочитайте (и проголосуйте за него) Ответ xnor на Puzzle SE.

Здесь я лишь перечислю некоторые факты о перестановки (пожалуйста, прочитайте эту страницу Википедии для определения терминов):

Здесь под «перестановкой» я подразумеваю перестановку множества \$\{1,\dots,n\}\$.

1. Каждую перестановку можно записать как произведение двух циклов (замена двух элементов местами).
2. Таким образом, «программу» в этом вопросе можно рассматривать как умножение слева на перестановку \$X\$ и умножение справа на другую перестановку \$Y\$. Обозначим такую ​​программу через \$(X,Y)\$. Применить программу \$k\$ раз — это просто умножить \$X^k\$ слева и умножить \$Y^k\$ справа. «Период» \$(X,Y)\$ — это наименьший \$k>0\$ такой, что \$X^kY^k=\operatorname{id}\$. Здесь \$\operatorname{id}\$ — это перестановка, которая ничего не меняет.
3. Любую перестановку можно записать как произведение непересекающихся циклов.
4. Если мы запишем перестановку \$X\$ как произведение непересекающихся циклов, то порядок \$X\$ (т. е. наименьший \$k>0\$ такой, что \$X^k=\operatorname{id }\$) — НОК длин этих циклов. Длина цикла соответствует целочисленному разделу \$n\$.
5. Если \$k\$, \$l\$ — порядки перестановок \$X\$, \$Y\$ соответственно, то период программы \$(X,Y)\$ является делителем \ $\operatorname{lcm}(k,l)\$, но не обязательно равно \$\operatorname{lcm}(k,l)\$.
6. Но когда \$k\$ и \$l\$ взаимно просты, период \$(X,Y)\$ равен \$\operatorname{lcm}(k,l)=k\ l\$. Доказательство можно найти в ответе xnor на Puzzle SE.
7. Если \$k\$ — порядок некоторой перестановки, \$s\$ — делитель \$k\$, то существует перестановка с порядком \$s\$. Это видно из того, что если \$k\$ — порядок цикла \$C\$, \$s\$ — делитель \$k\$, то \$C^{k/s }\$ имеет порядок \$s\$.
8. Если \$\operatorname{lcm}(k,l)=m\$, \$u\$ делитель \$m\$, то мы всегда можем найти \$s\mid k\$, \$t\ Mid l\$ такой, что \$s\$ и \$t\$ взаимно просты, \$s\ t=u\$.
9. Таким образом, если \$k\$, \$l\$ — порядки перестановок \$X\$, \$Y\$ соответственно, мы всегда можем найти программу \$(X',Y')\$ (не обязательно то же, что и \$(X,Y)\$) с периодом \$\operatorname{lcm}(k,l)\$.
10. Таким образом, возможные периоды программ - это именно такие \$\operatorname{lcm}(k,l)\$, где \$k\$ и \$l\$ пробегают НОК целочисленных разделов \$n\$.

05AB1E, 10 байты

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))

Первый вход — \$n\$, второй — \$m\$.

Порт @алефальфаОтвет пользователя Pari/GP, так что обязательно проголосуйте за него!

Попробуйте онлайн или проверить все тестовые случаи.

Объяснение:

0 ||answer||

Python 3.8 (предварительная версия), 209, 187 (@pxeger), 180 179 байт (слияние)

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))

Попробуйте онлайн!

Старые версии

n

Попробуйте онлайн!

n

^ ^ ^ ^ ^ ^

Большое спасибо @pxeger!

0...n

Попробуйте это онлайн!

Попробуйте онлайн!

Объяснение

Мы можем думать о двух видах свопов как о «умножении слева или справа». Смысл этого в том, что мы можем перевернуть любую соседнюю пару свопов разного типа, не меняя результата, а пространство возможных цепочек свопов такое же, как одна произвольная перестановка слева и одна справа.

Поэтому нам необходимо знать период любой n-перестановки. Это можно получить из представления цикла. Период равен 1 см длины цикла. А объединенный (левый и правый) период - это lcm левого и правого lcms. РЕДАКТИРОВАТЬ В целом это не так. Однако верно то, что отмена может повлиять только на общие простые коэффициенты. Действительно. пусть A и B — левая и правая перестановки с периодами m и n. Если A^x B^x = 1 с x < lcm(m,n) и m имеет простой множитель p, которого нет ни в n, ни в x, то, возведя n-ю степень, мы получим A^(xn) = 1 что противоречит предположению, что период кратен p.

Выполнение n extracts the prime factors. The main function FALSE Простой: TRUE determines whether these powers can be distributed over two times n elements.

группирует их по полномочиям и

Руби 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}))

, 136 106 байт

Попробуйте онлайн!

Порт ответа Кевина Круйссена 05AB1E, который был портом ответа Alephalpha Pari/GP, но объяснен в терминах, понятных инженеру. :-)

Это очень медленно из-за грубого разделения: вместо того, чтобы пытаться хитрить, я просто получаю все комбинации из n чисел от 0 до n и фильтрую по сумме, а затем удаляю 0 при вычислении lcm.

Древесный уголь 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[] ) //

, 64 60 59 байт Попробуйте онлайн! 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)) for possible, nothing if not. Explanation: Based on @xnor's Puzzling.SE answer.

(m)(n)

Ссылка на подробную версию кода. Выводит логическое значение Charcoal, т.е. 120 and m .

8

Вход n into its prime power factors e.g. 8 .

8

Разложить {8},{3,5} , or expressed more golfily, the minimum possible maximum sums of two complementary sets of factors does not exceed 11 Проверить, можно ли разбить факторы на два множества, сумма которых не превосходит {5},{3,8} the sets are 13 . В случае {3},{5,8} , 16 максимальная сумма {},{3,5,8} , 3*5*8 максимальная сумма n , and n максимальная сумма ¬‹θ⌊ＥＸ²Ｌυ⌈Ｅ²↨¹Φυ⁼λ﹪÷ιＸ²ξ² . The minimum of these is 120=3*5*8 максимальная сумма m needs to be at least Ｆ…·²ηＷ¬﹪ηι«⊞υ×ι⎇﹪∨Πυ¹ι¹⊟υ≧÷ιη» , так m of n .

для

JavaScript (ES6), 107 байт ＮθＮη and returns \$0\$ for true or \$1\$ for false.

Ожидает На основе.

-

алгоритм Алефальфы

Попробуйте онлайн!

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

ПрокомментировалР

, 139 134 129 байт

->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)}}

Изменить: -5 байт благодаря pajonk

Попробуйте онлайн! Подход, основанный наответ алефальфы
: проголосуй за это! h if the loop is impossible, or f Возврат

если цикл возможен. g by first creating a Генерирует все пары целочисленных разделов огромный 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)) , and then testing the LCM of rows whose first and second halves each sum to 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] массив из удвоенных всех комбинаций 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] greater than 5.

---

. Так что не хватает памяти для любого, 204 178 176 байт

Изменить: -2 байта благодаря pajonk

Åœ # 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)

Попробуйте онлайн!

Предыдущая версия с более эффективной (но значительно более длинной) функцией целочисленного разделения, позволяющей ей фактически работать в тестовых случаях с n>5 (хотя время ожидания TIO все еще истекает для n=16 и выше).
Возврат Åœãε˜.¿}Iå (falsy) if the loop is not possible, or a non-zero integer (truthy) if the loop is possible.

рекурсивная функция p получает все целочисленные разделы (с некоторыми дубликатами)

m

функция л вычисляет LCM своего векторного аргумента

y

Итак, наконец, функция возможно_цикл использует их, чтобы проверить, возможен ли цикл:

x ||answer||

Типы TypeScript, 526 байт

n

Попробуйте онлайн!

Порт ответа Кевина Круйссена 05AB1E, который был портом ответа Alephalpha Pari/GP, но объяснен в терминах, понятных инженеру. :-)

Негольфед / Объяснение

y ||answer||

Ржавчина, 345 305 байт

x

Попробуйте онлайн!

Также порт ответа @alephapha. Значительная часть — это просто реализация секционирования и LCM.

• -40 байт за счет замены реализации LCM

Язык Wolfram (Математика), 51 байт

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

Попробуйте онлайн!