Dobla, XOR y hazlo de nuevo

20

Definimos la función g como g (n) = n XOR (n * 2) para cualquier número entero n> 0 .

Dado x> 0 , encuentre el entero más pequeño y> 0 tal que g k (y) = x para algunos k> 0 .

Ejemplo

x = 549

549 = 483 XOR (483 * 2)     (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2)     (as binary:  111100011 =  10100001 XOR  101000010)

Lo que significa que g 2 (161) = 549 . No podemos ir más allá, ya que no hay n tal que g (n) = 161 . Entonces, la salida esperada para x = 549 es y = 161 .

Reglas

  • Se supone que no debe admitir entradas no válidas. Se garantiza que existe un par (y, k) para el valor de entrada x .
  • Este es el , por lo que gana la respuesta más corta en bytes.

Casos de prueba

     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
fuente
3
OEIS relacionado: A048274, que es la secuenciaa(n) = g(n)
Giuseppe

Respuestas:

5

Java 8, 68 57 53 52 bytes

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

-5 bytes gracias a @ OlivierGrégoire .

Pruébalo en línea.

Explicación:

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
fuente
1
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}(52 bytes). Lo siento ^^ '
Olivier Grégoire
@ OlivierGrégoire Aún más inteligente, ¡gracias!
Kevin Cruijssen
for(int i=0;n>i-=i+i^i^n?-1:n=i;);?
Titus
@Titus Me temo que eso no va a funcionar en Java (aunque he usado ese enfoque en mi respuesta iterativa de JavaScript ). En Java i+i^i^n?no es un booleano, por lo que ni siquiera se compilará. Además, n>i-=...necesitará paréntesis ( n>(i-=...)), y n=ino está permitido en la cláusula else del ternario if, solo en la cláusula if (esta última no sé por qué, pero desafortunadamente eso es lo que es en Java )
Kevin Cruijssen
1
@KevinCruijssen "y n=ino está permitido en la cláusula else del ternario si". Porque Java lo analizaría como (i-=(i*2^i)!=n?-1:n)=iilegal.
Olivier Grégoire
3

JavaScript, 53 bytes

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

Ges decir g^-1, que se establece ien 0caso de éxito, se establece ien 1si falla

tsh
fuente
1
Este fue el enfoque que trató de usar a pesar de que ocurrió una versión de 50 bytes: f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n. Lamentablemente, el enfoque aburrido es 12 bytes más corto.
Neil
3

Pyth , 13 12 10 bytes

Se guardó 1 byte gracias a @MrXcoder y 2 bytes más siguiendo su sugerencia

fqQ.W<HQxy

Pruébalo en línea

Explicación:

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
fuente
1
Puede soltar el final Tde 12 bytes.
Sr. Xcoder
3

R , 73 65 bytes

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

Pruébalo en línea!

Muchas gracias Giuseppe (-8) debido a tus ajustes, tan simple pero muy efectivo

DS_UNI
fuente
1
en contraposición a una respuesta anterior de la suya, ya que esta función es recursiva, que no necesita el f=ya que las necesidades de función para ser obligados a ftrabajar correctamente. Dicho esto, buen trabajo, ¡y toma un +1 de mí!
Giuseppe
2
También puede hacer un nuevo ajuste de su lógica y llevar esto a 65 bytes
Giuseppe
2

JavaScript 38 36 bytes

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

Pruébelo en línea : comienza a arrojar errores de desbordamiento en algún lugar entre 9999&57308 .

Lanudo
fuente
2

Jalea , 8 7 bytes

Úselo ⁺¿para devolver el último elemento distinto de cero (gracias Dennis por -1 byte)

^Ḥ)i$⁺¿

Pruébalo en línea!

La fuerza bruta gana de nuevo :(

usuario202729
fuente
1
^Ḥ)i$⁺¿Guarda un byte.
Dennis
Y es 2 veces más lento.
user202729
2

C (gcc) , 57 56 55 51 bytes

  • Guardado un byte gracias a ceilingcat ; !=- .
  • Guardado un byte de cinco bytes gracias a Rogem ; haciendo uso de la expresión ternaria y las peculiaridades de gcc.
X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}

Pruébalo en línea!

Jonathan Frech
fuente
1
+1 paraX(O,R)
JayCe
@ceilingcat Buena sugerencia, gracias.
Jonathan Frech
for(R=1;R;O=R?R:O)Guarda un byte.
R=O;al final parece ser innecesario, ahorrándote otros 4 bytes.
@Rogem parece ser, gracias.
Jonathan Frech
2

Z80Golf , 22 bytes

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

Puerto de la respuesta Java de @ KevinCruijssen

Ejemplo con entrada de 9-¡Pruébelo en línea!

Ejemplo con entrada de 85-¡Pruébelo en línea!

Montaje:

;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

Ejemplo de ensamblaje para llamar a la función e imprimir el resultado:

ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
Logern
fuente
Si realiza ael contador de bucle en lugar de d, puede reemplazar las ld d,0instrucciones en xor aambas ocasiones, lo que ahorra dos bytes.
Misha Lavrov
1

JavaScript (Node.js), 48 45 38 bytes

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

-7 bytes gracias a que @Neil creó una versión recursiva de mi versión iterativa a continuación. No funciona para casos de prueba grandes.

Pruébalo en línea.


Versión iterativa de 45 bytes que funciona para todos los casos de prueba:

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

Puerto de mi respuesta Java.
-3 bytes gracias a @Arnauld .

Pruébalo en línea.

Kevin Cruijssen
fuente
1
Puedes hacerlo i-=i*2^i^n?-1:n=i(pero desafortunadamente no en Java).
Arnauld
@Arnauld Supuse que algo era posible para el booleano en Java solo 1en JS. ¡Gracias!
Kevin Cruijssen
1
38 bytes escritos de forma recursiva (no funciona para entradas más grandes):f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Neil
1

Ruby , 39 bytes

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

Pruébalo en línea!

Como se esperaba para la versión recursiva, se queja de "nivel de pila demasiado profundo" en los últimos casos de prueba.

Kirill L.
fuente
1

Jalea , 11 9 bytes

BÄḂṛḄß$Ṫ?

Pruébalo en línea!

Consejos: utilice la función recursiva en lugar de bucles.


Muy rápido, lamentablemente pierde con el enfoque de fuerza bruta.

Tenga en cuenta que:

  • Para x> 0 , f (x)> x .
  • popcount (f (x)) es par, donde popcount (n) es el número de bits establecido en n .
  • Si n tiene incluso popcount, entonces existe x tal que f (x) = n .
  • Deje B (x) ser la representación binaria de x , y Ṗ (l) sea ​​la lista l con el último elemento eliminado. Entonces B (x) es el XOR acumulado de Ṗ (B (f (x))) .

Entonces, repetidamente:

  • Calcule su representación binaria ( B)
  • luego tome el XOR acumulado (use ^\o ÄḂ, tienen el mismo efecto).
  • Compruebe si ( ?) la cola (último elemento) ( ) del XOR acumulado es distinto de cero (cuenta pop impar)
    • Si es así, convierta la lista binaria de nuevo a decimal y recurse.
    • Si no, devuelve la entrada ( ).
usuario202729
fuente
9 bytes:B^\⁸Ḅß$Ṫ?
Leaky Nun
1

Adelante (gforth) , 71 bytes

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

Pruébalo en línea!

Explicación

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
fuente
1

Perl 6 , 44 bytes

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

Intentalo

Expandido:

{  # 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
fuente
1

PHP, 49 bytes

Basado en las respuestas de Kevin Cruijssen.

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

Ejecutar como tubería -nro probarlo en línea .

Titus
fuente
1

F #, 92 bytes

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

Pruébalo en línea!

Verifica recursivamente los números del 1 al i-1. Si hay una coincidencia, busque una más pequeña para ese número. Si no hay coincidencia, devuelva el número de entrada.

Ciaran_McCarthy
fuente
1

JavaScript (Node.js) , 40 bytes

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

Pruébalo en línea!

Gracias Shaggy por -1 bytes.

Respuesta de Port of my Jelly .

Finalmente, hay un lenguaje en el que este enfoque es más corto ( Uy ). (Probé Python y Java , no funciona)

¿Alguien puede explicar por qué puedo usar en /2lugar de >>1?

usuario202729
fuente
1
x/2funciona debido al flujo inferior aritmético. Cualquier número IEEE 754 eventualmente se evaluará como 0 cuando se divida entre 2 veces suficientes. (Y la parte decimal simplemente se ignora cuando se hace XOR, por lo que esto no afecta el resultado).
Arnauld
40 bytes
Shaggy
@Shaggy Sorprendido de que funcione. Sé que funciona para Python y Lua, etc., pero no para Javascript.
user202729
Lo falsedevuelto en la última iteración se convierte implícitamente en0 operador XOR bit a bit convierte .
Shaggy
@Shaggy De hecho, no falseestá involucrado . JS se &&comporta casi idénticamente a Python / Lua and.
user202729
1

K (ngn / k) , 32 26 bytes

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

Pruébalo en línea!

{ } es una función con argumento x

/ lo aplica hasta la convergencia

$[ ; ; ] si-entonces-otro

2\xdígitos binarios de x(esto es específico de ngn / k)

+\ sumas parciales

2! mod 2

a: asignar a a

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

si lo anterior es 1, xserá devuelto

de otra manera:

-1_a soltar el último elemento de a

2/ decodificar binario

ngn
fuente
0

C, 62 bytes

Basado en Java de Kevin Cruijssen:

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

Probar:

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

Cuando se ejecuta, el programa de prueba genera:

     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 bytes

Solo funciona con C89 o K&R C:

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

JustinCB
fuente
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}¿Funcionan estos 57 bytes?
Titus
0

Wolfram Language (Mathematica) , 58 bytes

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

Pruébalo en línea!

Comienza con una lista que contiene solo la entrada. Iterativamente reemplaza la lista por todos los enteros que ya están en ella, o se asignan a ella mediante la operación doble y xor. Luego //.dice hacer esto hasta llegar a un punto fijo. La respuesta es el elemento mínimo del resultado.

Misha Lavrov
fuente