Definiujemy funkcję g jako g (n) = n XOR (n * 2) dla dowolnej liczby całkowitej n> 0 .
Biorąc pod uwagę x> 0 , znajdź najmniejszą liczbę całkowitą y> 0 taką, że g k (y) = x dla niektórych k> 0 .
Przykład
x = 549
549 = 483 XOR (483 * 2) (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2) (as binary: 111100011 = 10100001 XOR 101000010)
Co oznacza, że g 2 (161) = 549 . Nie możemy iść dalej, ponieważ nie ma n takich, że g (n) = 161 . Oczekiwany wynik dla x = 549 to y = 161 .
Zasady
- Nie należy wspierać nieprawidłowych wpisów. Dla wartości wejściowej x gwarantowana jest para (y, k) .
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach!
Przypadki testowe
3 --> 1
5 --> 1
6 --> 2
9 --> 7
10 --> 2
23 --> 13
85 --> 1
549 --> 161
960 --> 64
1023 --> 341
1155 --> 213
1542 --> 2
9999 --> 2819
57308 --> 19124
57311 --> 223
983055 --> 1
a(n) = g(n)
Odpowiedzi:
Java 8,
68575352 bajty-5 bajtów dzięki @ OlivierGrégoire .
Wypróbuj online.
Wyjaśnienie:
źródło
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}
(52 bajty). Przepraszam ^^ 'for(int i=0;n>i-=i+i^i^n?-1:n=i;);
?i+i^i^n?
nie ma wartości logicznej, więc nawet się nie skompiluje. Ponadton>i-=...
będzie wymagał nawiasu (n>(i-=...)
) in=i
nie jest dozwolony w klauzuli else z trójki, jeśli tylko w klauzuli if (tej ostatniej nie wiem, dlaczego, ale niestety tak jest w Javie ).n=i
nie jest dozwolony w klauzuli else z trójki-jeśli". Ponieważ Java parsuje to jako(i-=(i*2^i)!=n?-1:n)=i
nielegalne.Python 2 ,
5453 bajtówWypróbuj online!
źródło
JavaScript, 53 bajty
G
tog^-1
, która ustawionai
jest w0
przypadku sukcesu, ustawionai
w1
przypadku niepowodzenia.źródło
f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n
. Niestety nudne podejście jest o 12 bajtów krótsze.Pyth ,
13 1210 bajtówZaoszczędzono 1 bajt dzięki @MrXcoder i 2 kolejne bajty po ich sugestii
Wypróbuj online
Wyjaśnienie:
źródło
T
dla 12 bajtów.R ,
7365 bajtówWypróbuj online!
Wielkie dzięki Giuseppe (-8) za twoje poprawki, tak proste, ale bardzo skuteczne
źródło
f=
, ponieważ potrzeby funkcyjne na związanie sięf
działać prawidłowo. To powiedziawszy, dobra robota i weź ode mnie +1!JavaScript,
3836 bajtówWypróbuj online - zaczyna generować błędy przepełnienia gdzieś pomiędzy
9999
&57308
.źródło
Galaretka ,
87 bajtówUżyj,
⁺¿
aby zwrócić ostatni niezerowy element (dzięki Dennis za -1 bajt)Wypróbuj online!
Brute force znów wygrywa :(
źródło
^Ḥ)i$⁺¿
zapisuje bajt.C (gcc) ,
57565551 bajtów!=
~-
.bajtpięć bajtów dzięki Rogemowi ; wykorzystując wyrażenie potrójne i dziwactwa gcc.Wypróbuj online!
źródło
X(O,R)
for(R=1;R;O=R?R:O)
zapisuje bajt.R=O;
na końcu wydaje się niepotrzebny, oszczędzając kolejne 4 bajty.Z80Golf , 22 bajty
Port odpowiedzi Java @ KevinCruijssen
Przykład z wprowadzeniem 9-Wypróbuj online!
Przykład z wejściem 85-Wypróbuj online!
Montaż:
Przykład zestawu do wywołania funkcji i wydrukowania wyniku:
źródło
a
zamiast tego utworzysz licznik pętlid
, możesz zastąpićld d,0
instrukcjexor a
oba razy, co oszczędza dwa bajty.Java (JDK 10) , 78 bajtów
Wypróbuj online!
źródło
JavaScript (Node.js),
484538 bajtów-7 bajtów dzięki @Neil utworząc poniżej rekurencyjną wersję mojej iteracyjnej wersji. Nie działa w przypadku dużych przypadków testowych.
Wypróbuj online.
Iteracyjna 45 bajtowa wersja, która działa dla wszystkich przypadków testowych:
Port mojej odpowiedzi Java.
-3 bajty dzięki @Arnauld .
Wypróbuj online.
źródło
i-=i*2^i^n?-1:n=i
(ale niestety nie w Javie).1
w JS. Dzięki!f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Rubin , 39 bajtów
Wypróbuj online!
Jak oczekiwano w przypadku wersji rekurencyjnej, narzeka na „zbyt wysoki poziom stosu” w tych ostatnich przypadkach testowych.
źródło
Galaretka ,
119 bajtówWypróbuj online!
Wskazówki: Użyj funkcji rekurencyjnej zamiast pętli.
Bardzo szybko, niestety przegrywa z podejściem brutalnej siły.
Uwaga:
Dlatego wielokrotnie:
B
)^\
lubÄḂ
, mają ten sam efekt).?
) ogon (ostatni element) (Ṫ
) skumulowanego XOR jest niezerowy (liczba nieparzysta)ṛ
).źródło
B^\⁸Ḅß$Ṫ?
Dalej (gforth) , 71 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Perl 6 , 44 bajtów
Spróbuj
Rozszerzony:
źródło
Prolog (SWI) , 44 bajty
Wypróbuj online!
źródło
PHP, 49 bajtów
Na podstawie odpowiedzi Kevina Cruijssena.
Uruchom jako potok z
-nr
lub spróbuj online .źródło
F #, 92 bajty
Wypróbuj online!
Rekurencyjnie sprawdza numery od 1 do
i-1
. Jeśli istnieje dopasowanie, sprawdź, czy dla tego numeru jest mniejszy. Jeśli nie ma dopasowania, zwróć numer wejściowy.źródło
JavaScript (Node.js) , 40 bajtów
Wypróbuj online!
Dzięki Shaggy za -1 bajtów.
Port mojej galaretki odpowiedzi .
Wreszcie istnieje język, w którym to podejście jest
krótsze( ups ). (Próbowałem Python i Java , to nie działa)Czy ktoś może wyjaśnić, dlaczego mogę użyć
/2
zamiast>>1
?źródło
x/2
działa z powodu niedomiaru arytmetycznego. Każdy numer IEEE 754 zostanie ostatecznie oceniony jako 0, gdy zostanie podzielony przez 2 wystarczającą liczbę razy. (Część dziesiętna jest po prostu ignorowana, gdy XOR'd, więc nie wpływa to na wynik).false
Powrócił na ostatniej iteracji jest niejawnie rzutować0
przez mnożenie operatora XOR.false
jest zaangażowany . JS&&
zachowuje się prawie identycznie jak Python / Luaand
.K (ngn / k) ,
3226 bajtówWypróbuj online!
{
}
jest funkcją z argumentemx
/
stosuje to do momentu konwergencji$[
;
;
]
jeśli-to-jeszcze2\x
binarne cyfryx
(jest to specyficzne dla ngn / k)+\
sumy częściowe2!
mod 2a:
Przypisać doa
*|
last - reverse (|
) i get first (*
)jeśli powyższe wynosi 1,
x
zostanie zwróconeInaczej:
-1_a
upuść ostatni elementa
2/
dekodować binarnieźródło
C, 62 bajty
Na podstawie Java Kevina Cruijssena:
int n(int j){for(int i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}
Testować:
Po uruchomieniu program testowy generuje:
C, 54 bajty
Działa tylko z C89 lub K&R C:
n(j){for(i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}
źródło
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}
Czy te 57 bajtów działa?Wolfram Language (Mathematica) , 58 bajtów
Wypróbuj online!
Zaczyna się od listy zawierającej tylko dane wejściowe. Iteracyjnie zamienia listę na wszystkie liczby całkowite, które już w niej są, lub odwzorowuje na nią operację podwójnego xor. Następnie
//.
mówi, aby to zrobić, aż do osiągnięcia stałego punktu. Odpowiedź jest najmniejszym elementem wyniku.źródło