Números con múltiples carreras de unos

30

Tarea

Encuentre el conjunto de números de modo que la representación binaria contenga dos o más corridas 1separadas 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 nindica 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 : la respuesta con la menor cantidad de bytes gana.


fuente
Creo que te perdiste 23 para n = 5.
xnor
@xnor estás en lo correcto. Gracias y sí, eso tampoco lo hace equivalente a A094695. Hmm oeis.org/A101082 vs oeis.org/A166934
@VTCAKAVSMoACE sí. Si uno está \ndelimitando y colocando un \nen la última línea, entonces ,delimitado con un ,final también debería ser aceptable. Actualizado.
1
¿Puede la entrada estar en un formato de lista como [1, 2, 3]?
kirbyfan64sos
@ Kirbyfan64sos sí. Actualizado.

Respuestas:

7

Pyth, 12 bytes

f<2r.BT8U^2Q

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

              (implicit) Store the evaluated input in Q.
         ^2Q  Calculate 2**Q.
f       U     Filter; for each T in [0, ..., 2**Q-1]:
    .BT         Compute T's binary representation.
   r   8        Perform run-length encoding.
                This returns a list of character/run-length pairs.
 <2             Discard the trailing two pairs.
                This returns a non-empty array if there are more than 2 runs.
              Keep T if the array was truthy (non-empty).
Dennis
fuente
22

Python, 48

lambda n:[i for i in range(2**n)if'01'in bin(i)]

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íder 0, por lo que eso no sucederá.


Vieja respuesta:

lambda n:[i for i in range(2**n)if len(set(bin(i).split('0')))>2]

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 de

  • Cadenas vacías a la izquierda de la inicial 0, entre dos cualesquiera consecutivas 0, y a la derecha de cualquier final0
  • La letra bseguida de una o más iniciales
  • Carreras de 1's que no son líderes

Las dos primeras categorías siempre existen, pero la última solo existe si hay una ejecución 1que no contiene el inicio '1', y solo si hay más de una ejecución 1. Por lo tanto, es suficiente verificar si la lista contiene más que 2elementos distintos.

Python 3.5 ahorra 2 caracteres al desempacar {*_}en lugar de set(_).

xnor
fuente
Gracias por la idea de usar en /01/lugar de /10+1/. Aproveché eso en Perl .
msh210
13

Ruby, 44 40 38 caracteres

tachado 44 sigue siendo regular 44; (

->n{(0..2**n).select{|x|/01/=~'%b'%x}}

Una función anónima (proc, en realidad) que toma un número entero y devuelve una matriz.

Utiliza la expresión regular /10+1/: a 1, al menos una 0, y luego otra 1. @histocrat señala que si 01está en algún lugar de la cadena, debe haber un 1lugar antes.

Pomo de la puerta
fuente
1
El uso de una cadena de formato es un poco más corto aquí: /10+1/=~'%b'%x. Además, puede guardar un personaje utilizando un rango inclusivo ( 0..2**n) ya 2**nque nunca tendrá varias ejecuciones.
histocrat
@histocrat Huh, nunca supe que podría cambiar el orden de la cadena y la expresión regular con =~. ¡Gracias!
Pomo de la puerta
1
Espera, en realidad la expresión regular /01/funciona igual de bien. Si hay un 01, debe haber un 1 a la izquierda en alguna parte.
histocrat
@histocrat Oh, eso es inteligente! Eso salva dos personajes.
Pomo de la puerta
7

Julia, 43 41 bytes

n->filter(i->ismatch(r"01",bin(i)),1:2^n)

Esto 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 01solo coincidirá si hay un 1 anterior.

Sin golf:

function f(n::Int)
    # Take the integers from 1 to 2^n and filter them down to
    # only those such that the binary representation of the integer
    # matches the regex /01/.
    filter(i -> ismatch(r"01", bin(i)), 1:2^n)
end
Alex A.
fuente
El truco del histocrático, no el mío. :)
Pomo de la puerta
@Doorknob Oh, oye, ahora ambos tienen crédito. :)
Alex A.
6

Matlab, 79 68 64 59

La 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.

@(n)find(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,1:2^n-1))

Versiones antiguas:

k=1:2^input('')-1;k(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,k))

for k=1:2^input('')-1;if sum(~~diff(dec2bin(k)+0))>1;disp(k);end;end

for k=1:2^input('')-1;if sum(~~conv(dec2bin(k)+0,[-1,1],'v'))>1;disp(k);end;end
falla
fuente
6

JavaScript (ES7), 89 85 72 69 62 bytes

Santa vaca, crear rangos en JS no es fácil. Quizás sería más corto con un forbucle real . No, mentí; En realidad es un poco más largo. Oh bien. Supongo que tendré que conformarme con 27 bytes guardados. (7 gracias a Mwr247!)

x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]

Funciona correctamente en las últimas versiones de Firefox, pero probablemente no en ningún otro navegador. Pruébalo:

<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px">5</textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode="x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]";function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML+='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{var evalResult=eval(code);if(typeof evalResult=="function"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>

(Fragmento tomado de esta página )

Sugerencias bienvenidas!

ETHproducciones
fuente
Puede usar en .keys()lugar de .fill()y en alugar de iatar el mío para 62:x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]
Mwr247
@ Mwr247 ¡Gracias! Me pregunto si es posible en menores de 62 años ... :)
ETHproductions
6

Haskell, 68 61 53 bytes

Mejora de Damien

g x|x`mod`4==1=x>4|2>1=g$x`div`2
a x=filter g[1..2^x]

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

g x|x<5=1>2|x`mod`4==1=2>1|2>1=g$x`div`2
a x=filter g[1..2^x]

Originalmente

g x|x<5=False|x`mod`4=1==True|2>1=g$x`div`2
a x=filter g[1..(x^2-1)]

Si tiene que ser un programa completo,

g x|x<5=False|x`mod`4==1=True|2>1=g$x`div`2
main=interact$show.a
a x=filter g[1..2^(read x)]
Akangka
fuente
1
Las lambdas están bien, ya que OP no especificó escribir una función o programa con nombre. Por cierto, ¡bienvenido a PPCG!
lirtosiast
1
Creo que te refieres a lo 1..(2^x-1)que puede ser 1.. (2^x)porque 2 ^ x siempre falla.
lirtosiast
Puede reemplazar las constantes Falsey Truecon 1>2y 1<2. No hay necesidad de paréntesis 2^x-1. (Por cierto: tienes un error tipográfico: debe ser 4==1=True).
nimi
Gracias por la corrección de errores tipográficos. Era tarde en la noche en mi tiempo.
Akangka
¡buenos trucos! Creo que puedes reducir g a: gx | x mod4 == 1 = x> 4 | 2> 1 = g $ x div2
Damien el
5

APL, 34 27 bytes

{0~⍨{⍵×2<+/2≢/⍵⊤⍨⍵/2}¨⍳2*⍵}

Esto crea una función monádica sin nombre que acepta un número entero a la derecha y devuelve una matriz.

Explicación:

                     }¨⍳2*⍵}  ⍝ For each integer from 1 to 2^input...
              ⍵⊤⍨⍵/2         ⍝ Get the binary representation as a vector
           2≢/                ⍝ Pairwise non-match, yielding a boolean vector
       2<+/                   ⍝ Check whether the number of trues is >2
     ⍵×                       ⍝ Yield the integer if so, otherwise 0
{0~⍨{                         ⍝ Remove the zeros from the resulting array

¡Guardado 7 bytes gracias a Dennis!

Alex A.
fuente
4

R, 55 47 bytes

(con algo de ayuda de @ Alex.A)

cat(grep("10+1",R.utils::intToBin(1:2^scan())))

R no tiene una función incorporada para mostrar los números convertidos de una manera conveniente, por lo que estoy usando R.utils::intToBinpara 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.

David Arenburg
fuente
Creo que el separador predeterminado para cates un espacio, por lo que podría omitir por ,sep=","completo, ahorrando 7 bytes.
Alex A.
@AlexA. sí, entonces ¿puedo usar un espacio aquí como sep? No estaba seguro
David Arenburg
1
El OP dijo un delimitador de su elección, así que creo que un espacio parece lo suficientemente razonable. :)
Alex A.
¿Esto realmente necesita la función de gato? sin él, la salida estará delimitada por tabuladores. El contador de la izquierda es parte de la interfaz de usuario, si lo escribe en un archivo, esto no se incluirá, por lo que no es parte de la salida.
freekvd
@freekvd sin él no se imprimirá en STDOUT, algo sobre las tontas reglas de este sitio.
David Arenburg el
4

CJam, 14

2qi#{2b2,#)},p

3 bytes más cortos gracias a Dennis. Pruébalo en línea

aditsu
fuente
¿Qué tal 2be`,2>.
jimmy23013
2
2be`2>y 2,#)debería funcionar también. Además, el OP ha aclarado que la salida se puede imprimir en forma de lista.
Dennis
4

JavaScript (ES6), 69 68 67 62 bytes

a=>[...Array(1<<a).keys()].filter(i=>/01/.test(i.toString(2)))

Hoy 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, use x=>[...Array(x)].map((a,i)=>i), ya que son solo unos pocos bytes más.

Mwr247
fuente
4

Java, 214 165 155 154 148 141 110 bytes

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

String f(int l){String r="";for(long i=5;i<1L<<l;++i)if(Long.toString(i,2).contains("01"))r+=i+", ";return r;}

Sin golf:

public class NumbersWithMultipleRunsOfOnes {

  public static void main(String[] a) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "3", "5" },
      { "4", "5, 9, 10, 11, 13" },
      { "5", "5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumbersWithMultipleRunsOfOnes().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  String f(int l) {
    String r = "";
    for (long i = 5; i < 1L << l; ++i)
      if (Long.toString(i, 2).contains("01")) r += i + ", ";
    return r;
  }
  // End golf
}

Salida del programa (recuerde, los delimitadores finales son aceptables):

Input: 3
Expected: 5
Actual:   5, 

Input: 4
Expected: 5, 9, 10, 11, 13
Actual:   5, 9, 10, 11, 13, 

Input: 5
Expected: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
Actual:   5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 

fuente
¿No puedes usar intpara la variable de contador?
flawr
Todos los tipos enteros en Java no están firmados. Para trabajar con un entero positivo de 32 bits, longse requiere un 64 bits . Además, el uso de en intrealidad aumentaría el tamaño del código debido a que hace referencia a la Integerclase 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 .*
Ah, claro, pero pensé que podrías usar el Longenvoltorio int. (¿Bueno, no en este caso, pero en general?)
error
Sí, intse promocionará longcuando se use como parámetro con Long. En este caso, aunque realmente no hay ninguna forma de usar un intdebido al bit de signo, y Integeres más largo que Long. Aún así, he encontrado algunas formas de exprimir un poco de espacio extra de un lenguaje tan detallado como Java.
¿Se puede usar en new Long()lugar de Long.parseLong()?
Ypnypn
4

C (gcc) , 111 99 bytes

long i,x;main(a,b)char**b;{for(;++i<1L<<atol(b[1]);x>>ffsl(~x)-1&&printf("%ld,",i))x=i>>ffsl(i)-1;}

Pruébalo en línea!

¡12 bytes afeitados gracias a @ceilingcat!

Sin golf:

int main(int a, char **b) {
  for(long i = 0, x = 0; ++i < (1LL << atol(b[1])); ) {
    x = i >> (ffsl(i) - 1);
    if (x >> (ffsl(~x) - 1))
      printf("%ld,", i);
  }
}

La función ffsl () le proporciona el índice del primer bit que se establece en un entero largo. Entonces hacemos un bucle desde i = 12 ^ número_de_bits. Lo ajustamos xa idesplazado a la derecha hasta que hayamos eliminado todos los bits cero consecutivos en el extremo menos significativo. Luego, nos desplazamos hacia la xderecha 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.

G. Sliepen
fuente
2
Tengo que decir que realmente me gusta que alguien haya hecho una respuesta de manipulación en lugar de un enfoque de "convertir a cadena y regex".
@MichaelT Me pregunto si hay una solución corta usando solo operaciones primitivas bit a bit.
lirtosiast
@ThomasKwa Eso podría ser algo que hacer como un desafío de código .
Interesante. También puede escribir la prueba de esta manera: 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.
G. Sliepen
1
@ThomasKwa y = x | (x-1) para activar todos los 0 bits más a la derecha. Entonces z = y & (y + 1) para desactivar todos los bits finales de 1. Si z no es cero, entonces el número original tuvo más de una ejecución.
Alchymist
3

JavaScript (ES6) 76

f=n=>Array(1<<n).fill().map((_,x)=>/01/.test(x.toString(2))?x+',':'').join``

//TEST
for(i=1;i<16;i++)O.innerHTML+=i+' -> '+f(i)+'\n'
<pre id=O></pre>

edc65
fuente
@DLosc no, el resultado sería algo así,,,,,5,,,,9,10,11,,13,,,,17,18,19,20,21,22,23,,25,26,27,,29,,
edc65
3

K5, 19 bytes

Esto funciona de acuerdo con principios similares a la solución de Dennis, pero con menos componentes para aprovechar.

{&2<+/'~0=':'+!x#2}

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:

  4#2
2 2 2 2

  !4#2
(0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1)

  +!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 0
 0 0 1 1
 0 1 0 0
 0 1 0 1
 0 1 1 0
 0 1 1 1
 1 0 0 0
 1 0 0 1
 1 0 1 0
 1 0 1 1
 1 1 0 0
 1 1 0 1
 1 1 1 0
 1 1 1 1)

  ~0=':'+!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 1
 0 0 1 0
 0 1 1 0
 0 1 1 1
 0 1 0 1
 0 1 0 0
 1 1 0 0
 1 1 0 1
 1 1 1 1
 1 1 1 0
 1 0 1 0
 1 0 1 1
 1 0 0 1
 1 0 0 0)

  +/'~0=':'+!4#2
0 1 2 1 2 3 2 1 2 3 4 3 2 3 2 1

  2<+/'~0=':'+!4#2
0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0

  &2<+/'~0=':'+!4#2
5 9 10 11 13

Y todos juntos:

  {&2<+/'~0=':'+!x#2}'3 4 5 
(,5
 5 9 10 11 13
 5 9 10 11 13 17 18 19 20 21 22 23 25 26 27 29)
JohnE
fuente
2

Pip, 13 + 1 = 14 bytes

Toma datos de la línea de comando y usa la -sbandera para espacios entre números de salida.

01NTB_FI,2**a

Bastante sencillo: construir range(2**a)y filtrar lambda _: "01" in toBinary(_). Estaba bastante contento de pensar en la 01idea de forma independiente. No se necesitan comillas 01porque escanea como un literal numérico (los números y las cadenas son del mismo tipo en Pip).

DLosc
fuente
2

Julia, 40 bytes

n->filter(i->count_ones(i$i>>1)>2,1:2^n)

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>>1tendrá 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 para ialternar entre cero y una vez. count_onesencuentra la cantidad de unidades y luego filterelimina las que no tienen suficientes.

Glen O
fuente
2

C ++, 197 188 141 bytes

Nota: esto fue escrito y probado usando MSVC ++ 2013. Parece que #includeing <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 printflugar de couttambién guarda un par de bytes.

Golfizado:

#include<iostream>
int main(int a,char**b){char c[34];for(long i=5;i<1L<<atol(b[1]);++i){_ltoa(i,c,2);if(strstr(c,"01"))printf("%ld\n",i);}}

Sin golf:

#include <iostream>
int main(int a, char **b) {
  char c[34];
  for (long i = 5; i < 1L << atol(b[1]); ++i) {
    _ltoa(i, c, 2);
    if (strstr(c, "01"))
      printf("%ld\n", i);
  }
}

fuente
Yoiu puede usar en '\n'lugar de std :: endl (en general), o ','dado que cualquier separador es válido y uno posterior está bien.
G. Sliepen
En lugar de expresiones regulares, simplemente puedes hacerlo strstr(c,"01").
G. Sliepen
@ G.Sliepen gracias! Honestamente, simplemente copié mi solución Java y la convertí a C ++, pero la solución simple a menudo es la mejor. Probablemente debería hacer algo similar con Java ahora.
Dos pequeños errores: 1<<atol(b[1])deberían ser 1L<<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 %ldpara imprimir números entre 2 ^ 31 y 2 ^ 32 correctamente.
G. Sliepen
2

Perl 5, 55 53 49 47 41 bytes

sprintf("%b",$_)=~/01/&&say for 0..2**<>

54 52 48 46 40 bytes, más uno para la -Ebandera 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.

msh210
fuente
2

C, 84 81 bytes

long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}

Esto 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

long i,j,k;
main()
{
    for(scanf("%ld",&j);++i<1L<<j;)
    {
        k=i|(i-1);
        if((k&(k+1)) == 0)
            printf("%d ",i);
    }
}
Alquimista
fuente
int64_tsolo se define si usted #include<stdint.h>. Asegurar que la operación de 64 bits requiere un long longtipo a un costo de 5 bytes.
chqrlie
Tenga en cuenta que invoca el comportamiento indefinido pasando long ipor %dformato. 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;}
chqrlie
@chqrlie Todos muy buenos puntos. Gracias.
Alchymist
1

Pyth, 20 17 16 bytes

f:.BT"10+1"ZU^2Q

Demo en vivo.

kirbyfan64sos
fuente
Simplemente puedes combinar "01". Excepto por 0, el binario repr. siempre comenzará con un 1.
Dennis
1

Python 2.7, 89 bytes

print[i for i in range(1,2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]

Creo que esto podría jugarse un poco.

Loovjo
fuente
@ mbomb007 Intenté eso, no funcionó.
Loovjo
@ mbomb007 ¿Estás usando Python 2.7?
Loovjo
¿Importa qué versión de 2.7? Lo ejecuto en repl.it (2.7.2) y no funciona, pero Ideone (2.7.10) sí. Sin embargo, podría ser un error en repl.it, no necesariamente una diferencia de versión.
mbomb007
Su programa imprime incorrectamente 0en la salida.
mbomb007
También 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 para 0sería la misma longitud (89), si la usa range(1,2**input()).
mbomb007
1

TI-BASIC, 34 32 30 bytes

Para una calculadora de la serie TI-83 + / 84 +.

For(X,5,e^(Ans
If log(sum(2=int(4fPart(X/2^randIntNoRep(1,Ans
Disp X
End

Para que un número contenga dos corridas de 1s, debe contener dos 10s 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á 2dónde hay a 10. 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^(Anscomo argumento final del For(bucle: siempre es mayor que 2^Ans, pero e^(es un token único, por lo que es un byte más corto.

Entrada / salida para N = 4:

4:prgmRUNSONES
               5
               9
              10
              11
              13

Entonces la calculadora arroja un error; la pantalla de error se ve así:

ERR:DOMAIN
1:Quit
2:Goto

Cuando se presiona 1, la pantalla de inicio se muestra nuevamente:

4:prgmRUNSONES
               5
               9
              10
              11
              13
           Error

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^14pueden no ser exactas. Si bien he verificado que los números más complicados 3*2^30-1y que 2^32-1se manejan correctamente, no he descartado la posibilidad de errores de redondeo. Sin embargo, me sorprendería si hubiera errores para cualquier entrada.

lirtosiast
fuente
¿Cómo cuentas 32 bytes? A mí me parece 70 (incluidas las nuevas líneas).
msh210
TI-BASIC está tokenizado; utiliza una codificación de caracteres patentada en la que todos estos comandos son de un byte cada uno y los otros son dos. Es el consenso de la comunidad puntuar con esta codificación; consulte meta.codegolf.stackexchange.com/a/4764/39328 para obtener más detalles.
lirtosiast
Oh genial Gracias para tu información.
msh210
1
  • esto no supera la respuesta de flawr pero no pude resistir el encanto de la pregunta

matlab(90)(70)

j=input('');for l=2:j-1,a=1;for k=l:-1:2,a=a+2^k;a:a+2^(k-1)-2,end,end

ejecución

4

ans =

5

ans =

9    10    11

ans =

13

principio

  • La serie de números es el resultado de la consiguiente tira de 1, que significa f (n, l) = 2 ^ l + 2 ^ (l + 1) + .... 2 ^ n

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)


Editar: desafortunadamente eso no lo hace jugar más al golf, pero quería agregar otro enfoque para procesar esta idea

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

@(n)setdiff(0:2^n-1,arrayfun(@(x)2^mod(x,(n+1)-fix(x/(n+1)))*(2^fix(x/(n+1))-1),0:(n+1)^2))
Abr001am
fuente
1

C, 103 102 bytes

long i,x;main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!printf("%ld,",i));x/=2);}

Expandiéndose (realmente contrayéndose) en la entrada G.Sliepen, aprovechando la observación xnor sobre el 01patrón en la representación binaria, pero usando solo funciones estándar y algunos cambios de bits.

Versión sin golf:

long i, x;
main(int a, char**b) {
    for (; ++i < 1L << atoi(b[1]);) {
        for (x = i; x > 4 && (x % 4 != 1 || !printf("%ld,", i)); x /= 2)
            ;
    }
}

El bucle interno busca iel patrón binario 01desplazándose iterativamente xhacia la derecha siempre que le queden 3 bits. printfdevuelve el número de caracteres impresos, por lo tanto, nunca 0, por lo que la prueba del bucle interno falla después del printf, evitando la necesidad de una breakinstrucción

C ++, 129 128 bytes

Adaptando la misma idea, la variante C ++ está aquí:

#include<iostream>
long i,x;int main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!(std::cout<<i<<','));x/=2);}

Técnicamente, debería hacer iuna long longoperación para asegurar la operación de 64 bits y calcular hasta 2^325 bytes adicionales, pero las plataformas modernas tienen entradas de 64 bits.

chqrlie
fuente
1

JavaScript ES6, 60 bytes

Código

n=>[...Array(1<<n).keys()].filter(g=x=>x>4?x%4==1|g(x>>1):0)

Pruébalo en línea!

Explicación

[...Array(1<<n).keys()]                                          Create an array of numbers from 0 to 2^n-1
                       .filter(                                  Find the numbers which meet criteria
                               g=x=>x>4?                  :0     If x is less than or equal to four return zero (false/invalid)
                                        x>4?x%4==1|              If the binary pattern ends with 01 return one (true/valid)
                                                   g(x>>1)       Otherwise bitshift right by one and try again
fəˈnɛtɪk
fuente
0

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.

x,c;main(n,v){n--;for(;c<1<<n;c++)for(v=0;v<32;v++)if(c&1<<v){if(x&&x<v&&printf("%d ",c))break;x=v+1;}}

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.

Jerry Jeremiah
fuente
0

PowerShell, 80 bytes

while([Math]::Pow(2,$args[0])-gt$n++){$n|?{[Convert]::ToString($n,2)-match"01"}}
Andrés
fuente
0

Python, 44 bytes

De acuerdo, esto probablemente podría ser más corto, pero es mi primer codegolf:

x=1
while True:
    if '01' in bin(x):
        print(x)
    x+=1

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.

Zachary Smith
fuente
1
Debe tomar la entrada ( input()es ideal) para obtener n, y luego solo contar hasta 2^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 usar mapo una comprensión de lista probablemente acortaría enormemente su código.
Mego
0

Otra respuesta matlab diferente de buena puntuación.

matlab 60 60(57)

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

ejecución

>> @(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

ans =

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

>> ans(5)

ans =

 5     9    10    11    13    17    18    19    20    21    22    23    25    26    27    29

  • La idea es recoger números x donde la representación binaria de - (x) +1 no contiene solo una ocurrencia de1

ejemplo:

0000111se rechaza porque ~ x = 1111, ~ x + 1 = 00001contiene un dígito = 1

0100111se acepta porque ~ x = 1011, ~ x + 1 = 0111contiene muchos 1

Abr001am
fuente