Podwój, XOR i zrób to jeszcze raz

20

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 , 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
Arnauld
źródło
3
Powiązany OEIS: A048274, który jest sekwencjąa(n) = g(n)
Giuseppe

Odpowiedzi:

5

Java 8, 68 57 53 52 bajty

n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}

-5 bajtów dzięki @ OlivierGrégoire .

Wypróbuj online.

Wyjaśnienie:

n->{                 // Method with integer as both parameter and return-type
  for(int i=0;i<n;)  //  Loop `i` in the range (1,n)
    i-=(i*2^i)==n?   //   If `i*2` XOR-ed with `i` equals `n`
        n=i          //    Set `n` to `i`, and set `i` to 0 to reset the loop
       :             //   Else:
        -1;          //    Increase `i` by 1 to go to the next iteration
  return n;}         //  Return `n` after the entire loop
Kevin Cruijssen
źródło
1
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}(52 bajty). Przepraszam ^^ '
Olivier Grégoire,
@ OlivierGrégoire Jeszcze mądrzejszy, dzięki!
Kevin Cruijssen
for(int i=0;n>i-=i+i^i^n?-1:n=i;);?
Titus
@Titus Obawiam się, że to nie zadziała w Javie (chociaż zastosowałem to podejście w mojej iteracyjnej odpowiedzi JavaScript ). W Javie i+i^i^n?nie ma wartości logicznej, więc nawet się nie skompiluje. Ponadto n>i-=...będzie wymagał nawiasu ( n>(i-=...)) i n=inie 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 ).
Kevin Cruijssen
1
@KevinCruijssen "i n=inie jest dozwolony w klauzuli else z trójki-jeśli". Ponieważ Java parsuje to jako (i-=(i*2^i)!=n?-1:n)=inielegalne.
Olivier Grégoire,
3

JavaScript, 53 bajty

f=x=>(i=0,y=(G=x=>x&&(i^=x&1)+2*G(x>>1))(x),i?x:f(y))

Gto g^-1, która ustawiona ijest w 0przypadku sukcesu, ustawiona iw 1przypadku niepowodzenia.

tsh
źródło
1
Było to podejście próbowałem użytku choć wpadłem w wersji 50-bajtowy: 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.
Neil
3

Pyth , 13 12 10 bajtów

Zaoszczędzono 1 bajt dzięki @MrXcoder i 2 kolejne bajty po ich sugestii

fqQ.W<HQxy

Wypróbuj online

Wyjaśnienie:

fqQ.W<HQxyZZT   Implicit: Q=eval(input()), trailing ZZT inferred

f               Return the first T in [1,2,3...] where the following is truthy
   .W       T     Functional while - loop until condition is true, starting value T
     <HQ            Condition: continue while iteration value (H) less than input
        xyZZ        Body: xor iteration value (Z) with double (y) iteration value (Z)
 qQ               Is the result of the above equal to input?
Sok
źródło
1
Możesz upuścić końcowy Tdla 12 bajtów.
Pan Xcoder,
3

R , 73 65 bajtów

f=function(x){for(i in 1:x)if(x==bitwXor(i,i*2)){i=f(i);break};i}

Wypróbuj online!

Wielkie dzięki Giuseppe (-8) za twoje poprawki, tak proste, ale bardzo skuteczne

DS_UNI
źródło
1
w przeciwieństwie do poprzedniej odpowiedzi od Ciebie, ponieważ ta funkcja jest rekurencyjna, to nie potrzebne f=, ponieważ potrzeby funkcyjne na związanie się fdziałać prawidłowo. To powiedziawszy, dobra robota i weź ode mnie +1!
Giuseppe
2
możesz także zrobić kilka zmian w logice i uzyskać to do 65 bajtów
Giuseppe
2

JavaScript, 38 36 bajtów

f=(n,x=n)=>x?x^x+x^n?f(n,--x):f(x):n

Wypróbuj online - zaczyna generować błędy przepełnienia gdzieś pomiędzy 9999& 57308.

Kudłaty
źródło
2

Galaretka , 8 7 bajtów

Użyj, ⁺¿aby zwrócić ostatni niezerowy element (dzięki Dennis za -1 bajt)

^Ḥ)i$⁺¿

Wypróbuj online!

Brute force znów wygrywa :(

użytkownik202729
źródło
1
^Ḥ)i$⁺¿zapisuje bajt.
Dennis
I jest 2x wolniejszy.
user202729,
2

C (gcc) , 57 56 55 51 bajtów

  • Zapisano bajt dzięki pułapowi cat ; !=-.
  • Zaoszczędził bajt pięć bajtów dzięki Rogemowi ; wykorzystując wyrażenie potrójne i dziwactwa gcc.
X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}

Wypróbuj online!

Jonathan Frech
źródło
1
+1 zaX(O,R)
JayCe
@ceilingcat Dobra sugestia, dzięki.
Jonathan Frech,
for(R=1;R;O=R?R:O)zapisuje bajt.
R=O;na końcu wydaje się niepotrzebny, oszczędzając kolejne 4 bajty.
@Rogem Wygląda na to, dzięki.
Jonathan Frech,
2

Z80Golf , 22 bajty

00000000: 1600 1803 4216 007a b830 097a 82aa b828  ....B..z.0.z...(
00000010: f314 18f3 78c9                           ....x.

Port odpowiedzi Java @ KevinCruijssen

Przykład z wprowadzeniem 9-Wypróbuj online!

Przykład z wejściem 85-Wypróbuj online!

Montaż:

;d=loop counter
;b=input and output
f:
	ld d,0
	jr loop
	begin:
	ld b,d
	ld d,0
	loop:
		ld a,d
		cp b
		jr nc,end	; if d==b end
		ld a,d
		add d		; mul by 2
		xor d
		cp b
		jr z,begin	; if (d*2)^d==b set b to d
		inc d
		jr loop
	end:
	ld a,b
	ret

Przykład zestawu do wywołania funkcji i wydrukowania wyniku:

ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
Logern
źródło
Jeśli azamiast tego utworzysz licznik pętli d, możesz zastąpić ld d,0instrukcje xor aoba razy, co oszczędza dwa bajty.
Misha Lavrov
1

Java (JDK 10) , 78 bajtów

int g(int n){return f(n)%2<1?g(f(n)/2):n;}int f(int x){return 1>x?0:x^f(x/2);}

Wypróbuj online!

użytkownik202729
źródło
1

JavaScript (Node.js), 48 45 38 bajtów

f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n

-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:

n=>{for(i=0;i<n;)i-=i*2^i^n?-1:n=i;return n;}

Port mojej odpowiedzi Java.
-3 bajty dzięki @Arnauld .

Wypróbuj online.

Kevin Cruijssen
źródło
1
Możesz to zrobić i-=i*2^i^n?-1:n=i(ale niestety nie w Javie).
Arnauld
@Arnauld Stwierdził, że coś w języku boolean w Javie jest możliwe tylko 1w JS. Dzięki!
Kevin Cruijssen
1
38 bajtów zapisywanych rekurencyjnie (nie działa dla większych danych wejściowych):f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Neil
1

Rubin , 39 bajtów

f=->x,y=x{y<1?x:x==y^y*2?f[y]:f[x,y-1]}

Wypróbuj online!

Jak oczekiwano w przypadku wersji rekurencyjnej, narzeka na „zbyt wysoki poziom stosu” w tych ostatnich przypadkach testowych.

Kirill L.
źródło
1

Galaretka , 11 9 bajtów

BÄḂṛḄß$Ṫ?

Wypróbuj online!

Wskazówki: Użyj funkcji rekurencyjnej zamiast pętli.


Bardzo szybko, niestety przegrywa z podejściem brutalnej siły.

Uwaga:

  • Dla x> 0 , f (x)> x .
  • popcount (f (x)) jest parzyste, gdzie popcount (n) to liczba bitów ustawiona w n .
  • Jeśli n ma nawet liczbę pop, to istnieje x takie, że f (x) = n .
  • Niech B (x) będzie binarną reprezentacją x , a Ṗ (l) będzie listą l z usuniętym ostatnim elementem. Zatem B (x) jest zakumulowanym XOR z Ṗ (B (f (x))) .

Dlatego wielokrotnie:

  • Oblicz jego reprezentację binarną (B )
  • następnie weź zgromadzony XOR (użyj ^\lubÄḂ , mają ten sam efekt).
  • Sprawdź, czy ( ?) ogon (ostatni element) ( ) skumulowanego XOR jest niezerowy (liczba nieparzysta)
    • Jeśli tak, przekonwertuj listę binarną z powrotem na dziesiętną i powtórz.
    • Jeśli nie, zwraca input ( ).
użytkownik202729
źródło
9 bajtów:B^\⁸Ḅß$Ṫ?
Leaky Nun
1

Dalej (gforth) , 71 bajtów

: f 0 begin 2dup dup 2* xor = if nip 0 else 1+ then 2dup < until drop ;

Wypróbuj online!

Wyjaśnienie

0                 \ add an index variable to the top of the stack
begin             \ start an indefinite loop
  2dup            \ duplicate the top two stack items (n and i)
  dup 2* xor =    \ calculate i xor 2i and check if equal to n
  if nip 0        \ if equal, drop n (making i the new n) and use 0 as the new i
  else 1+         \ otherwise just increment i by 1
  then            \ end the if-statement
  2dup <          \ duplicate the top two stack items and check if n < i
until             \ if previous statement is true, end the loop
drop              \ drop i, leaving n on top of the stack
reffu
źródło
1

Perl 6 , 44 bajtów

{({first {($^a+^2*$a)==$_},^$_}...^!*).tail}

Spróbuj

Rozszerzony:

{  # bare block lambda with implicit parameter $_

  (
    # generate a sequence

    # no need to seed the sequence with $_, as the following block will
    # default to using the outer $_
    # $_, 

    { # parameter $_

      first
        {  # block with placeholder parameter $a

          ( $^a +^ 2 * $a ) # double (numeric) xor
          == $_             # is it equal to the previous value
        },

        ^$_  # Range up to and excluding the previous value ( 0..^$_ )
    }

    ...^  # keep doing that until: (and throw away last value)

    !*    # it doesn't return a trueish value

  ).tail  # return the last generated value
}
Brad Gilbert b2gills
źródło
1

PHP, 49 bajtów

Na podstawie odpowiedzi Kevina Cruijssena.

for($x=$argn;$x>$i-=$i*2^$i^$x?-1:$x=$i;);echo$x;

Uruchom jako potok z -nrlub spróbuj online .

Tytus
źródło
1

F #, 92 bajty

let rec o i=
 let r=Seq.tryFind(fun x->x^^^x*2=i){1..i-1}
 if r.IsNone then i else o r.Value

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.

Ciaran_McCarthy
źródło
1

JavaScript (Node.js) , 40 bajtów

f=n=>g(n)%2?n:f(g(n)/2)
g=x=>x&&x^g(x/2)

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ć /2zamiast >>1?

użytkownik202729
źródło
1
x/2dział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).
Arnauld
40 bajtów
Shaggy
@Shaggy Zaskoczony, że to działa. Wiem, że to działa dla Python i Lua itp., Ale nie Javascript.
user202729,
falsePowrócił na ostatniej iteracji jest niejawnie rzutować 0przez mnożenie operatora XOR.
Shaggy
@Shaggy W rzeczywistości nie falsejest zaangażowany . JS &&zachowuje się prawie identycznie jak Python / Lua and.
user202729,
1

K (ngn / k) , 32 26 bajtów

{$[*|a:2!+\2\x;x;2/-1_a]}/

Wypróbuj online!

{ } jest funkcją z argumentem x

/ stosuje to do momentu konwergencji

$[ ; ; ] jeśli-to-jeszcze

2\xbinarne cyfry x(jest to specyficzne dla ngn / k)

+\ sumy częściowe

2! mod 2

a: Przypisać do a

*|last - reverse ( |) i get first ( *)

jeśli powyższe wynosi 1, xzostanie zwrócone

Inaczej:

-1_a upuść ostatni element a

2/ dekodować binarnie

ngn
źródło
0

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ć:

#include <stdio.h>
int n(int j);
#define p(i) printf("%6d --> %5d\n", i, n(i))
int main(void)
{
    p(3);
    p(5);
    p(6);
    p(9);
    p(10);
    p(23);
    p(85);
    p(549);
    p(960);
    p(1023);
    p(1155);
    p(1542);
    p(9999);
    p(57308);
    p(57311);
    p(983055);
}

Po uruchomieniu program testowy generuje:

     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

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;}

JustinCB
ź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?
Tytus
0

Wolfram Language (Mathematica) , 58 bajtów

Min[{#}//.x_:>Select[Range@#,MemberQ[x,#|BitXor[#,2#]]&]]&

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.

Misza Ławrow
źródło