Encuentre el siguiente número binario escaso 1

27

Un entero positivo N es K- disperso si hay al menos K 0 entre dos 1 consecutivos en su representación binaria.

Entonces, el número 1010101 es 1 escaso mientras que 101101 no lo es.

Su tarea es encontrar el siguiente número 1 disperso para el número de entrada dado. Por ejemplo, si la entrada es 12 ( 0b1100), la salida debería ser 16 ( 0b10000) y si la entrada es 18 ( 0b10010), la salida debería ser 20 ( 0b10100).

¡El programa o función más pequeño (en bytes) gana! Lagunas estándar no permitidas.

articuno
fuente
¿"Siguiente" como en "siguiente más alto" o como "con la menor diferencia absoluta"?
FUZxxl
"siguiente" como en "siguiente más alto".
articuno
¿Qué rango de entrada necesita ser manejado?
mbomb007
Asumiré que los números negativos no necesitan serlo.
mbomb007
@articuno ¿Podemos crear una función o tiene que ser un programa completo? Las funciones son bastante estándar.
mbomb007

Respuestas:

13

Pyth, 9 bytes

Mi primer intento en Pyth:

f!.&TyThQ

Pruébalo aquí

               implicit: Q = input()            
f      hQ      find the first integer T >= Q + 1, 
               that satisfies the condition:
 !.&TyT        T & (T * 2) is 0
Trauma digital
fuente
9

CJam, 14 11 bytes

3 bytes guardados gracias a DigitalTrauma.

l~{)___+&}g

Pruébalo aquí.

Explicación

l~          "Read and eval input.";
  {      }g "Do while...";
   )_       "Increment and duplicate (call this x).";
     __+    "Get two more copies and add them to get x and 2x on the stack.";
        &   "Take their bitwise AND. This is non-zero is as long as x's base-2
             representation contains '11'.";

Esto deja el último número en la pila que se imprime automáticamente al final del programa.

Martin Ender
fuente
8

Python 2, 44 bytes

Este es un programa completo de Python que lee en n e imprime la respuesta. Creo que le va bastante bien en la subcompetencia de legibilidad.

n=input()+1
while'11'in bin(n):n+=1
print n

Los resultados de la prueba:

$ echo 12 | python soln.py 
16
$ echo 18 | python soln.py 
20
Caballero Lógico
fuente
6

Pyth, 12 11 bytes

f!}`11.BThQ

Pruébelo en línea: Pyth Compiler / Executor .

               implicit: Q = input()            
f        hQ    find the first integer T >= Q + 1, 
               that satisfies the condition:
 !}`11.BT         "11" is not in the binary representation of T
Jakube
fuente
1
Puedes guardar un personaje convirtiéndote "11"en `11.
orlp
@orlp Gracias, debería haber notado esto.
Jakube
5

Mathematica, 41 30 bytes

Guardado 11 bytes gracias a Martin Büttner.

#+1//.i_/;BitAnd[i,2i]>0:>i+1&
alephalpha
fuente
3
¿Podría agregar una descripción, por favor?
mbomb007
4

Perl, 31

#!perl -p
sprintf("%b",++$_)=~/11/&&redo

O desde la línea de comando:

 perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"
nutki
fuente
4

APL, 18 bytes

1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}

Esto se evalúa como una función monádica. Pruébalo aquí Uso:

   1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16

Explicación

1∘+                    ⍝ Increment the input ⍺
   ⍣{            }     ⍝ until
     ~∨/               ⍝ none of
        2∧/            ⍝ the adjacent coordinates contain 1 1 in
           ⍺⊤⍨⍺⍴2      ⍝ the length-⍺ binary representation of ⍺.
Zgarb
fuente
4

J, 20 caracteres

Un verbo monádico. Arreglado para obedecer las reglas.

(+1 1+./@E.#:)^:_@>:

Explicación

Primero, este es el verbo con espacios y luego un poco menos golfizado:

(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:

Leer:

    ]                             The argument
      +                           plus
        [: +./                    the or-reduction of
               1 1 E.             the 1 1 interval membership in
                      #:          the base-2 representation of the argument,
[: (                    )^:_      that to the power limit of
                             >:   the incremented argument

El argumento más la reducción o de la 1 1pertenencia al intervalo en la representación de base 2 del argumento, que se aplica al límite de potencia al argumento incrementado.

Básicamente calculo si 1 1ocurre en la representación de base 2 de la entrada. Si lo hace, incremente la entrada. Esto se pone bajo un límite de potencia, lo que significa que se aplica hasta que el resultado ya no cambie.

FUZxxl
fuente
Buen algoritmo! Tiene la misma longitud en la LPA: {⍵+∨/2∧/⍵⊤⍨⍵⍴2}⍣=.
Zgarb
@randomra Ah, ya veo.
FUZxxl
4

Javascript, 25 19

Usando el hecho de que, para un número binario escaso 1 x&2*x == 0:

f=x=>x++&2*x?f(x):x
Mella
fuente
3

JavaScript (ES6), 39 43

Sin expresiones regulares, sin cadenas, recursivo:

R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n

Versión iterativa:

F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}

Es muy simple, solo usa el desplazamiento a la derecha para encontrar una secuencia de 11. Cuando la encuentre, salte al siguiente número. La versión recursiva se deriva directamente de la iterativa.

Sin espíritu y más obvio. Para jugar al golf, la parte más complicada es fusionar los bucles interno y externo (tener que iniciar x a 3 al inicio)

F = n=>{
  do {
    ++n; // next number
    for(x = n; x != 0; x >>= 1) {
      // loop to find 11 in any position
      if ((x & 3) == 3) { // least 2 bits == 11
        break;
      }
    }
  } while (x != 0) // if 11 was found,early exit from inner loop and x != 0
  return n
}
edc65
fuente
Esto %4>2parece un poco de hechicería de la teoría de los números, ¿puedes explicarlo || proporcionar un enlace?
Jacob
@Jacob (x% 4> 2) es simplemente ((x & 3) == 3), pero con la precedencia del operador es JS, evita los 2 corchetes
edc65
Simple de lo que pensaba. Ahora con la versión no golfista está claro. ¡Gracias!
Jacob
3

Python 2, 37 bytes

f=input()+1
while f&2*f:f+=1
print f

Usó la lógica x & 2*x == 0para 1 número disperso.
Gracias a @Nick y @CarpetPython.

ShinMigami13
fuente
¿Por qué el voto negativo? Esto funciona perfectamente bien y también está bien golfizado.
ETHproductions
¡Bienvenido a PPCG, por cierto, y buena primera respuesta! Te animo a continuar respondiendo desafíos en el sitio :-)
ETHproductions
2

JavaScript, 75 66 62 bytes

¡Gracias a Martin Büttner por guardar 9 bytes y Pietu1998 por 4 bytes!

function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}

Cómo funciona: ejecuta un forbucle a partir de a + 1que el número actual no sea disperso en 1, y si lo es, el bucle se interrumpe y devuelve el número actual. Para verificar si un número es escaso, lo convierte a binario y verifica si no contiene 11.

Código sin golf:

function nextOneSparseNumber(num) {
    for (num++; /11/.test(num.toString(2)); num++);
    return num;
}
ProgramFOX
fuente
2

Julia, 40 bytes

n->(while contains(bin(n+=1),"11")end;n)

Esto crea una función anónima que acepta un solo entero como entrada y devuelve el siguiente entero más alto de 1 disperso. Para llamarlo, dale un nombre, por ejemplo f=n->..., y do f(12).

Ungolfed + explicación:

function f(n)

    # While the string representation of n+1 in binary contains "11",
    # increment n. Once it doesn't, we've got the answer!

    while contains(bin(n += 1), "11")
    end

    return(n)
end

Ejemplos:

julia> f(12)
16

julia> f(16)
20

¡Sugerencias y / o preguntas son bienvenidas como siempre!

Alex A.
fuente
2

> <> (Pez) , 31 + 3 = 34 bytes

1+:>:  4%:3(?v~~
;n~^?-1:,2-%2<

Uso:

>python fish.py onesparse.fish -v 12
16

3 bytes agregados para la -vbandera.

randomra
fuente
1

JavaScript (ECMAScript 6), 40

Por recursividad:

g=x=>/11/.test((++x).toString(2))?g(x):x

JavaScript, 56

Lo mismo sin funciones de flecha.

function f(x){return/11/.test((++x).toString(2))?f(x):x}
nutki
fuente
1

Scala, 65 bytes

(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}

(si se requiere una función con nombre, la solución será de 69 bytes)

Jacob
fuente
1

Python, 39 33 bytes

Pruébelo aquí: http://repl.it/gpu/2

En forma lambda (gracias a xnor para jugar al golf):

f=lambda x:1+x&x/2and f(x+1)or-~x

¡La sintaxis de la función estándar resultó ser más corta que una lambda por una vez!

def f(x):x+=1;return x*(x&x*2<1)or f(x)
mbomb007
fuente
Es posible reducir el One Lambda de 33 bytes: f=lambda x:1+x&x/2and f(x+1)or-~x. Resulta que si cambias de bit a la derecha en lugar de a la izquierda, puedes usarlo en x/2lugar de (x+1)/2porque la diferencia siempre está en cero bits x+1. Sin embargo, la especificación pide un programa.
xnor
Le pregunté y dijo que podemos hacer funciones. La mayoría de las respuestas ya están.
mbomb007
1

Java, 33 bytes.

Utiliza el método en esta respuesta

n->{for(;(n++&2*n)>0;);return n;}

TIO

Benjamin Urquhart
fuente
0

Rubí, 44

->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}

Bastante básico Una lambda con un bucle infinito y una expresión regular para probar la representación binaria. Desearía que loopcediera un número de índice.

Max
fuente
@ mbomb007 hecho. gracias por el consejo.
Max
0

Matlab ( 77 74 bytes)

m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N

Notas:

  • Basta con números de prueba m+1a 2*m, donde mestá la entrada.
  • ~any(x)es truesi xcontiene todos ceros o si xestá vacío
Luis Mendo
fuente
0

C (32 bytes)

f(int x){return 2*++x&x?f(x):x;}

Implementación recursiva del mismo algoritmo que tantas otras respuestas.

Alquimista
fuente
0

Perl, 16 bytes

Combinando el x&2*xde varias respuestas (creo que Nick es el primero) con los redo rendimientos de nutki :

perl -pe'++$_&2*$_&&redo'

Probado en fresa 5.26.

msh210
fuente
0

Jalea , 7 bytes

‘&Ḥ¬Ɗ1#

Un programa completo que acepta un número entero no negativo que imprime un número entero positivo (como enlace monádico produce una lista que contiene un número entero positivo).

Pruébalo en línea!

¿Cómo?

Comenzando en v=n+1, e incrementando, doble vpara desplazar cada bit hacia arriba un lugar y bit a bit Y con vy luego realizar NO lógico para probar si ves escaso hasta que se encuentre uno de esos números.

‘&Ḥ¬Ɗ1# - Main Link: n   e.g. 12
‘       - increment           13
     1# - 1-find (start with that as v and increment until 1 match is found) using:
    Ɗ   -   last three links as a dyad:
  Ḥ     -   double v
 &      -   (v) bit-wise AND (with that)
   ¬    -   logical NOT (0->1 else 1)
        - implicit print (a single item list prints as just the item would)
Jonathan Allan
fuente
0

Stax , 5 bytes

╦>ù╤x

Ejecutar y depurarlo

Funciona usando este procedimiento. La entrada comienza en la parte superior de la pila.

  • Incrementar y copiar dos veces.
  • Reducir a la mitad la parte superior de la pila.
  • Bitwise-y dos elementos superiores en la pila.
  • Si el resultado es verdadero (distinto de cero), repita todo el programa.
recursivo
fuente