Desafio

Escreva uma função ou programa que aceite um número decimal positivo, chame-o de A e produza dois números positivos, B e C , de modo que:

• A == B bitxor C
• B e C não devem conter nenhum dos dígitos 0, 3 ou 7 em sua representação decimal.

Exemplos

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

Como a decomposição não é exclusiva, sua função / programa não precisa produzir exatamente os mesmos resultados que esses exemplos fornecidos.

Regras muito detalhadas

1. As submissões devem ser na forma de uma função ou programa completo . importdeclarações que contam para a pontuação final.

2. Você pode assumir que a entrada A sempre contém pelo menos um dígito de 0, 3 ou 7.

3. Você pode assumir que sempre existe uma decomposição.

4. Você pode usar o BigInt se eles fazem parte das bibliotecas padrão do idioma ou podem ser instalados através do gerenciador de pacotes de jure do idioma .

5. A função deve ser rápida. Não deve demorar mais de 20 segundos para ser executado em um computador razoavelmente moderno quando alimentado com um número de 100 dígitos e não mais que 2 segundos quando alimentado com um número de 10 dígitos.

6. A função / programa deve suportar entrada de pelo menos 100 dígitos .

   • Se a função / programa puder suportar apenas números inteiros até N <100 dígitos, haverá uma penalidade de + 10 × (100 / N - 1) bytes para a pontuação final. Isso serve para incentivar os golfistas a apoiar uma gama mais ampla de números, mesmo que a importação possa ser detalhada.

7. Não há restrições à apresentação de entradas / saídas, desde que elas estejam claramente na representação decimal.

   • A função pode inserir e enviar strings / BigInts se os tipos inteiros internos não forem suficientes.
   • A entrada pode vir do parâmetro da função, argumento da linha de comando ou STDIN.
   • A função pode retornar o resultado ou apenas imprimi-lo diretamente em STDOUT.
   • No entanto, o estouro assinado nas entradas / saídas não é permitido.
   • Respostas aproximadas não são toleradas, as entradas / saídas devem ser exatas.

Pontuação

Este é um código de golfe . A solução mais curta em bytes ganha.

Existe uma penalidade se o programa puder suportar apenas números com menos de 100 dígitos:

• Inteiros de 64 bits (19 dígitos) = +42 bytes
• Inteiros de 63 bits (18 dígitos) = +45 bytes
• Números inteiros de 53 bits (15 dígitos) = +56 bytes
• Inteiros de 31/32 bits (9 dígitos) = +101 bytes

CJam, 70 bytes

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

Experimente online.

Seleciona aleatoriamente números inteiros até encontrar uma correspondência. Isso mal cumpre o limite de 20 segundos para números inteiros de 64 bits (usando o interpretador Java), então adicionei 42 à contagem de bytes real.

Exemplo de execução

$ cjam t <<< 7777777777; echo
2695665494
6161166119

Lisp comum, 240 224 183 173 169 bytes

Lisp comum é um pouco detalhado para o golfe. No entanto, isso decompõe números de 100 dígitos em menos de um segundo e números inteiros de 200 dígitos em menos de dez segundos, portanto, não há necessidade de penalidades. O algoritmo é determinístico.

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

O avanço de linha entre as funções é apenas para fins tipográficos. Teste realizado com a entrada de referência de 100 dígitos:

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

Como bônus, incluo uma versão do código que constrói de maneira incremental a solução de cima para baixo. Ele pode gerenciar um número de 1000 dígitos em menos de dez segundos, mas não pode competir no golfe devido ao código adicional.

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

O Python suporta nativamente bigints, mas esse programa excede em muito 20 segundos um número de 100 dígitos. No entanto, decompõe números inteiros de 64 bits em cerca de 2 segundos.

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

(Isso é apenas para estimular melhores soluções. Essa é a minha solução ao resolver o problema original no filme 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)

Embora o comportamento do xor bit a bit no sistema decimal seja bastante complicado, há uma observação importante: modificar os dígitos baixos não afetará os dígitos altos . Portanto, podemos trabalhar de cima para baixo: tente liberar os dígitos superiores de 0, 3, 7 e, em seguida, trabalhe no próximo dígito, até que o número inteiro seja calculado. Isso nos permite executar em tempo linear, e o processamento de um número de mil dígitos pode ser concluído em menos de 1 segundo. (A solução Common Lisp também está usando a mesma técnica que eu acredito.)