Deux nombres contiennent-ils des factorielles uniques?

11

Divisez deux nombres en leurs factoriels; s'ils en partagent, renvoyez une valeur de falsey. Sinon, retournez une valeur véridique. (inspiré par cette question récente )

En d'autres termes, écrivez chaque nombre d'entrée comme la somme des factorielles (d'entiers positifs) de la manière la plus gourmande possible; retourner une valeur véridique si aucune factorielle n'apparaît dans les deux représentations, une valeur de falsey sinon.

Exemple

Étant donné 20 et 49:

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

Aucun factoriel n'apparaît dans les deux représentations, donc retournez une valeur véridique.

Étant donné 32 et 132:

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

3! apparaît dans les deux représentations, retournez donc une valeur de falsey.

E / S

L'entrée et la sortie peuvent se faire par n'importe quel moyen standard .

L'entrée sera toujours deux entiers non négatifs; aucune limite supérieure sur ces entiers autre que ce dont votre langue a besoin.

La sortie doit être une valeur true ou falsey . Ces valeurs ne doivent pas nécessairement être cohérentes pour différentes entrées, tant que chaque sortie est correctement véridique / falsey.

Cas de test

Si une entrée est 0, la réponse sera toujours véridique. Autres cas de test véridiques:

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

Si les deux entrées sont des entiers impairs, ou si les deux entrées sont le même entier positif, alors la sortie sera toujours falsey. Autres cas de test 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}

Il s'agit de code-golf , donc le moins d'octets gagne!

code-golf arithmetic decision-problem integer factorial Greg Martin
la source
"écrivez chaque nombre d'entrée comme la somme des factorielles (d'entiers positifs) de la manière la plus gourmande possible" ne voulez-vous pas dire la manière la plus paresseuse possible à la place?
user41805
4
@KritixiLithos no. Il fait référence à la classe d'algorithmes connus sous le nom d'algorithmes gourmands, qui fonctionnent en maximisant certaines mesures après chaque étape. Comme dans, en prenant toujours autant que possible.
John Dvorak

Réponses:

9

Gelée , 7 octets

Æ!ṠḄ&/¬

Essayez-le en ligne!

Comment ça fonctionne

Æ!ṠḄ&/¬  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
la source
Æ!semble incroyablement utile dans certains scénarios.
Magic Octopus Urn
Y a-t-il quelque chose à gagner en essayant de multiplier directement par élément les listes factorielles, sans prendre de signes?
Greg Martin
@GregMartin Je ne pense pas. Les tableaux de chiffres devraient être remplis ou tronqués à la même longueur, ce qui coûtera probablement plus d'octets qu'il n'en enregistre.
Dennis
3

Python 3 , 93 91 octets

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)

Essayez-le en ligne!

ovs
la source
3

Python 2 , 47 octets

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

Essayez-le en ligne!

xnor
la source
J'adore cette solution. Pourriez-vous l'annoter avec un peu de votre réflexion?
Chas Brown
2

JavaScript (ES6), 71 octets

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

Les entiers JavaScript sont limités à 53 bits de précision, ce qui est à peu près suffisant pour 18 !; cela signifie que je peux utiliser un masque de 18 bits pour suivre les factoriels nécessaires.

Neil
la source
2

PHP, 109 octets

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;

Essayez-le en ligne!

Jörg Hülsermann
la source
0

Mathematica, 73 octets

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

formulaire de saisie

[x1, x2]

J42161217
la source
Je reçois plusieurs erreurs en testant cela ...
Scott Milner
Tapez juste à la fin [x1, x2]
J42161217
Ah. Je saisissais une liste, au lieu de deux entiers séparés. Vous pouvez le jouer plus loin avec ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61](69 octets). Dans le codage ISO 8859-1, le ±est un octet.
Scott Milner
0

C, 122 119 octets

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

Qest la fonction principale. Il doit être invoqué avec exactement deux valeurs entières positives. Cela se termine avec un code de sortie de 0pour véridique et 1pour faux.

Bien que cela ne semble pas fonctionner sur TIO, cela fonctionne sur mon système avec le Homebrew fourni gcc 7.1.0.

Je n'ai pas joué au Cgolf depuis un bon moment, donc les conseils de golf sont très appréciés!

R. Kap
la source