Dois números contêm fatoriais exclusivos?

11

Divida dois números em seus fatoriais; se eles compartilharem algum, retorne um valor falsey. Caso contrário, retorne um valor verdadeiro. (inspirado nesta pergunta recente )

Em outras palavras, escreva cada número de entrada como a soma dos fatoriais (de números inteiros positivos) da maneira mais ambiciosa possível; retorne um valor verdadeiro se nenhum fatorial aparecer em ambas as representações, um valor falsey caso contrário.

Exemplo

Dado 20 e 49:

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

Nenhum fatorial aparece nas duas representações, portanto, retorne um valor verdadeiro.

Dados 32 e 132:

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

3! aparece nas duas representações, portanto, retorne um valor de falsey.

I / O

A entrada e a saída podem ser efetuadas por qualquer meio padrão .

A entrada sempre será dois números inteiros não negativos; nenhum limite superior para esses números inteiros além do que seu idioma exige.

A saída deve ser um valor verdadeiro ou falso . Esses valores não precisam necessariamente ser consistentes para entradas diferentes, desde que cada saída seja correta / verdadeira.

Casos de teste

Se uma entrada for 0, a resposta será sempre verdadeira. Outros casos de teste de verdade:

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

Se ambas as entradas são números inteiros ímpares ou se as duas entradas são o mesmo número inteiro positivo, a saída será sempre falsey. Outros casos de teste de 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}

Isso é código-golfe , e o menor número de bytes vence!

code-golf arithmetic decision-problem integer factorial Greg Martin
fonte
"escreva cada número de entrada como a soma dos fatoriais (de inteiros positivos) da maneira mais ambiciosa possível", você não quer dizer a maneira mais preguiçosa possível ?
user41805
4
@KritixiLithos no. Ele está se referindo à classe de algoritmos conhecidos como algoritmos gananciosos, que funcionam maximizando algumas métricas após cada etapa. Sempre pegando o máximo que podem.
John Dvorak

Respostas:

9

Geléia , 7 bytes

Æ!ṠḄ&/¬

Experimente online!

Como funciona

Æ!ṠḄ&/¬  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.
Dennis
fonte
Æ!parece incrivelmente útil em certos cenários.
Magic Octopus Urn
Há algo a ganhar tentando multiplicar elementarmente as listas fatoriais de base diretamente, sem receber sinais?
Greg Martin
@GregMartin Acho que não. As matrizes de dígitos teriam que ser preenchidas ou truncadas no mesmo comprimento, o que provavelmente custará mais bytes do que ele salva.
Dennis
3

Python 3 , 93 91 bytes

lambda a,b:k(a)&k(b)=={0}
k=lambda t,n=1,a=1:{t}&{0}or a*n>t and{a-1}|k(t-n)or k(t,n*a,a+1)

Experimente online!

ovs
fonte
3

Python 2 , 47 bytes

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

Experimente online!

xnor
fonte
Eu amo essa solução. Você poderia anotá-lo com um pouco do seu pensamento?
quer
2

JavaScript (ES6), 71 bytes

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

Os números inteiros do JavaScript são limitados a 53 bits de precisão, o que é suficiente para 18 !; isso significa que posso usar uma máscara de 18 bits para rastrear quais fatores são necessários.

Neil
fonte
2

PHP, 109 bytes

for(;$a?:$a=$argv[++$i];$a-=$r[$i][]=$f,$i<2?:$t+=in_array($f,$r[1]))for($c=$f=1;($a/$f*=$c)>=++$c;);echo!$t;

Experimente online!

Jörg Hülsermann
fonte
0

Mathematica, 73 bytes

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

formulário de entrada

[x1, x2]

J42161217
fonte
Estou ficando vários erros testando isso ...
Scott Milner
Basta digitar no final [x1, x2]
J42161217 5/17/17
Ah Eu estava inserindo uma lista, em vez de dois inteiros separados. Você pode jogar mais com ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61](69 bytes). Na codificação ISO 8859-1, o ±é um byte.
Scott Milner
0

C, 122 119 bytes

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é a função principal. Deve ser chamado com exatamente dois valores inteiros positivos. Isso sai com um código de saída0 for 1for truthy e false.

Embora isso não pareça funcionar no TIO, ele funciona no meu sistema com o Homebrew fornecido gcc 7.1.0.

Eu não pratico Cgolfe há um bom tempo, então as dicas de golfe são muito apreciadas!

R. Kap
fonte