Два числа содержат уникальные факториалы?

11

Разбейте два числа на их факториалы; если они разделяют их, возвращают значение фальси. В противном случае верните истинное значение. (вдохновленный этим недавним вопросом )

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

пример

Учитывая 20 и 49:

20 = 3! + 3! + 3! + 2!
49 = 4! + 4! + 1!

В обоих представлениях нет факториала, поэтому верните истинное значение.

Дано 32 и 132:

132 = 5! + 3! + 3!
 32 = 4! + 3! + 2!

3! появляется в обоих представлениях, так что возвращайте ложное значение.

I / O

Ввод и вывод может быть любым стандартным способом .

Ввод всегда будет двумя неотрицательными целыми числами; нет верхней границы этих целых чисел, кроме того, что требует ваш язык.

Вывод должен быть истинным или ложным значением . Эти значения не обязательно должны быть согласованными для разных входных данных, если каждый выходной результат корректен / неверен.

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

Если один вход 0, ответ всегда будет правдивым. Другие правдивые тестовые случаи:

{6, 3}, {4, 61}, {73, 2}, {12, 1}, {240, 2}, {5, 264}, {2, 91}, {673, 18},
 {3, 12}, {72, 10}, {121, 26}, {127, 746}

Если оба входа являются нечетными целыми числами, или если оба входа являются одним и тем же положительным целым числом, то результат всегда будет ложным. Другие тесты Falsey:

{8, 5}, {7, 5}, {27, 47}, {53, 11}, {13, 123}, {75, 77}, {163, 160}, {148, 53},
 {225, 178}, {285, 169}, {39, 51}, {207, 334}, {153, 21}, {390, 128}, {506, 584},
 {626, 370}, {819, 354}

Это код-гольф , поэтому побеждает меньше байтов!

code-golf arithmetic decision-problem integer factorial Грег Мартин
источник
«запишите каждое входное число как сумму факториалов (натуральных чисел) самым жадным образом», разве вы не имеете в виду самый ленивый способ вместо этого?
user41805
4
@ KritixiLithos нет. Он ссылается на класс алгоритмов, известных как жадные алгоритмы, которые работают, максимизируя некоторую метрику после каждого шага. Как, всегда, принимая столько, сколько они могут.
Джон Дворак

Ответы:

9

Желе , 7 байт

Æ!ṠḄ&/¬

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

Как это работает

Æ!ṠḄ&/¬  Main link. Argument: (x, y) (pair of integers)

Æ!       Convert x and y to factorial base.
  Ṡ      Apply the sign function to each digit.
   Ḅ     Unbinary; convert each resulting Boolean array from base 2 to integer.
    &/   Reduce the resulting pair of integers by bitwise AND.
      ¬  Take the logical NOT of the result.
Деннис
источник
Æ!кажется безумно полезным в определенных сценариях.
Волшебная Осьминог Урна
Есть ли что-то, что можно получить, пытаясь поэлементно умножать списки факториальной базы напрямую, без признаков?
Грег Мартин
@GregMartin Я так не думаю. Массивы цифр должны быть дополнены или усечены до той же длины, что, вероятно, будет стоить больше байтов, чем экономит.
Деннис
3

Python 2 , 47 байт

h=lambda a,b,d=2:a<1or a%d*(b%d)<h(a/d,b/d,d+1)

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

XNOR
источник
Я люблю это решение. Не могли бы вы аннотировать это с небольшим количеством вашего мышления?
Час Браун
2

JavaScript (ES6), 71 байт

(a,b,g=(n,e=1,f=1)=>n>=f&&g(n,++e,f*e)+((n/f|0)%e&&1<<e))=>!(g(a)&g(b))

Целые числа JavaScript ограничены 53 битами точности, что почти достаточно для 18 !; это означает, что я могу использовать маску из 18 бит, чтобы отслеживать, какие факториалы нужны.

Нил
источник
0

Mathematica, 73 байта

F[x_]:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[F@#,F@#2]&

форма ввода

[X1, x2]

J42161217
источник
Я получаю несколько ошибок при тестировании этого ...
Скотт Милнер
Просто введите в конце [x1, x2]
J42161217
Ах. Я вводил список, а не два отдельных целых числа. Вы можете играть в гольф дальше ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61](69 байт). В кодировке ISO 8859-1 ±это один байт.
Скотт Милнер
0

C 122 119 байт

G(q,i){return gamma(q+1)>i?gamma(q):G(q+1,i);}
Q(a,b,u,v){while(a&&b){a-=u=G(1,a);b-=v=G(1,b);if(a==b)exit();}exit(0);}

Qэто основная функция. Он должен вызываться ровно с двумя положительными целочисленными значениями. Это выход с кодом выхода из 0для truthy и 1для falsy.

Хотя это, похоже, не работает на TIO, он работает на моей системе с предоставленным Homebrewgcc 7.1.0 .

Я давно не играл в Cгольф, поэтому советы по игре в гольф очень ценятся!

Р. Кап
источник