Alternar algunos bits y obtener un cuadrado

26

Dado un número entero , debe encontrar el número mínimo de bits que deben invertirse en para convertirlo en un número cuadrado . Solo puede invertir bits por debajo del más significativo .norte>3norte

Ejemplos

  • norte=4 4 ya es un número cuadrado ( 22 ), por lo que la salida esperada es 0 0 .
  • norte=24 se puede convertir en un número cuadrado invirtiendo 1 bit: 1100011001 ( 25=5 52 ), por lo que la salida esperada es 1 .
  • norte=22 no se puede convertir en un número cuadrado invirtiendo un solo bit (los posibles resultados son , , y ) pero se puede hacer invirtiendo 2 bits: ( ), por lo que la salida esperada es .232018 años3010110100 00 00 0dieciséis=4 422

Reglas

  • Está bien si su código es demasiado lento o arroja un error para los casos de prueba más grandes, pero al menos debería admitir en menos de 1 minuto.3<norte<10000
  • Este es el !

Casos de prueba

    Input | Output
----------+--------
        4 | 0
       22 | 2
       24 | 1
       30 | 3
       94 | 4
      831 | 5
      832 | 1
     1055 | 4
     6495 | 6
     9999 | 4
    40063 | 6
   247614 | 7        (smallest N for which the answer is 7)
  1049310 | 7        (clear them all!)
  7361278 | 8        (smallest N for which the answer is 8)
100048606 | 8        (a bigger "8")

O en formato amigable copiar / pegar:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
Arnauld
fuente
Casi la mitad de las respuestas no se ejecutan 100048606en TIO, ¿es eso un problema?
Urna mágica del pulpo
@MagicOctopusUrn Gracias, he actualizado las reglas para aclarar que admitir es opcional. norte10000
Arnauld
1
Esta también sería una buena pregunta de código más rápido (sin la restricción de tamaño de entrada)
qwr
@qwr Sí, probablemente. O si quieres ir al hardcore: dado , encuentra el N más pequeño de modo que f ( N ) = k . kNf(N)=k
Arnauld

Respuestas:

14

Ruby, 74 bytes

->n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size>Math.log2(n)?n:a.count(?1)}.min}

Pruébalo en línea!

Esto simplemente genera la secuencia (que es mucho más que suficiente), lo XOR con n , y luego toma el número de 1s en su representación binaria si el número de bits es menor que o igual a log 2 n , o n de lo contrario. Luego toma la cantidad mínima de bits invertidos. Devolver n en lugar del número de bits volteados cuando el bit más alto volteado es mayor que log 2 n evita que estos casos se elijan como mínimo, ya que n[12,22,...,norte2]norteIniciar sesión2nortenortenorteIniciar sesión2nortenorte siempre será mayor que la cantidad de bits que tiene.

Gracias a Piccolo por guardar un byte.

Pomo de la puerta
fuente
Puede guardar un byte usando en (n^x*x).to_s 2;...lugar de(n^x*x).to_s(2);...
Piccolo
@ Piccolo No puedo creer que me haya perdido eso, ¡gracias!
Pomo de la puerta
6

Jalea , 12 bytes

²,BẈEðƇ²^B§Ṃ

Pruébalo en línea!

¡Mira un paquete de prueba!

Enlace monádico. Debería ser golfable. Pero soy demasiado tonto para pensar en una forma de deshacerme del ³s. Es mi primera respuesta en la que utilizo con éxito el filtrado / mapeo / bucle en general junto con una cadena diádica \ o /

Explicación

², BẈEðƇ² ^ B§Ṃ - Programa completo / Enlace monádico. Llame al argumento N.
     ðƇ - Mantener filtro [1 ... N] con la siguiente cadena diádica:
², BẈE: el cuadrado del elemento actual tiene la misma longitud de bits que N.
² - Cuadrado.
 , - Emparejar con N.
  B - Convierte ambos a binario.
   Ẉ - Recuperar sus longitudes.
    E - Y verifique si equivalen.
       ² ^ - Después de filtrar, cuadra los resultados y XOR con N.
         B - Representación binaria de cada uno.
          § - Suma de cada uno. Cuenta el número de 1s en binario.
           Ṃ - Mínimo
Sr. Xcoder
fuente
5

Casco , 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

Pruébalo en línea!

Explicación

▼mΣf(¬→)S↑(M(¤ż≠↔ḋ)İ□ḋ) -- example input n=4
        S↑(           ) -- take n from n applied to (..)
                     ḋ  -- | convert to binary: [1,0,0]
                   İ□   -- | squares: [1,4,9,16,...]
           M(     )     -- | map with argument ([1,0,0]; example with 1)
                 ḋ      -- | | convert to binary: [1]
             ¤  ↔       -- | | reverse both arguments of: [1] [0,0,1]
              ż≠        -- | | | zip with inequality (absolute difference) keeping longer elements: [1,0,1]
                        -- | : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1],[1,0,1,1,1],....
                        -- : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1]]
    f(  )               -- filter elements where
       →                -- | last element
      ¬                 -- | is zero
                        -- : [[0,0,0]]
 mΣ                     -- sum each: [0]
▼                       -- minimum: 0
ბიმო
fuente
▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2Lḋahorra 2 bytes. RIP tu puntaje cuadrado perfecto.
Sr. Xcoder
@ Mr.Xcoder: lástima el puntaje ... Pero me deshice de un poco más, ahora apuntando a 16; P
ბიმო
5

Perl 6 , 65 bytes

{min map {+$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/\./},^2**.msb}

Pruébalo en línea!

Me siento un poco sucio por probar un cuadrado perfecto al buscar un punto en la representación de cadena de la raíz cuadrada del número, pero ... cualquier cosa para eliminar bytes.

Sean
fuente
4

05AB1E , 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes gracias a @ Mr.Xcoder usando un puerto de su respuesta Jelly .

Pruébelo en línea o verifique todos los casos de prueba (los tres casos de prueba más grandes se eliminan porque caducan después de 60 segundos; todavía toma alrededor de 35-45 segundos con los otros casos de prueba).

Explicación:

L            # Create a list in the range [1, input]
             #  i.e. 22 → [0,1,2,...,20,21,22]
 n           # Take the square of each
             #  i.e. [0,1,2,...,20,21,22] → [0,1,4,...,400,441,484]
  ʒ     }    # Filter this list by:
   ,         #  Pair the current value with the input
             #   i.e. 0 and 22 → [0,22]
             #   i.e. 25 and 22 → [25,22]
    b        #  Convert both to binary strings
             #   i.e. [0,22] → ['0','10110']
             #   i.e. [25,22] →  ['10000','11001']
     g      #  Take the length of both
             #   i.e. ['0','10110'] → [1,5]
             #   ['10000','11001'] → [5,5]
       Ë     #  Check if both are equal
             #   i.e. [1,5] → 0 (falsey)
             #   i.e. [5,5] → 1 (truthy)
^            # After we've filtered, Bitwise-XOR each with the input
             #  i.e. [16,25] and 22 → [6,15]
 b           # Convert each to a binary string again
             #  i.e. [6,15] → ['110','1111']
  S         # Change the binary strings to a list of digits
             #  i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
    O        # Take the sum of each
             #  i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß            # And then take the lowest value in the list
             #  i.e. [2,4] → 2
Kevin Cruijssen
fuente
1
Está bien, entonces, una validez de 15 byter: Lnʒ‚b€gË}^b€SOß. Desafortunadamente, rompe su suite de pruebas
Sr. Xcoder
1
@ Mr.Xcoder Gracias! Y mi suite de pruebas casi siempre se rompe después de jugar al golf ... XD Pero ahora también está arreglado.
Kevin Cruijssen
Supongo que no soy bueno escribiendo conjuntos de pruebas en 05AB1E ¯ \ _ (ツ) _ / ¯, es bueno que lo hayas solucionado :)
Sr. Xcoder
3

Java (JDK 10) , 110 bytes

n->{int i=1,s=1,b,m=99,h=n.highestOneBit(n);for(;s<h*2;s=++i*i)m=(s^n)<h&&(b=n.bitCount(s^n))<m?b:m;return m;}

Pruébalo en línea!

Olivier Grégoire
fuente
1
Puede guardar 1 byte utilizando bitwise y en &lugar de lógico y&&
kirbyquerby
3

Gaia , 18 bytes

Cerca del puerto de mi respuesta Jelly .

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

Pruébalo en línea!

Descompostura

s¦⟪, b¦l¦y⟫⁇ ⟪^ bΣ⟫¦⌋ - Programa completo. Llamemos a la entrada N.
s¦ - Cuadra cada número entero en el rango [1 ... N].
  ⟪⟫⁇ - Seleccione aquellos que cumplan una determinada condición, cuando se ejecuta
                     Un bloque diádico. El uso de un bloque diádico ahorra un byte porque el
                     input, N, se usa implícitamente como otro argumento.
   , - Empareja el elemento actual y N en una lista.
    b¦ - Convertirlos a binario.
      l¦ - Obtenga sus longitudes.
        y - Luego verifique si son iguales.
           ⟪⟫¦ - Ejecuta todos los enteros válidos a través de un bloque diádico.
            ^ - XOR cada uno con N.
             bΣ - Convierte a binario y suma (cuenta los 1s en binario)
                 ⌋ - Mínimo
Sr. Xcoder
fuente
2

Brachylog , 56 41 bytes

No va a romper ningún récord de longitud, pero pensé que lo publicaría de todos modos

⟨⟨{⟦^₂ᵐḃᵐ}{h∋Q.l~t?∧}ᶠ{ḃl}⟩zḃᶠ⟩{z{∋≠}ᶜ}ᵐ⌋

Pruébalo en línea!

Kroppeb
fuente
Acabo de darme cuenta de que comprimir es una cosa. Lo
acortaré
1
@Arnauld Sí, el problema principal era que para cada i en rango (0, n + 1) recalculé el rango, lo cuadré y lo binario. Poner esto afuera recuperó algunos bytes más, pero ahora es mucho más rápido
Kroppeb
2

Ensamblado x86-64, 37 bytes

Bytecode:

53 89 fb 89 f9 0f bd f7 89 c8 f7 e0 70 12 0f bd
d0 39 f2 75 0b 31 f8 f3 0f b8 c0 39 d8 0f 42 d8
e2 e6 93 5b c3

Muy bien, esto calcula incluso el ejemplo más alto en menos de un segundo.

El corazón del algoritmo es xor / popcount como de costumbre.

    push %rbx
    /* we use ebx as our global accumulator, to see what the lowest bit
     * difference is */
    /* it needs to be initialized to something big enough, fortunately the
     * answer will always be less than the initial argument */
    mov %edi,%ebx
    mov %edi,%ecx
    bsr %edi,%esi
.L1:
    mov %ecx,%eax
    mul %eax
    jo cont     /* this square doesn't even fit into eax */
    bsr %eax,%edx
    cmp %esi,%edx
    jnz cont    /* can't invert bits higher than esi */
    xor %edi,%eax
    popcnt %eax,%eax
    cmp %ebx,%eax   /* if eax < ebx */
    cmovb %eax,%ebx
cont:
    loop .L1
    xchg %ebx,%eax
    pop %rbx
    retq
ObsequiousNewt
fuente
Sugiera reemplazar al menos uno de sus movxchg
correos electrónicos
Por lo que puedo decir, solo hay uno que salvaría un byte ( mov %ecx,%eax) y no puedo dejar que% ecx muera allí.
ObsequiousNewt
1

Carbón , 31 bytes

NθI⌊EΦEθ↨×ιι²⁼LιL↨θ²ΣE↨責⁼λ§ιμ

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Nθ                              Input N
       θ                        N
      E                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              L L               Length
             ⁼                  Equals
    E                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     E          Map over digits
                           λ    Current base 2 digit of N
                             ι  Current base 2 value
                              μ Inner index
                            §   Get digit of value
                          ⁼     Equals
                         ¬      Not (i.e. XOR)
                    Σ           Take the sum
   ⌊                            Take the minimum
  I                             Cast to string
                                Implicitly print
Neil
fuente
1

C (gcc) ,  93  91 bytes

g(n){n=n?n%2+g(n/2):0;}m;i;d;f(n){m=99;for(i=0;++i*i<2*n;m=g(d=i*i^n)<m&d<n/2?g(d):m);n=m;}

Pruébalo en línea!


Editar: creo que mi solución original (¡ Pruébelo en línea! ) No es válida, porque una de las variables m, global para guardar algunos bytes al no especificar el tipo, se inicializó fuera de f(n)y, por lo tanto, tuvo que reinicializarse entre llamadas


Código sin comentarios y comentado:

g(n){n=n?n%2+g(n/2):0;} // returns the number of bits equal to 1 in n
m; //miminum hamming distance between n and a square
i; //counter to browse squares
d; //bitwise difference between n and a square
f(n){m=99; //initialize m to 99 > size of int (in bits)
    for(
        i=0;
        ++i*i<2*n; //get the next square number, stop if it's greater than 2*n
        g(d=i*i^n)<m&&d<n/2&&(m=g(d)) //calculate d and hamming distance
//      ^~~~~~~~~~~^ if the hamming distance is less than the minimum
//                    ^~~~^ and the most significant bit of n did not change (the most significant bit contains at least half the value)
//                           ^~~~~~~^ then update m
       );
    n=m;} // output m

Ediciones:

  • Guardado 2 bytes gracias a ceilingcat
Annyo
fuente