Herausforderung

Schreiben Sie eine Funktion oder ein Programm mit einer positiven Dezimalzahl, nennen Sie es A und geben Sie zwei positive Zahlen, B und C , aus, so dass:

• A == B bitxor C
• B und C dürfen in ihrer Dezimaldarstellung keine der Ziffern 0, 3 oder 7 enthalten.

Beispiele

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

Da die Zerlegung nicht eindeutig ist, muss Ihre Funktion / Ihr Programm nicht genau die gleichen Ergebnisse ausgeben wie diese Beispiele.

Sehr detaillierte Regeln

1. Die Einreichung sollte in Form einer vollständigen Funktion oder eines vollständigen Programms erfolgen . importAussagen noch auf die Endnote zählen.

2. Sie können davon ausgehen, dass der Eingang A immer mindestens eine Ziffer von 0, 3 oder 7 enthält.

3. Sie können davon ausgehen, dass eine Zerlegung immer existiert.

4. Sie können BigInt verwenden, wenn sie Teil der Standardbibliotheken der Sprache sind oder über den De-Jure- Paketmanager der Sprache installiert werden können .

5. Die Funktion sollte schnell sein. Es sollte nicht länger als 20 Sekunden dauern , um auf einem einigermaßen modernen Computer ausgeführt zu werden, wenn eine 100-stellige Zahl eingegeben wird, und nicht länger als 2 Sekunden, wenn eine 10-stellige Zahl eingegeben wird.

6. Die Funktion / das Programm sollte die Eingabe von mindestens 100 Stellen unterstützen .

   • Wenn die Funktion / das Programm nur Ganzzahlen mit bis zu N <100 Stellen unterstützt, wird der Endpunktzahl eine Strafe von + 10 × (100 / N - 1) Bytes auferlegt. Dies soll Golfer ermutigen, einen größeren Zahlenbereich zu unterstützen, auch wenn der Import ausführlich ist.

7. Die Darstellung von Ein- / Ausgängen unterliegt keiner Einschränkung, solange sie eindeutig dezimal dargestellt werden.

   • Die Funktion kann Strings / BigInts ein- und ausgeben, wenn die integrierten Integer-Typen nicht ausreichen.
   • Die Eingabe kann vom Funktionsparameter, Befehlszeilenargument oder STDIN stammen.
   • Die Funktion kann das Ergebnis zurückgeben oder das Ergebnis direkt an STDOUT ausgeben.
   • Ein vorzeichenbehafteter Überlauf in den Ein- / Ausgängen ist jedoch nicht zulässig.
   • Ungefähre Antworten werden nicht toleriert, die Ein- / Ausgaben müssen genau sein.

Wertung

Dies ist ein Code-Golf . Kürzeste Lösung in Bytes gewinnen.

Es gibt eine Strafe, wenn das Programm nur Nummern mit weniger als 100 Stellen unterstützt:

• 64-Bit-Ganzzahlen (19 Stellen) = +42 Byte
• 63-Bit-Ganzzahlen (18 Stellen) = +45 Bytes
• 53-Bit-Ganzzahlen (15 Stellen) = +56 Byte
• 31/32-Bit-Ganzzahlen (9 Stellen) = +101 Byte

CJam, 70 Bytes

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

Probieren Sie es online aus.

Wählt nach dem Zufallsprinzip ganze Zahlen aus, bis eine Übereinstimmung gefunden wird. Dies entspricht kaum der Beschränkung von 20 Sekunden für 64-Bit-Ganzzahlen (unter Verwendung des Java-Interpreters), daher habe ich der tatsächlichen Byteanzahl 42 hinzugefügt.

Beispiellauf

$ cjam t <<< 7777777777; echo
2695665494
6161166119

Common Lisp, 240 224 183 173 169 Bytes

Common Lisp ist ein bisschen wortreich zum Golfen. Dadurch werden jedoch 100-stellige Zahlen in weniger als einer Sekunde und 200-stellige Ganzzahlen in weniger als zehn Sekunden zerlegt, sodass keine Strafen erforderlich sind. Der Algorithmus ist deterministisch.

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

Der Zeilenvorschub zwischen den Funktionen dient nur typografischen Zwecken. Testlauf mit der 100-stelligen Referenzeingabe:

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

Als Bonus füge ich eine Version des Codes hinzu, mit der die Lösung schrittweise von oben nach unten erstellt wird. Es kann eine 1000-stellige Zahl in weniger als zehn Sekunden verwalten, kann aber aufgrund des zusätzlichen Codes nicht im Golfsport mithalten.

(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

Python unterstützt Bigints von Haus aus, aber dieses Programm überschreitet 20 Sekunden für eine 100-stellige Zahl bei weitem. Es zerlegt jedoch 64-Bit-Ganzzahlen in etwa 2 Sekunden.

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)

(Dies ist nur zur Anregung besserer Lösungen. Dies ist meine Lösung beim Lösen des ursprünglichen Problems in ASCII-Filmen.)

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)

Obwohl das Verhalten von bitweisem xor im Dezimalsystem ziemlich kompliziert ist, gibt es eine wichtige Beobachtung: Das Ändern der niedrigen Stellen hat keine Auswirkungen auf die hohen Stellen . Daher können wir von oben nach unten arbeiten: Versuchen Sie, die oberen Ziffern von 0, 3, 7 freizumachen, und arbeiten Sie dann an der nächsten Ziffer, bis die ganze Zahl berechnet ist. Dies ermöglicht es uns, in linearer Zeit zu arbeiten. Die Verarbeitung einer tausendstelligen Zahl kann dann in weniger als 1 Sekunde abgeschlossen sein. (Die Common Lisp-Lösung verwendet auch die gleiche Technik, die ich glaube.)