Wyzwanie

Napisz funkcję lub program, który pobiera dodatnią liczbę dziesiętną, nazwij ją A i wyślij dwie liczby dodatnie, B i C , tak aby:

• A == B bitxor C.
• B i C nie mogą zawierać cyfr 0, 3 lub 7 w postaci dziesiętnej.

Przykłady

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

Ponieważ rozkład nie jest unikalny, twoja funkcja / program nie musi generować dokładnie takich samych wyników jak te podane przykłady.

Bardzo szczegółowe zasady

1. Zgłoszenia powinny mieć formę pełnej funkcji lub programu . importOświadczenia nie liczą się do punktacji końcowej.

2. Możesz założyć, że wejście A zawsze zawiera co najmniej cyfrę 0, 3 lub 7.

3. Możesz założyć, że rozkład zawsze istnieje.

4. Możesz użyć BigInt, jeśli są one częścią standardowych bibliotek języka lub można je zainstalować za pomocą języka menedżera pakietów de jure .

5. Funkcja powinna być szybka. Nie powinno to zająć więcej niżUruchomienie na rozsądnie nowoczesnym komputerze 20 sekund, jeśli zostanie podany numer 100-cyfrowy, i nie więcej niż 2 sekundy, gdy zostanie podany numer 10-cyfrowy.

6. Funkcja / program powinien obsługiwać dane wejściowe co najmniej 100 cyfr .

   • Jeśli funkcja / program obsługuje tylko liczby całkowite do N <100 cyfr, zostanie nałożona kara wysokości + 10 × (100 / N - 1) bajtów do wyniku końcowego. Ma to zachęcić golfistów do obsługi szerszego zakresu liczb, nawet jeśli import może być pełny.

7. Jest ma ograniczeń w prezentacji danych wejściowych / wyjściowych, o ile są one wyraźnie w postaci dziesiętnej.

   • Funkcja może wprowadzać i wyprowadzać ciągi znaków / BigInts, jeśli wbudowane typy liczb całkowitych nie są wystarczające.
   • Dane wejściowe mogą pochodzić z parametru funkcji, argumentu wiersza poleceń lub STDIN.
   • Funkcja może zwrócić wynik lub po prostu wydrukować wynik bezpośrednio do STDOUT.
   • Jednak podpisane przepełnienie wejść / wyjść jest niedozwolone.
   • Przybliżone odpowiedzi nie są tolerowane, dane wejściowe / wyjściowe muszą być dokładne.

Punktacja

To jest golf golfowy . Najkrótsze rozwiązanie w bajtach wygrywa.

Jeżeli program obsługuje tylko liczby mniejsze niż 100 cyfr, obowiązuje kara:

• 64-bitowe liczby całkowite (19 cyfr) = +42 bajty
• 63-bitowe liczby całkowite (18 cyfr) = +45 bajtów
• 53-bitowe liczby całkowite (15 cyfr) = +56 bajtów
• 31/32-bitowe liczby całkowite (9 cyfr) = +101 bajtów

CJam, 70 bajtów

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

Wypróbuj online.

Losowo wybiera liczby całkowite, aż znajdzie dopasowanie. To ledwo jest zgodne z 20-sekundowym limitem dla 64-bitowych liczb całkowitych (przy użyciu interpretera Java), więc dodałem 42 do rzeczywistej liczby bajtów.

Przykładowy przebieg

$ cjam t <<< 7777777777; echo
2695665494
6161166119

Common Lisp, 240 224 183 173 169 bajtów

Common Lisp jest nieco gadatliwy dla golfistów. Jednak rozkłada to 100 cyfr w mniej niż sekundę i 200 cyfr liczb całkowitych w mniej niż dziesięć sekund, więc nie trzeba kar. Algorytm jest deterministyczny.

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

Przesunięcie linii między funkcjami służy wyłącznie do celów typograficznych. Uruchomienie testowe ze 100-cyfrowym wejściem odniesienia:

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

Jako bonus dołączam wersję kodu, która stopniowo buduje rozwiązanie odgórne. Może zarządzać liczbą 1000 cyfr w mniej niż dziesięć sekund, ale nie może konkurować w golfie z powodu dodatkowego kodu.

(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 bajtów

Python natywnie obsługuje bigintery, ale ten program znacznie przekracza 20 sekund dla liczby 100-cyfrowej. Jednak rozkłada 64-bitowe liczby całkowite w około 2 sekundy.

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

(Ma to na celu stymulowanie lepszych rozwiązań. To moje rozwiązanie podczas rozwiązywania pierwotnego problemu w filmie 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)

Chociaż zachowanie bitowej xor w systemie dziesiętnym jest dość skomplikowane, istnieje jedna ważna obserwacja: modyfikacja niskich cyfr nie wpłynie na wysokie cyfry . Dlatego możemy pracować z góry na dół: staraj się, aby górne cyfry były wolne od 0, 3, 7, a następnie pracuj nad kolejną cyfrą, aż zostanie obliczona liczba całkowita. To pozwala nam działać w czasie liniowym, a następnie przetworzenie tysiąc-cyfrowej liczby może zakończyć się w ciągu 1 sekundy. (Rozwiązanie Common Lisp wykorzystuje również tę samą technikę, którą uważam).