Números binarios entre padres

28

Si expresa algún número entero positivo en binario sin ceros a la izquierda y reemplaza cada 1con a (y cada 0con a ), ¿coincidirán todos los paréntesis?

En la mayoría de los casos no lo harán. Por ejemplo, 9 está 1001en binario, que se convierte ())(, donde solo coinciden los dos primeros paréntesis.

Pero a veces coinciden. Por ejemplo, 44 ​​está 101100en binario, que se convierte ()(()), donde todos los paréntesis izquierdos tienen un paréntesis derecho coincidente.

Escriba un programa o función que tome un entero positivo de base diez e imprima o devuelva un valor verdadero si la versión del número entre paréntesis binarios tiene todos los paréntesis coincidentes. Si no es así, imprima o devuelva un valor falso .

El código más corto en bytes gana.

Secuencia OEIS relacionada.

Verdaderos ejemplos debajo de 100:

2, 10, 12, 42, 44, 50, 52, 56

Ejemplos de falsa por debajo de 100:

1, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 49, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99
Pasatiempos de Calvin
fuente
55
Más OEIS
Mego
10
Hay una secuencia de todo ...
Arcturus

Respuestas:

8

TeaScript , 9 bytes 16 18 20 22 24

Guardado 2 bytes gracias a @ETHproductions

!x÷W(n,¢)

Woah Eso es corto Utiliza el enfoque de @ xnor. Esto usará la función de reemplazo recursivo ( W) que reemplazará todo 10igual a ()nada. Si la cadena está en blanco, está equilibrada.


Usando una versión de TeaScript hecha después de que se publicó este desafío, esto podría convertirse en 7 bytes:

!x÷W(n)

Sin golf

!xT(2)W(n,``)

Explicación

!      // NOT, returns true if empty string, else false
 xT(2)   // To binary
 W(n,``) // n is 10, reclusive replaces 10 or (), with nothing.
Downgoat
fuente
1
¡Excelente! Dos cosas que podrían ayudar: 1) Si es falso al subir, ya ha sido falso al bajar, por lo que no debería necesitar la primera tilde. 2) Creo que ~--ces falso en exactamente el mismo escenario que c--.
ETHproductions
@ETHproductions increíble, gracias! Ahora tengo 16 bytes
Downgoat
13

Pyth, 10 bytes

!uscG`T.BQ

Pruebe este conjunto de pruebas en el compilador Pyth.

Cómo funciona

              (implicit) Store the evaluated input in Q.
       .BQ    Return the binary string representation of Q.
 u            Reduce w/base case; set G to .BQ and begin a loop:
     `T         Return str(10) = "10".
   cG           Split G (looping variable) at occurrences of "10".
  s             Join the pieces without separators.
              Set G to the returned string.
              If the value of G changed, repeat the loop.
              This will eventually result in either an empty string or a
              non-empty string without occurrences of "10".
!             Return (and print) the logical NOT of the resulting string.
Dennis
fuente
Se me ocurrió el equivalente !u:G`Tk.BQ. Posiblemente más fácil de entender.
orlp
Sí, esa es ciertamente una opción más natural.
Dennis
8

Python2, 87 bytes

try:exec"print 1,"+"".join(["],","["][int(c)]for c in bin(input())[2:])
except:print 0

Una implementación terrible que abusa de los errores de sintaxis.

orlp
fuente
3
Este es el código de golf. Terrible es un cumplido.
corsiKa
8

JavaScript (ES6), 55 54 51 bytes

n=>![...n.toString(d=2)].some(c=>(d+=c*2-1)<2)*d==2

Bytes guardados gracias a @ Vɪʜᴀɴ y @xsot !

Explicación

n=>
  ![...n.toString(    // convert the input to an array of binary digits
    d=2)]             // d = current depth (+2)
      .some(c=>       // iterate through the digits
        (d+=c*2-1)    // increment or decrement the parenthesis depth
          <2          // if the depth goes negative, return false
      )*
        d==2          // if we finished at a depth of 0, return true
usuario81655
fuente
1
Puede guardar dos bytes eliminando lo que no necesita f=. También puede usar use en +clugar de c|0case para un número entero. También puedes usar el (+c?d++:d--)que es aún más corto
Downgoat
@ Vɪʜᴀɴ OK. ¿Hay algún tipo de guía sobre cuándo necesito usar f=? Debido a que muchas otras respuestas de JavaScript en el sitio nombran sus funciones.
user81655
1
Por lo general, solo necesita darle un nombre a la función si el desafío requiere que lo haga. De lo contrario, es seguro asumir que las funciones sin nombre están bien.
Alex A.
En Firefox, al ejecutar esto 11, regresa truecuando debería regresarfalse
Downgoat
2
No conozco JavaScript, pero intenté cortar algunos bytes y funciona en Chrome:n=>![...n.toString(d=2)].some(c=>(d+=c*2-1)<2)*d==2
xsot
7

Python 2, 45 bytes

f=lambda n,i=1:i*n>0<f(n/2,i+(-1)**n)or n<i<2

Una función recursiva. Lee dígitos binarios ndesde el final, manteniendo un recuento idel nivel de anidamiento actual de los padres. Si cae por debajo 0, rechazar. Cuando llegamos al inicio, verifica si el conteo es 0.

En realidad, comenzamos el conteo en i=1para que sea más fácil verificar si ha caído 0. El único caso de éxito de terminal es n==0y i==1, verificado con n<i<2. Forzamos esta verificación para que ocurra si n==0, o si icae 0, en cuyo caso falla automáticamente.

feersum ahorró dos bytes al reestructurar los casos no recursivos con desigualdades en cortocircuito.

xnor
fuente
3
Necesita más abuso condicional. f=lambda n,i=1:n>0<i*f(n/2,i+(-1)**n) or n<i<2, al menos, ahorra 1.
feersum
6

CJam, 11 bytes

ri2b"}{"f=~

Esto es un poco impuro: para los números que se pueden comparar con los padres, imprimirá uno o más bloques. Para los números que no se pueden sincronizar entre padres, se bloqueará sin imprimir nada en STDOUT. Si prueba esto en línea en el intérprete de CJam , tenga en cuenta que no distingue entre STDOUT y STDERR.

Dado que las cadenas no vacías / vacías son verdaderas / falsas en CJam y la salida impresa siempre es una cadena, podría decirse que cumple con las reglas. Con el costo adicional de 3 bytes más, para un total de 14 bytes , podemos dejar una cadena verdadera o falsa en la pila que se imprimirá:

Lri2b"}{"f=~]s

Esto todavía se bloquea para los números que no se pueden modificar entre padres, lo cual está permitido de manera predeterminada .

Pruebas de funcionamiento

$ cjam <(echo 'ri2b"}{"f=~') <<< 52 2>&-; echo
{{}{}}
$ cjam <(echo 'ri2b"}{"f=~') <<< 53 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 54 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 55 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 56 2>&-; echo
{{{}}}

Cómo funciona

ri          e# Read an integer from STDIN.
  2b        e# Push the array of its binary digits.
    "}{"f=  e# Replace 0's with }'s and 1's with {'s.
          ~ e# Evaluate the resulting string.
            e# If the brackets match, this pushes one or more blocks.
            e# If the brackets do not match, the interpreter crashes.

CJam, 15 bytes

ri2bs_,{As/s}*!

Pruebe este violín en el intérprete de CJam o verifique todos los casos de prueba a la vez .

Cómo funciona

ri               Read an integer from STDIN.
  2b             Push the array of its binary digits.
    s            Cast to string.
     _,          Push the string's length.
       {    }*   Do that many times:
        As/        Split at occurrences of "10".
           s       Cast to string to flatten the array of strings.
              !  Push the logical NOT of the result.
Dennis
fuente
1
maldita sea, apenas me vuelves a ganar ...
GamrCorps
6

Python, 51 bytes

lambda n:eval("'0b'==bin(n)"+".replace('10','')"*n)

Una función anónima. Evalúa una expresión que se parece a

'0b'==bin(n).replace('10','').replace('10','').replace('10','')...

Cada reemplazo elimina todo lo 10que corresponde (). Después de que se hayan realizado todos los reemplazos, la función devuelve si lo que queda es solo el prefijo binario 0b. Es más que suficiente hacer nreemplazos, ya que un knúmero de dígitos toma en la mayoría de los k/2pasos, y su valor es más 2**k.

xnor
fuente
4

Rubí, 40

->i{n='%0b'%i;1while n.slice!'10';n<?0}

Manipulación simple de cuerdas. Cae '10' hasta que no quede ninguno.

No es que Charles
fuente
4

En serio , 17 bytes

,;2@¡@`""9u$(Æ`nY

Salidas 0para falso y 1para verdadero. Pruébalo en línea .

Explicación:

,      get value from stdin
;      dupe top of stack
2@¡    pop a: push a string containing the binary representation of a (swapping to get order of operands correct)
@      swap top two elements to get original input back on top
`""9u$(Æ` define a function:
  ""     push empty string
  9u$    push "10" (push 9, add 1, stringify)
  (      rotate stack right by 1
  Æ      pop a,b,c: push a.replace(b,c) (replace all occurrences of "10" in the binary string with "")
n      pop f,a: call f a times
Y      pop a: push boolean negation of a (1 if a is falsey else 0)
Mego
fuente
4

Japt, 23 bytes

Japt es una versión abreviada de Ja vaScri pt . Interprete

Us2 a e@+X?++P:P-- &&!P

Esto me recuerda cuán lejos aún tiene que ir Japt en comparación con TeaScript. Después de renovar el intérprete en los próximos días, me gustaría agregar caracteres de "atajo" como los de Vɪʜᴀɴ.

Cómo funciona

       // Implicit: U = input number, P = empty string
Us2 a  // Convert U to base 2, then split the digits into an array.
e@     // Assert that every item X in this array returns truthily to:
 +X?   //  If X = 1,
 ++P   //   ++P. ++(empty string) returns 1.
 :P--  //  Otherwise, P--. Returns false if P is now -1.
&&!P   // Return the final result && !P (true if P is 0; false otherwise).
       // Implicit: output final expression

Poco después de este desafío, @ Vɪʜᴀɴ (ahora conocido como @Downgoat) me ayudó a implementar una función de reemplazo recursivo, como Wen la respuesta de TeaScript. Esto significa que este desafío ahora se puede hacer en solo 5 bytes:

!¢eAs  // Implicit: U = input integer, A = 10
 ¢     // Convert U to binary.
  eAs  // Recursively remove instances of A.toString().
!      // Return the logical NOT of the result (true only for the empty string).

¡Pruébalo en línea!

ETHproducciones
fuente
3

Mathematica, 49 bytes

(#~IntegerDigits~2//.{x___,1,0,y___}:>{x,y})=={}&
alephalpha
fuente
No puedo leer Mathematica. Explicación, por favor? :)
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Convierta el número en base 2 (como una lista), luego elimínelo repetidamente 1,0de la lista y pruebe si el resultado es una lista vacía.
alephalpha
3

Octava, 48 bytes

@(a)~((b=cumsum(2*dec2bin(a)-97))(end)|any(b<0))
alephalpha
fuente
3

C ++, 104 94 bytes

#include<iostream>
int n,c;int main(){for(std::cin>>n;n&c>=0;n>>=1)c+=n&1?-1:1;std::cout<<!c;}

Ejecutar con este compilador , debe especificar la entrada estándar antes de ejecutar.

Explicación

  • Las declaraciones fuera de main se inicializan a 0.
  • Leer un decimal se convierte implícitamente en binario, porque esta es una computadora.
  • Verificamos bits / paréntesis de derecha a izquierda debido a n>>=1.
  • c+=n&1?-1:1mantiene el recuento de paréntesis abierto ).
  • n&c>=0 se detiene cuando solo quedan 0 iniciales o los paréntesis se cierran más de lo que se abren.
Linus
fuente
3

Haskell, 49 46 bytes

0#l=l==1
_#0=2<1
n#l=div n 2#(l+(-1)^n)
f=(#1)

Ejemplo de uso: f 13-> False.

Estoy siguiendo el nivel de anidación lcomo muchas otras respuestas. Sin embargo, el caso "equilibrado" está representado por 1, así que el caso "más- que )- (" lo es 0.

PD: encontré el ajuste del nivel de anidación l+(-1)^nen la respuesta de xnor .

nimi
fuente
El signumparece demasiado complicado, ¿qué tal solo _#0=1<0?
xnor
@xnor: sí, gracias.
nimi
¿Por qué no en l>0lugar de l==1?
Michael Klein
@MichaelKlein: porque solo l==1está equilibrado. Si l>1, los paréntesis no están equilibrados.
nimi
@nimi Ya veo, interpreté mal cómo funciona
Michael Klein
3

Python 2, 60 57 56 55 53 52 50 49 bytes

n=input()
i=1
while i*n:i+=1|n%-2;n/=2
print i==1

¡Gracias a xnor por guardar dos bytes y feersum por llevar el conteo final de bytes a 49!

Explicación

El número de entrada n, se procesa desde su bit menos significativo. ies un contador que realiza un seguimiento del número de 0 y 1. Tenga en cuenta que se inicializa 1para guardar un byte. El ciclo abortará antes de nllegar a 0 si el número de 1 excede el número de 0 ( i<=0).

Para que los paréntesis sean equilibrados, se requieren dos condiciones:

  • El número de 0 y 1 es igual (es decir i==1)
  • El número de 1 nunca excede el número de 0 durante este proceso (es decir, el ciclo no aborta prematuramente n==0). Editar: me di cuenta de que esta condición no es necesaria, ya que idebe ser no positiva si n!=0la condición anterior es suficiente.
xsot
fuente
Si iy nno son negativos, entonces lo i==n==0es i+n==0.
orlp
ipuede ser negativo si el ciclo aborta prematuramente.
xsot
En realidad, i|n==0siempre debería funcionar.
orlp
Gran sugerencia, esa línea se ve mejor ahora.
xsot
while i*ndebería funcionar
xnor
3

JavaScript ES5, 118 87 85 82 77 bytes

Técnica interesante en mi opinión. Menos muchísimo, gracias a @ETHproductions y @NotthatCharles

function p(x){x=x.toString(2);while(/10/.test(x))x=x.replace(10,"");return!x}

JavaScript ES6, 77 57 56 54 bytes

-21 bytes a ETHproductions.

x=>[...x=x.toString(2)].map(_=>x=x.replace(10,""))&&!x
Conor O'Brien
fuente
Me gusta la traducción a paréntesis. Sin embargo, si lo deja como 1s y 0s, es un poco más corto:function p(x){x=x.toString(2);r=/10/;while(x.search(r)>=0){x=x.replace(r,"")}return!x}
ETHproductions
@ETHproductions ¡Buen punto! Creo que dejaré el otro código en la parte inferior, realmente me gusta el algoritmo ^ _ ^ ¡Gracias amigo!
Conor O'Brien
La versión ES6 todavía puede jugarse un montón: x=>([...x=x.toString(2)].map(_=>x=x.replace(/10/,"")),!x)el truco es mover el ciclo while a un .map, ya que nunca hay más '10 en una entrada que su longitud.
ETHproductions
@ETHproductions Gracias de nuevo ^ _ ^ Buen truco con map.
Conor O'Brien
No hay problema :) Por cierto, otro byte se puede guardar con un truco que edc65 usa todo el tiempo: x=>[...x=x.toString(2)].map(_=>x=x.replace(/10/,""))&&!xIDK si puede acortarse .
ETHproductions
2

D, 209 170 bytes

import std.stdio;import std.format;import std.conv;void main(char[][]a){string b=format("%b",to!int(a[1]));int i;foreach(c;b){i+=c=='1'?1:-1;if(i<0)break;}writeln(i==0);}

Esto hace exactamente lo que se supone que debe hacer sin adiciones o beneficios.

fase
fuente
2

C, 67 bytes

n;main(i){for(scanf("%d",&n);n*i;n/=2)i+=1-n%2*2;putchar(48+!~-i);}

Más o menos un puerto de mi presentación de Python.

xsot
fuente
2

Prólogo, 147 bytes

b(N,[X|L]):-N>1,X is N mod 2,Y is N//2,b(Y,L).
b(N,[N]).
q([H|T],N):-N>=0,(H=0->X is N+1;X is N-1),q(T,X).
q([],N):-N=0.
p(X):-b(X,L),!,q(L,0).

Cómo funciona

b(N,[X|L]):-N>1,X is N mod 2,Y is N//2,b(Y,L).
b(N,[N]).

Convierte el número decimal N en su representación binaria como una lista (invertida). Sentido:

b(42,[0,1,0,1,0,1]) is true

Luego:

q([H|T],N):-N>=0,(H=0->X is N+1;X is N-1),q(T,X).
q([],N):-N=0.

Recurre sobre la lista [H | T] aumentando N si el elemento principal es 0, de lo contrario disminuyéndolo.
Si N en cualquier punto se vuelve negativo o si N al final no es 0, devuelve falso, de lo contrario es verdadero.

El corte en

p(X):-b(X,L),!,q(L,0).

Existe para evitar el retroceso y encontrar soluciones no binarias para las

pruebas b (N, [N])
Pruébelo en línea aquí
Ejecútelo con una consulta como:

p(42).
Emigna
fuente
2

PowerShell, 106 bytes

param($a)$b=[convert]::ToString($a,2);1..$b.Length|%{if($b[$_-1]%2){$c++}else{$c--}if($c-lt0){0;exit}};!$c

No voy a ganar ninguna competencia de corta duración, eso es seguro. Pero oye, ¿al menos está superando a Java?

Utiliza la llamada .NET muy larga [convert]::ToString($a,2)para convertir nuestro número de entrada en una cadena que representa los dígitos binarios. Luego for-loop a través de esa cadena con 1..$b.length|%{..}. Cada ciclo, si nuestro dígito es un 1(evaluado en %2lugar de -eq1guardar un par de bytes), incrementamos nuestro contador; de lo contrario, lo decrementamos. Si alguna vez llegamos negativo, lo que significa que había más )de lo (encontrado hasta ahora, por lo que la salida 0y exit. Una vez que pasamos por el ciclo, $ces uno 0o algún número >0, por lo que tomamos el no lógico !del mismo, que obtiene salida.

Esto tiene la peculiaridad de generar resultados 0si los elementos parentales no coinciden porque tenemos más ), pero generar resultados Falsesi los elementos parentales no coinciden porque tenemos más (. Esencialmente declaraciones falsas funcionalmente equivalentes, simplemente interesantes. Si todos los parens coinciden, salidas True.

AdmBorkBork
fuente
Bien, seguro. (Bueno, si puedo solucionar la molesta duda de que estoy resolviendo el problema incorrecto, lo haré).
TessellatingHeckler
1

GNU Sed (con extensión eval), 27

s/.*/dc -e2o&p/e
:
s/10//
t

Sed realmente no tiene una idea definida de verdad y falsey, por lo que aquí estoy afirmando que la cadena vacía significa verdad y todas las demás cadenas significan falsey.

Si esto no es aceptable, entonces podemos hacer lo siguiente:

GNU Sed (con extensión eval), 44

s/.*/dc -e2o&p/e
:
s/10//
t
s/.\+/0/
s/^$/1/

Esto genera 1 para verdad y 0 en caso contrario.

Trauma digital
fuente
1

ES (ESMin), 21 caracteres / 43 bytes

ô⟦ïßḂ]Ĉ⇀+$?⧺Ḁ:Ḁ‡)⅋!Ḁ)

Try it here (Firefox only).

Tenga en cuenta que esto utiliza variables predefinidas a números (específicamente 2 y 0). Hay variables numéricas predefinidas de 0 a 256.

19 caracteres / 40 bytes, no competitivos

⟦ïßḂ]Ĉ⇀+$?⧺Ḁ:Ḁ‡)⅋!Ḁ

Try it here (Firefox only).

Decidí implementar la salida implícita ... Sin embargo, los formularios de salida anteriores todavía son compatibles, por lo que obtienes varias opciones de salida.

Mama Fun Roll
fuente
porque todos miden por recuento de char
fase
1

Java, 129 131 bytes

boolean T(int i){int j=0,k=0;for(char[]a=Integer.toString(i,2).toCharArray();j<a.length&&k>=0;j++){k+=a[j]=='1'?1:-1;}return k==0;}

Probablemente se puede acortar. Explicación por venir. ¡Gracias a Geobits por 4 bytes de descuento!

GamrCorps
fuente
¿Es posible combinar int k=0;con int j=0;?
ETHproductions
No, j es una variable interna en el bucle for y no se puede hacer referencia fuera de él.
GamrCorps
Sin embargo, debería poder combinar de la otra manera: int k=0,j=0;for(...luego podría poner la char[]declaración dentro del inicializador de bucle para guardar también un punto y coma.
Geobits
El mayor problema es que esto da falsos positivos. Devuelve verdadero para 9, 35, 37, 38, por ejemplo .
Geobits
@Geobits oops, ni siquiera me di cuenta de eso, se solucionará cuando tenga la oportunidad.
GamrCorps
1

C ++, 61 bytes

Creo que la respuesta actual de C ++ es incorrecta: devuelve un valor verdadero para todos los números pares, p. Ej. 4. Descargo de responsabilidad: no pude usar el compilador mencionado, así que usé g ++ 4.8.4. El problema radica en el uso del operador AND binario en lugar del AND lógico que se usa para romper temprano cuando el número de paréntesis de cierre excede el número de paréntesis de apertura. Este enfoque podría funcionar si truese representa como una palabra con un patrón de bits verdadero. En mi sistema, y ​​probablemente en la mayoría de los otros sistemas, truees equivalente a 1; Solo una parte es cierta. Además, n/=2es más corto que n>>=1. Aquí hay una versión mejorada como una función:

int f(int n,int c=0){for(;c>=0&&n;n/=2)c+=n&1?-1:1;return c;}
vysar
fuente
0

𝔼𝕊𝕄𝕚𝕟 (muy poco competitivo), 6 caracteres / 8 bytes

!ïⓑĦⅩ

Try it here (Firefox only).

He decidido volver a visitar este desafío después de mucho, mucho tiempo. 𝔼𝕊𝕄𝕚𝕟 ha mejorado mucho.

La razón por la que esta es una respuesta separada es porque las 2 versiones son casi completamente diferentes.

Explicación

Convierte la entrada a binario, reemplaza recursivamente instancias de 10, luego verifica si el resultado es una cadena vacía.

Mama Fun Roll
fuente
0

C # 98 bytes

bool f(int m){int i=0;foreach(char s in Convert.ToString((m),2)){if(s=='1')i+=2;i--;}return i==0;}

Abierto para cualquier sugerencia. me gusta este desafío, aunque sea antiguo

downrep_nation
fuente