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
Zgłoszenia powinny mieć formę pełnej funkcji lub programu .
import
Oświadczenia nie liczą się do punktacji końcowej.Możesz założyć, że wejście A zawsze zawiera co najmniej cyfrę 0, 3 lub 7.
Możesz założyć, że rozkład zawsze istnieje.
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 .
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.
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.
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
Odpowiedzi:
CJam, 70 bajtów
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
źródło
Common Lisp,
240224183173169 bajtówCommon 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.
Przesunięcie linii między funkcjami służy wyłącznie do celów typograficznych. Uruchomienie testowe ze 100-cyfrowym wejściem odniesienia:
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.
źródło
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.
źródło
while
pętli, aby próbować losowych wartości - możesz po prostu wywołać tę funkcję ponownie. Bez konieczności struktury sterowania można następnie zwinąć funkcji wlambda
i potrójny:from random import* d=lambda a,b=0:set(`b`+`a^b`)&set(\'037\')and d(a,randint(1,a))or(b,a^b)
. Chociaż lepiej byłoby po prostu nie używać funkcji.Python 3 (132 bajty)
(Ma to na celu stymulowanie lepszych rozwiązań. To moje rozwiązanie podczas rozwiązywania pierwotnego problemu w filmie ASCII.)
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).
źródło
997^8 == 1005
. Myślę, że istnieje tutaj jądro pomysłu, ale nie jest to oczywiste.{1,2,4,5,6,8,9}
, byłyby takie, które nie wpłyną na wysokie cyfry. (np997^2 == 999
.). Wewnętrznawhile
pętla wyczerpuje się, aby znaleźć wybór, który zachowa ważność wysokich cyfr.