Défi

Écrivez une fonction ou un programme qui prend un nombre décimal positif, appelez-le A et affichez deux nombres positifs, B et C , tels que:

• A == B bitxor C
• B et C ne doivent contenir aucun des chiffres 0, 3 ou 7 dans leur représentation décimale.

Exemples

>>> decompose(3)
1, 2
>>> decompose(7)
1, 6
>>> decompose(718)
121, 695
>>> decompose(99997)
2, 99999
>>> decompose(4294967296)
4294968218, 922
>>> decompose(5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376)
6291484486961499292662848846261496489294168969458648464915998254691295448225881546425551225669515922,
1191982455588299219648819556299554251659915414942295896926425126251962564256469862862114191986258666

Étant donné que la décomposition n'est pas unique, votre fonction / programme n'a pas besoin de produire exactement les mêmes résultats que ces exemples fournis.

Règles très détaillées

1. Les soumissions doivent prendre la forme d'une fonction ou d'un programme complet . importdéclarations ne comptent pour le score final.

2. Vous pouvez supposer que l'entrée A contient toujours au moins un chiffre de 0, 3 ou 7.

3. Vous pouvez supposer qu'une décomposition existe toujours.

4. Vous pouvez utiliser BigInt s'ils font partie des bibliothèques standard de la langue, ou peuvent être installés via le gestionnaire de packages de jure de la langue .

5. La fonction doit être rapide. Il ne devrait pas prendre plus de 20 secondes pour s'exécuter sur un ordinateur raisonnablement moderne lorsqu'il reçoit un numéro à 100 chiffres et pas plus de 2 secondes lorsqu'il est alimenté par un numéro à 10 chiffres.

6. La fonction / le programme doit prendre en charge la saisie d'au moins 100 chiffres .

   • Si la fonction / le programme ne peut prendre en charge que des nombres entiers jusqu'à N <100 chiffres, il y aura une pénalité de + 10 × (100 / N - 1) octets au score final. Il s'agit d'encourager les golfeurs à prendre en charge une plus large gamme de nombres même si l'importation peut être détaillée.

7. Il n'y a aucune restriction sur la présentation des entrées / sorties tant qu'elles sont clairement en représentation décimale.

   • La fonction peut entrer et sortir des chaînes / BigInts si les types entiers intégrés ne sont pas suffisants.
   • L'entrée peut provenir du paramètre de fonction, de l'argument de ligne de commande ou de STDIN.
   • La fonction peut renvoyer le résultat ou simplement imprimer le résultat directement dans STDOUT.
   • Cependant, un débordement signé dans les entrées / sorties n'est pas autorisé.
   • Les réponses approximatives ne sont pas tolérées, les entrées / sorties doivent être exactes.

Notation

Ceci est un code-golf . La solution la plus courte en octets gagne.

Il y a une pénalité si le programme ne peut prendre en charge que des nombres de moins de 100 chiffres:

• Entiers 64 bits (19 chiffres) = +42 octets
• Entiers 63 bits (18 chiffres) = +45 octets
• Entiers 53 bits (15 chiffres) = +56 octets
• Entiers 31/32 bits (9 chiffres) = +101 octets

CJam, 70 octets

ri:Q{;Qmr_Q^`1$`+730`&}g_Q^p

Essayez-le en ligne.

Sélectionne aléatoirement des entiers jusqu'à ce qu'il trouve une correspondance. Cela respecte à peine la limite de 20 secondes pour les entiers 64 bits (en utilisant l'interpréteur Java), j'ai donc ajouté 42 au nombre d'octets réel.

Exemple d'exécution

$ cjam t <<< 7777777777; echo
2695665494
6161166119

Common Lisp, 240 224 183 173 169 octets

Common Lisp est un peu bavard pour le golf. Cependant, cela décompose les nombres à 100 chiffres en moins d'une seconde et les nombres entiers à 200 chiffres en moins de dix secondes, donc pas besoin de pénalités. L'algorithme est déterministe.

(defun s(z)(and #1=(some(lambda(q)(position q(format()"~a"z)))"037")(+ z(floor z(expt 10 #1#)))))
(defun d(x)(do((y x(or(s y)(s #3=(logxor x y))(return`(,y,#3#)))))(())))

Le saut de ligne entre les fonctions est uniquement à des fins typographiques. Test avec l'entrée de référence à 100 chiffres:

(time (d 5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376))
took 677,000 microseconds (0.677000 seconds) to run.
      20,989 microseconds (0.020989 seconds, 3.10%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     671,875 microseconds (0.671875 seconds) were spent in user mode
           0 microseconds (0.000000 seconds) were spent in system mode
 54,221,104 bytes of memory allocated.
(1864921261592819619661568919418981552559955289196969112566252282429216186594265918444566258544614425
 5891958562486995519825158818455999516899524658151445485616155916296966645869599949958954491929662561)

En bonus, j'inclus une version du code qui construit progressivement la solution de haut en bas. Il peut gérer un nombre de 1000 chiffres en moins de dix secondes, mais ne peut pas participer au golf en raison du code supplémentaire.

(defun decompose (x)
  (flet ((s (z)
           (mapcan #'(lambda (c) (and #1=(position c #2=(format () "~a" z))
                                 (list (- (length #2#) #1# 1))))
                   '(#\0 #\3 #\7))))
    (do ((y x (let ((p (nconc (s y) (s #3=(logxor x y)))))
                (or p (return`(,y,#3#)))
                (+ y (expt 10 (apply #'max p))))))
        (nil))))

* (time (decompose (parse-integer (make-string 1000 :initial-element #\7))))
took 9,226,000 microseconds (9.226000 seconds) to run.
        90,966 microseconds (0.090966 seconds, 0.99%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     9,234,375 microseconds (9.234375 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 487,434,560 bytes of memory allocated.
(8889898889152488921298888992819221914229899249999918899888899888888889999989141219898898888988988898888888888899142442899924898918898898988988895189988898888924192198992454114198911989191888889898888918888988988998888891421118891899122898888998989898888898988898888999988918888898889189918889888888899888989219188898998888988892119889198888988888894888912188898989952999888888888898899998988898889228918998949999998898898991141888898999988912121292118899889998989899999892889941898888911888898889118998898888911889889888891452888998889288921141888888942189888899988891918889118888888888989892198899199914111188988889421111188889118888918989988912989999998989891119888898888888892621229888988888999619888952462219889189899998899888889989898891118989218888888898962988891188899888888888999888888888888888888888891269188921288888888998898899214191188888888898992188998898889919888889989889899988892115549998888898889218899988998911898989199918898918988898888891889888989119899888889888998918889112189998
 4184469818464841952189561886965821566229261221619858498284264289194458622668559698924621446851546256444641488616184155821914881485164244662156846141894655485889656891849662551896595944656451462198891289692696856414192264846811616261884188919426294584158925218559295881946496911489245664261126565546419851585441144861859822815144162828551969425529258169849412525611662488849586554989254181228254465226521648916188265491499166186964881248156451994924294646681548996645996894665198811511522424996844864211629888924642289925565591484541149414914699289441561496451494562955652129199261462268846144518142486845251946444998812988291119592418684842524648484689261441456645518518812265495165189812912919529151991611962525419626921619824496626511954895189658691229655648659252448158451924925658586522262194585891859285841914968868466462442488528641466655911199816288496111884591648442984864269495264612518852292965985888414945855422266658614684922884216851481646226111486498155591649619266595911992489425412191)
* (apply #'logxor *)
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

Python 2, 103 + 42 = 145 octets

Python prend en charge nativement les bigints, mais ce programme dépasse de loin 20 secondes pour un nombre à 100 chiffres. Cependant, il décompose les entiers 64 bits en environ 2 secondes.

from random import *
def d(a):
 b=c=0
 while set(`b`+`c`)&set('037'):
    b=randint(1,a);c=a^b
 return b,c

Python 3 (132 octets)

(C'est juste pour stimuler de meilleures solutions. C'est ma solution pour résoudre le problème d'origine dans un film ASCII.)

def d(a):
 l=len(str(a));s=int('1'*l);u=10**(l-1)
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u
  u//=10
 print(s,a^s)

Bien que le comportement de xor au niveau du bit dans le système décimal soit assez compliqué, il y a une observation majeure: la modification des chiffres bas n'affectera pas les chiffres hauts . Par conséquent, nous pouvons travailler de haut en bas: essayez de libérer les chiffres supérieurs de 0, 3, 7, puis travaillez sur le chiffre suivant, jusqu'à ce que le nombre entier soit calculé. Cela nous permet de fonctionner en temps linéaire, puis le traitement d'un nombre à mille chiffres peut se terminer en moins d'une seconde. (La solution Common Lisp utilise également la même technique, je crois.)