Tarea
Encuentre el conjunto de números de modo que la representación binaria contenga dos o más corridas 1
separadas por al menos una 0
.
Por ejemplo, para los números que tienen 4 bits de longitud:
0 0000 (no ones)
1 0001 (only one run)
2 0010 (only one run)
3 0011 (only one run)
4 0100 (only one run)
5 0101 Valid
6 0110 (only one run)
7 0111 (only one run)
8 1000 (only one run)
9 1001 Valid
10 1010 Valid
11 1011 Valid
12 1100 (only one run)
13 1101 Valid
14 1110 (only one run)
15 1111 (only one run)
Entrada
Un entero proporcionado a la aplicación a través de alguna entrada en el rango 3 .. 32
. Esto representa el número máximo de bits a contar.
La entrada de n
indica que los números deben ser examinados.0 .. 2n-1
Salida
Una lista delimitada (su elección) de todos los números que cumplen con los criterios. Los números deben presentarse en orden numérico. Un delimitador final adicional es aceptable. Los recintos de estructura de datos (p. Ej. []
Y similares) también son aceptables.
Ejemplo
Input: 3
Output: 5
Input: 4
Output: 5, 9, 10, 11, 13
Input: 5
Output: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
Este es el código de golf : la respuesta con la menor cantidad de bytes gana.
\n
delimitando y colocando un\n
en la última línea, entonces,
delimitado con un,
final también debería ser aceptable. Actualizado.[1, 2, 3]
?Respuestas:
Pyth, 12 bytes
Pruébalo en línea.
Idea
La representación binaria de cualquier número positivo siempre comienza con una carrera de 1 s, posiblemente seguida de otras carreras alternas de 0 sy 1 s. Si hay al menos tres ejecuciones separadas, se garantiza que dos de ellas serán ejecuciones de 1 s.
Código
fuente
Python, 48
Había estado pensando demasiado en esto. Solo necesitamos verificar si la expansión binaria contiene
'01'
.Para que haya dos series de unidades, la de la derecha debe ir precedida de a
0
. Si solo hay una carrera, no habrá ningún líder0
, por lo que eso no sucederá.Vieja respuesta:
La representación binaria de Python funciona muy bien aquí. Un número binario se escribe como
bin(9)=='0b10110'
. División en'0'
resultados en una lista de0
, entre dos cualesquiera consecutivas0
, y a la derecha de cualquier final0
b
seguida de una o más iniciales1
's que no son líderesLas dos primeras categorías siempre existen, pero la última solo existe si hay una ejecución
1
que no contiene el inicio'1'
, y solo si hay más de una ejecución1
. Por lo tanto, es suficiente verificar si la lista contiene más que2
elementos distintos.Python 3.5 ahorra 2 caracteres al desempacar
{*_}
en lugar deset(_)
.fuente
/01/
lugar de/10+1/
. Aproveché eso en Perl .Ruby,
444038 caracterestachado 44 sigue siendo regular 44; (
Una función anónima (proc, en realidad) que toma un número entero y devuelve una matriz.
Utiliza la expresión regular@histocrat señala que si/10+1/
: a1
, al menos una0
, y luego otra1
.01
está en algún lugar de la cadena, debe haber un1
lugar antes.fuente
/10+1/=~'%b'%x
. Además, puede guardar un personaje utilizando un rango inclusivo (0..2**n
) ya2**n
que nunca tendrá varias ejecuciones.=~
. ¡Gracias!/01/
funciona igual de bien. Si hay un01
, debe haber un 1 a la izquierda en alguna parte.Julia,
4341 bytesEsto crea una función sin nombre que acepta un número entero y devuelve una matriz. Utiliza el truco regex de histocrats (usado en la respuesta de Doorknob), donde
01
solo coincidirá si hay un 1 anterior.Sin golf:
fuente
Matlab,
79 68 6459La idea es interpretar el número binario como una matriz de ceros y unos, y luego calcular la diferencia absoluta entre cada par de vecinos. Si tenemos dos o más veces una diferencia de 1, entonces obviamente tenemos una serie de dos o más. Tenga en cuenta que esto solo funciona si representamos el número binario sin ceros a la izquierda.
Versiones antiguas:
fuente
JavaScript (ES7),
8985726962 bytesSanta vaca, crear rangos en JS no es fácil.
Quizás sería más corto con unNo, mentí; En realidad es un poco más largo. Oh bien. Supongo que tendré que conformarme con 27 bytes guardados. (7 gracias a Mwr247!)for
bucle real .Funciona correctamente en las últimas versiones de Firefox, pero probablemente no en ningún otro navegador. Pruébalo:
(Fragmento tomado de esta página )
Sugerencias bienvenidas!
fuente
.keys()
lugar de.fill()
y ena
lugar dei
atar el mío para 62:x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]
Haskell,
686153 bytesMejora de Damien
Historia:
Esto corrige el error (Switched == y =, y cuadrado en lugar de la potencia de dos). Y reemplace verdadero con 2> 1 y falso con 1> 2. También gracias a señalar que 2 ^ x siempre falla. Gracias a Thomas Kwa y nimi
Originalmente
Si tiene que ser un programa completo,
fuente
1..(2^x-1)
que puede ser1.. (2^x)
porque 2 ^ x siempre falla.False
yTrue
con1>2
y1<2
. No hay necesidad de paréntesis2^x-1
. (Por cierto: tienes un error tipográfico: debe ser4==1=True
).mod
4 == 1 = x> 4 | 2> 1 = g $ xdiv
2APL,
3427 bytesEsto crea una función monádica sin nombre que acepta un número entero a la derecha y devuelve una matriz.
Explicación:
¡Guardado 7 bytes gracias a Dennis!
fuente
R,
5547 bytes(con algo de ayuda de @ Alex.A)
R no tiene una función incorporada para mostrar los números convertidos de una manera conveniente, por lo que estoy usando
R.utils::intToBin
para esto, mientras que todo lo demás es solo informar la ubicación de la expresión de expresiones regulares coincidentes e imprimir en STDOUT mientras está separado por un espacio.fuente
cat
es un espacio, por lo que podría omitir por,sep=","
completo, ahorrando 7 bytes.CJam, 14
3 bytes más cortos gracias a Dennis. Pruébalo en línea
fuente
2be`,2>
.2be`2>
y2,#)
debería funcionar también. Además, el OP ha aclarado que la salida se puede imprimir en forma de lista.JavaScript (ES6),
69686762 bytesHoy descubrí una nueva forma más corta de llenar dinámicamente matrices sin el uso de relleno o mapa. Hacer
x=>[...Array(x).keys()]
devolverá una matriz de rango 0 a x. Si desea definir su propio rango / valores, usex=>[...Array(x)].map((a,i)=>i)
, ya que son solo unos pocos bytes más.fuente
Java,
214165155154148141110 bytesEste envío explota el hecho de que una representación de cadena binaria de un número en Java nunca tiene un cero a la izquierda. Si la cadena "01" aparece en la representación binaria de un número, debe marcar la segunda aparición del número "1".
Golfizado:
Sin golf:
Salida del programa (recuerde, los delimitadores finales son aceptables):
fuente
int
para la variable de contador?long
se requiere un 64 bits . Además, el uso de enint
realidad aumentaría el tamaño del código debido a que hace referencia a laInteger
clase contenedora que analiza los números. Creo que el lugar probable para ahorrar espacio sería la expresión regular, pero mis pruebas mostraron que tengo que tener el.*
Long
envoltorioint
. (¿Bueno, no en este caso, pero en general?)int
se promocionarálong
cuando se use como parámetro conLong
. En este caso, aunque realmente no hay ninguna forma de usar unint
debido al bit de signo, yInteger
es más largo queLong
. Aún así, he encontrado algunas formas de exprimir un poco de espacio extra de un lenguaje tan detallado como Java.new Long()
lugar deLong.parseLong()
?C (gcc) ,
11199 bytesPruébalo en línea!
¡12 bytes afeitados gracias a @ceilingcat!
Sin golf:
La función ffsl () le proporciona el índice del primer bit que se establece en un entero largo. Entonces hacemos un bucle desde
i = 1
2 ^ número_de_bits. Lo ajustamosx
ai
desplazado a la derecha hasta que hayamos eliminado todos los bits cero consecutivos en el extremo menos significativo. Luego, nos desplazamos hacia lax
derecha hasta que hayamos eliminado todos los 1 bits consecutivos en el extremo menos significativo. Si el resultado todavía no es cero, encontramos una coincidencia.fuente
if (popcount(i ^ (i*2))>3)
y expandir popcount () a una serie de AND bit a bit y operaciones de cambio. Pero eso resultaría en un código bastante largo.JavaScript (ES6) 76
fuente
,,,,,5,,,,9,10,11,,13,,,,17,18,19,20,21,22,23,,25,26,27,,29,,
K5, 19 bytes
Esto funciona de acuerdo con principios similares a la solución de Dennis, pero con menos componentes para aprovechar.
Primero, genere una serie de x-tuplas binarias (
+!x#2
), luego para cada tupla encuentre cada punto que un dígito no coincida con el anterior si tratamos el elemento -1 de la lista como 0 para este propósito (~0=':'
). Nuestras soluciones son donde dos es menor que la suma de cada cuenta de ejecución. (&2<+/'
)Mostrar cada paso intermedio es más claro:
Y todos juntos:
fuente
Pip, 13 + 1 = 14 bytes
Toma datos de la línea de comando y usa la
-s
bandera para espacios entre números de salida.Bastante sencillo: construir
range(2**a)
y filtrarlambda _: "01" in toBinary(_)
. Estaba bastante contento de pensar en la01
idea de forma independiente. No se necesitan comillas01
porque escanea como un literal numérico (los números y las cadenas son del mismo tipo en Pip).fuente
Julia, 40 bytes
Esto utiliza un enfoque algo diferente a la otra solución de Julia: en lugar de hacer una búsqueda de cadena para "01" en la cadena de bits, utiliza algunas matemáticas para determinar si el número satisface la condición.
i$i>>1
tendrá unos solo en los lugares donde el dígito cambia de cero a uno, o de uno a cero. Como tal, debe haber al menos tres unidades parai
alternar entre cero y una vez.count_ones
encuentra la cantidad de unidades y luegofilter
elimina las que no tienen suficientes.fuente
C ++,
197188141 bytesNota: esto fue escrito y probado usando MSVC ++ 2013. Parece que
#include
ing<iostream>
incluye todos los encabezados C necesarios para que esto funcione. También parece que el código ya no es realmente C ++, pero compilar usando C ++ permite ese truco de encabezado que reduce el tamaño del código en comparación con la inclusión de un montón de encabezados C más.Usar en
printf
lugar decout
también guarda un par de bytes.Golfizado:
Sin golf:
fuente
'\n'
lugar de std :: endl (en general), o','
dado que cualquier separador es válido y uno posterior está bien.strstr(c,"01")
.1<<atol(b[1])
deberían ser1L<<atol(b[1])
, de lo contrario el resultado de esa expresión será un entero de 32 bits con signo, lo que significa que el código solo se ejecutará hasta 2 ^ 30. El printf debería usar%ld
para imprimir números entre 2 ^ 31 y 2 ^ 32 correctamente.Perl 5,
5553494741 bytes5452484640 bytes, más uno para la-E
bandera en lugar de-e
.Gracias a xnor por la pista sobre el uso en
/01/
lugar de/10+1/
, que ahorró dos bytes.Gracias a Dennis por el consejo de usar en
<>
lugar de$ARGV[0]
, que ahorró seis bytes.fuente
C,
8481 bytesEsto se basa en los comentarios que hice en otra respuesta C a esta pregunta sobre la posibilidad de usar operadores simples de bits. Funciona cambiando todos los 0 bits finales a 1 en la instrucción i | (i-1). Luego cambia todos los bits finales de 1 a 0 usando k & (k + 1). Esto dará como resultado un cero si solo hay una serie de unidades y, de lo contrario, no será cero. Supongo que largo es de 64 bits, pero podría corregir esto a expensas de tres bytes usando int64_t en su lugar.
Sin golf
fuente
int64_t
solo se define si usted#include<stdint.h>
. Asegurar que la operación de 64 bits requiere unlong long
tipo a un costo de 5 bytes.long i
por%d
formato. Tenga en cuenta también que()
son superfluos para los operadores&
y|
. ¡Arreglar esto ahorra 3 bytes!long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}
Pyth,
201716 bytesDemo en vivo.
fuente
"01"
. Excepto por 0, el binario repr. siempre comenzará con un 1.Python 2.7, 89 bytes
Creo que esto podría jugarse un poco.
fuente
0
en la salida.print[i for i in range(2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]
es dos bytes más corto. Pero con la solución para0
sería la misma longitud (89), si la usarange(1,2**input())
.TI-BASIC,
343230 bytesPara una calculadora de la serie TI-83 + / 84 +.
Para que un número contenga dos corridas de 1s, debe contener dos
10
s cuando añadimos un cero final a la representación binaria.En lugar de generar la representación binaria y verificar a
10
, probamos matemáticamente pares de bits usando el resto por 4 (int(4fPart(
), que dará2
dónde hay a10
. Debido a que no nos importa el orden,randIntNoRep(
es la forma más corta de generar la lista de exponentes.Usamos
log(
para verificar el número de carreras:Si hay al menos 2 ejecuciones, entonces el resultado
log(
es positivo y se muestra el número.Si hay una ejecución, entonces
log(
es 0, y el número no se muestra.Si no hay carreras (lo que ocurre primero en X = 2 ^ Ans), luego
log(
arroja un ERR: DOMAIN, deteniendo la salida exactamente en el punto correcto.Lo usamos
e^(Ans
como argumento final delFor(
bucle: siempre es mayor que2^Ans
, peroe^(
es un token único, por lo que es un byte más corto.Entrada / salida para N = 4:
Entonces la calculadora arroja un error; la pantalla de error se ve así:
Cuando se presiona 1, la pantalla de inicio se muestra nuevamente:
Las calculadoras TI almacenan todos los números en un flotante BCD con 14 dígitos de precisión, no un flotante int o binario. Por lo tanto, las divisiones por potencias de dos mayores que
2^14
pueden no ser exactas. Si bien he verificado que los números más complicados3*2^30-1
y que2^32-1
se manejan correctamente, no he descartado la posibilidad de errores de redondeo. Sin embargo, me sorprendería si hubiera errores para cualquier entrada.fuente
matlab
(90)(70)ejecución
4
ans =
ans =
ans =
principio
Cualquier número tomado del intervalo] f (n, l), f (n, l) + 2 ^ (l-1) [donde l> 1 verifica esta condición, por lo que el resultado es el resultado de la negación de esta serie en términos de n.
x = 1
x = x + 1 =
01
,x = x + 2 ^ 0 =
11
,x = x + 1 =
001
,x = x + 2 ^ 1 =
011
,x = x + 2 ^ 0 =
111
,x = x + 1 =
0001
,x = x + 2 ^ 2 =
0011
,x = x + 2 ^ 1 =
0111
,x = x + 2 ^ 0 =
0111
,x = x + 1 =
1111
...x + 1, x = x + 2 ^ n, x = x + 2 ^ (n-1) ... x = x + 2 ^ 0
Mi programa imprime el rango entre cada dos líneas (si existe)
Después de un período de lucha, logré encontrar una representación matemática para esta serie que es:
2 ^ l (0 + 1 + 2 ^ 1 + ... 2 ^ k) con l + k <n
= 2 ^ l (2 ^ k-1)
puntuación = 90
fuente
C,
103102 bytesExpandiéndose (realmente contrayéndose) en la entrada G.Sliepen, aprovechando la observación xnor sobre el
01
patrón en la representación binaria, pero usando solo funciones estándar y algunos cambios de bits.Versión sin golf:
El bucle interno busca
i
el patrón binario01
desplazándose iterativamentex
hacia la derecha siempre que le queden 3 bits.printf
devuelve el número de caracteres impresos, por lo tanto, nunca0
, por lo que la prueba del bucle interno falla después delprintf
, evitando la necesidad de unabreak
instrucciónC ++,
129128 bytesAdaptando la misma idea, la variante C ++ está aquí:
Técnicamente, debería hacer
i
unalong long
operación para asegurar la operación de 64 bits y calcular hasta2^32
5 bytes adicionales, pero las plataformas modernas tienen entradas de 64 bits.fuente
JavaScript ES6, 60 bytes
Código
Pruébalo en línea!
Explicación
fuente
C (tipo de - compila con advertencias en GCC) - 103
Esto no utiliza funciones de biblioteca de ningún tipo, excepto printf. Al observar esto, puede ver que no se han escatimado esfuerzos para cumplir con los estándares o evitar UB.
Para que sea compatible, necesitaría hacer muchas cosas, como stdio.h, lo que sería contrario al espíritu de hacerlo lo más pequeño posible.
Si alguien tiene sugerencias para acortarlo, avíseme.
fuente
PowerShell, 80 bytes
fuente
Python, 44 bytes
De acuerdo, esto probablemente podría ser más corto, pero es mi primer codegolf:
Piense que esto responde a la pregunta, por favor no rechace el voto si no lo hace, simplemente publique lo que está mal a continuación.
fuente
input()
es ideal) para obtenern
, y luego solo contar hasta2^n-1
, en lugar de realizar un bucle indefinidamente. Además, puede usar 1 y 2 espacios para la anidación, en lugar de 4 y 8, y usarmap
o una comprensión de lista probablemente acortaría enormemente su código.Otra respuesta matlab diferente de buena puntuación.
matlab
60 60(57)ejecución
ans =
>> ans(5)
ans =
1
ejemplo:
0000111
se rechaza porque ~ x =1111
, ~ x + 1 =00001
contiene un dígito = 10100111
se acepta porque ~ x =1011
, ~ x + 1 =0111
contiene muchos 1fuente