Números binários parentificáveis

28

Se você expressar algum número inteiro positivo em binário sem zeros à esquerda e substituir every 1por a (e every 0por a ), todos os parênteses serão iguais?

Na maioria dos casos, eles não vão. Por exemplo, 9 está 1001em binário, que se torna ())(, onde apenas os dois primeiros parênteses correspondem.

Mas às vezes eles combinam. Por exemplo, 44 ​​está 101100em binário, que se torna ()(()), onde todos os parênteses à esquerda têm um parêntese à direita correspondente.

Escreva um programa ou função que receba um número inteiro positivo de base dez e imprima ou retorne um valor verdadeiro se a versão entre parênteses binários do número tiver todos os parênteses correspondentes. Caso contrário, imprima ou retorne um valor falso .

O código mais curto em bytes vence.

Sequência OEIS relacionada.

Exemplos de verdade abaixo de 100:

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

Exemplos de falsas abaixo 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
Passatempos de Calvin
fonte
5
Mais OEIS
Mego
10
Há uma seqüência para tudo ...
Arcturus

Respostas:

8

TeaScript , 9 bytes 16 18 20 22 24

Economizou 2 bytes graças a @ETHproductions

!x÷W(n,¢)

Woah. Isso é curto. Usa a abordagem do @ xnor. Isso usará a função de substituição recursiva ( W), que substituirá todos 10iguais ()por nada. Se a string estiver em branco, ela será equilibrada.


O uso de uma versão do TeaScript feita após o lançamento deste desafio pode se transformar em 7 bytes:

!x÷W(n)

Ungolfed

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

Explicação

!      // NOT, returns true if empty string, else false
 xT(2)   // To binary
 W(n,``) // n is 10, reclusive replaces 10 or (), with nothing.
Downgoat
fonte
1
Excelente! Duas coisas que podem ajudar: 1) Se é falso ao subir, já está caindo, então você não precisa do primeiro til. 2) Eu acredito que ~--cé falso exatamente no mesmo cenário que c--.
ETHproductions
@ETHproductions incrível, obrigado! Agora estou com 16 bytes
Downgoat
13

Pitão, 10 bytes

!uscG`T.BQ

Experimente esta suíte de testes no Pyth Compiler.

Como 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
fonte
Eu vim com o equivalente !u:G`Tk.BQ. Indiscutivelmente mais fácil de entender.
orlp
Sim, essa é certamente uma escolha mais natural.
Dennis
8

Python2, 87 bytes

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

Uma implementação terrível que abusa de erros de sintaxe.

orlp
fonte
3
Isso é código de golfe. Terrível é um elogio.
corsiKa
8

JavaScript (ES6), 55 54 51 bytes

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

Bytes salvos graças a @ Vɪʜᴀɴ e @xsot !

Explicação

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
user81655
fonte
1
Você pode salvar dois bytes removendo o não necessário f=. Você também pode usar use em +cvez de c|0maiúsculas e minúsculas para um número inteiro. Você também pode usar o (+c?d++:d--)que é ainda mais curto
Downgoat 16/11/2015
@ OK. Existe algum tipo de guia sobre quando eu preciso usar f=? Porque muitas outras respostas JavaScript no site nomeiam suas funções.
user81655
1
Normalmente, você só precisa dar um nome à função se o desafio exigir que você o faça. Caso contrário, é seguro assumir que funções sem nome estão corretas.
Alex A.
No Firefox, executando isso por 11, retornos truequando ele deve retornarfalse
Downgoat
2
Eu não sei javascript, mas tentei cortar alguns bytes e ele funciona no chrome:n=>![...n.toString(d=2)].some(c=>(d+=c*2-1)<2)*d==2
xsot 16/11/2015
7

Python 2, 45 bytes

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

Uma função recursiva. Lê dígitos binários a npartir do final, mantendo uma contagem ido nível de aninhamento atual das parênteses. Se estiver abaixo 0, rejeite. Quando chegamos ao início, verifica se a contagem é 0.

Na verdade, começamos a contagem em i=1para facilitar a verificação se ela caiu 0. O único caso de sucesso do terminal é n==0e i==1, verificado com n<i<2. Forçamos essa verificação a ocorrer se n==0, ou se icair 0, caso em que falha automaticamente.

feersum economizou dois bytes reestruturando os casos não recursivos com desigualdades para causar um curto-circuito.

xnor
fonte
3
Precisa de mais abuso condicional. f=lambda n,i=1:n>0<i*f(n/2,i+(-1)**n) or n<i<2, pelo menos, salva 1.
feersum 16/11/2015
6

CJam, 11 bytes

ri2b"}{"f=~

Isso é um pouco imundo: para números com parênteses, ele imprimirá um ou mais blocos. Para números que não possam ser trocados entre parênteses, ele trava sem imprimir nada no STDOUT. Se você tentar isso on-line no intérprete CJam , lembre-se de que ele não faz distinção entre STDOUT e STDERR.

Como cadeias não vazias / vazias são verdadeiras / falsas no CJam e a saída impressa é sempre uma cadeia, é possível que ela esteja em conformidade com as regras. Com o custo adicional de mais 3 bytes, para um total de 14 bytes , podemos realmente deixar uma sequência de verdade ou falsidade na pilha que será impressa:

Lri2b"}{"f=~]s

Isso ainda trava para números não passíveis de parentalidade, o que é permitido por padrão .

Execuções de teste

$ 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
{{{}}}

Como 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}*!

Experimente este violino no intérprete CJam ou verifique todos os casos de teste de uma só vez .

Como 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
fonte
1
danado, você mal me bater de novo ....
GamrCorps
6

Python, 51 bytes

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

Uma função anônima. Avalia para uma expressão que se parece com

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

Cada substituição remove tudo 10, que corresponde a (). Depois que todas as substituições foram feitas, a função retorna se o que resta é apenas o prefixo binário 0b. É mais do que suficiente fazer nsubstituições, já que um knúmero de dois dígitos leva na maioria das k/2etapas e seu valor é maior 2**k.

xnor
fonte
4

Ruby, 40

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

Manipulação simples de strings. Larga '10' até não sobrar mais nada.

Não que Charles
fonte
4

Sério , 17 bytes

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

Saídas 0para false e 1true. Experimente online .

Explicação:

,      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
fonte
4

Japonês, 23 bytes

Japt é uma versão abreviada do Ja vaScri pt . Intérprete

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

Isso me lembra o quão longe o Japt ainda não foi comparado ao TeaScript. Depois de renovar o intérprete nos próximos dias, gostaria de adicionar caracteres de "atalho" como o Vɪʜᴀɴ.

Como 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

Logo após esse desafio, o @ Vɪʜᴀɴ (agora conhecido como @Downgoat) me ajudou a implementar um recurso de substituição recursiva, como Wna resposta do TeaScript. Isso significa que esse desafio agora pode ser feito em apenas 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).

Teste online!

ETHproductions
fonte
3

Mathematica, 49 bytes

(#~IntegerDigits~2//.{x___,1,0,y___}:>{x,y})=={}&
alefalpha
fonte
Não sei ler o Mathematica. Explicação, por favor? :)
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Converta o número na base 2 (como uma lista), remova-a repetidamente 1,0da lista e teste se o resultado é uma lista vazia.
alephalpha
3

Oitava, 48 bytes

@(a)~((b=cumsum(2*dec2bin(a)-97))(end)|any(b<0))
alefalpha
fonte
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;}

Executar com este compilador , deve especificar a entrada padrão antes de executar.

Explicação

  • As declarações fora do main são inicializadas como 0.
  • A leitura de um decimal converte implicitamente em binário, porque este é um computador.
  • Verificamos bits / parênteses da direita para a esquerda por causa de n>>=1.
  • c+=n&1?-1:1mantém a contagem de parênteses abertos ).
  • n&c>=0 para quando apenas os 0s iniciais permanecem ou os parênteses fecham mais do que abrem.
Linus
fonte
3

Haskell, 49 46 bytes

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

Exemplo de uso: f 13-> False.

Estou acompanhando o nível de aninhamento lcomo muitas outras respostas. No entanto, o caso "equilibrado" é representado por 1, assim como o caso "mais- )que- (" 0.

PS: encontrou o ajuste do nível de aninhamento l+(-1)^nna resposta do xnor .

nimi
fonte
O signumparece muito complicado, como sobre apenas _#0=1<0?
Xnor
@ xnor: sim, obrigado.
N
Por que não em l>0vez de l==1?
Michael Klein
@ MichaelKlein: porque apenas l==1é equilibrado. Se l>1, os parênteses estão desequilibrados.
nimi
@nimi eu vejo, eu mal interpretado como ele 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

Agradecemos ao xnor por salvar dois bytes e feersum por elevar a contagem final de bytes para 49!

Explicação

O número de entrada,, né processado a partir do seu bit menos significativo. ié um contador que controla o número de 0 e 1. Observe que ele foi inicializado 1para salvar um byte. O loop será interrompido antes de nchegar a 0 se o número de 1s exceder o número de 0s ( i<=0).

Para que os parênteses sejam equilibrados, são necessárias duas condições:

  • O número de 0 e 1 é igual (ie i==1)
  • O número de 1s nunca excede o número de 0s durante esse processo (ou seja, o loop não interrompe prematuramente n==0). Edit: eu percebi que esta condição não é necessária, pois ideve ser não positiva, se n!=0a condição anterior for suficiente.
xsot
fonte
Se ie nnão são negativos, então i==n==0é i+n==0.
orlp
ipode ser negativo se o loop for interrompido prematuramente.
Xsot #
Na verdade, i|n==0deve sempre funcionar.
orlp
Ótima sugestão, essa linha parece melhor agora.
Xsot #
while i*ndeve funcionar
xnor
3

JavaScript ES5, 118 87 85 82 77 bytes

Técnica interessante na minha opinião. Menos muito, graças a @ETHproductions e @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 em ETHproductions.

x=>[...x=x.toString(2)].map(_=>x=x.replace(10,""))&&!x
Conor O'Brien
fonte
Eu gosto da tradução entre parênteses. No entanto, se você deixar como 1s e 0s, é um pouco mais curto:function p(x){x=x.toString(2);r=/10/;while(x.search(r)>=0){x=x.replace(r,"")}return!x}
ETHproductions
@ETHproductions Bom ponto! Acho que vou deixar o outro código na parte inferior, gosto muito do algoritmo ^ _ ^ Obrigado companheiro!
Conor O'Brien
A versão ES6 ainda pode ser um jogo de golfe: x=>([...x=x.toString(2)].map(_=>x=x.replace(/10/,"")),!x)o truque é mover o loop while para um .map, já que nunca há mais dez em uma entrada do que seu comprimento.
ETHproductions
@ETHproductions Obrigado novamente ^ _ ^ Bom truque com map.
Conor O'Brien
Não tem problema :) BTW, outro byte pode ser salvo com um truque que o edc65 usa o tempo todo: x=>[...x=x.toString(2)].map(_=>x=x.replace(/10/,""))&&!xIDK, se puder ficar mais curto.
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);}

Isso faz exatamente o que deve ser feito sem acréscimos ou benefícios.

Estágio
fonte
2

C, 67 bytes

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

Praticamente uma porta da minha submissão python.

xsot
fonte
2

Prolog, 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).

Como funciona

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

Converte o número decimal N na sua representação binária como uma lista (invertida). Significado:

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

Então:

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

Recursa na lista [H | T] aumentando N se o elemento principal for 0, caso contrário, diminuindo-o.
Se N em algum momento se tornar negativo ou se N no final não for 0, retorne false, caso contrário true.

O corte

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

Existe para evitar retroceder e encontrar soluções não binárias para

testes b (N, [N])
Experimente aqui online aqui
Execute-o com uma consulta como:

p(42).
Emigna
fonte
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

Não vai ganhar nenhuma competição de menor duração, isso é certo. Mas ei, pelo menos está batendo em Java?

Usa a chamada .NET muito longa [convert]::ToString($a,2)para converter nosso número de entrada em uma sequência que representa os dígitos binários. Em seguida, fazemos um loop forçado nessa string com 1..$b.length|%{..}. Cada loop, se nosso dígito é a 1(avaliado com %2mais do que -eq1para salvar alguns bytes), incrementamos nosso contador; caso contrário, nós a diminuímos. Se alguma vez alcançarmos negativo, isso significa que houve mais do )que o (encontrado até agora, então produzimos 0e exit. Quando terminamos o loop, $cé um 0ou algum número >0, então tomamos a lógica - não !disso, que obtém a saída.

Isso tem a peculiaridade de produzir 0se os parênteses são incompatíveis porque temos mais ), mas gerar Falsese os parênteses são incompatíveis porque temos mais (. Declarações falsas essencialmente funcionais equivalentes, apenas interessantes. Se todos os parênteses coincidirem, será gerado True.

AdmBorkBork
fonte
OK, claro. (Bem, se eu puder resolver a dúvida incômoda de que estou resolvendo o problema errado, resolverei).
usar o seguinte
1

GNU Sed (com extensão eval), 27

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

Sed realmente não tem uma idéia definida de truth e falsey, então aqui estou afirmando que a string vazia significa truth e todas as outras strings significam falsey.

Se isso não for aceitável, podemos fazer o seguinte:

GNU Sed (com extensão eval), 44

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

Isso gera 1 para verdade e 0 caso contrário.

Trauma Digital
fonte
1

ES (ESMin), 21 caracteres / 43 bytes

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

Try it here (Firefox only).

Observe que isso usa variáveis ​​predefinidas para números (especificamente 2 e 0). Existem variáveis ​​numéricas predefinidas de 0 a 256.

19 caracteres / 40 bytes, não competitivo

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

Try it here (Firefox only).

Decidiu implementar saída implícita ... No entanto, os formulários de saída anteriores ainda são suportados, então você obtém várias opções de saída!

Mama Fun Roll
fonte
porque todo mundo mede pela contagem de caracteres
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;}

Provavelmente pode ser reduzido. Explicação para vir. Graças a Geobits por 4 bytes de desconto!

GamrCorps
fonte
É possível combinar int k=0;com int j=0;?
ETHproductions
Não, j é uma variável interna no loop for e não pode ser referenciada fora dele.
GamrCorps
Porém, você deve poder combinar de outra maneira: int k=0,j=0;for(...Depois, você pode colocar a char[]declaração dentro do inicializador de loop para salvar também um ponto-e-vírgula.
Geobits
O maior problema é que isso gera falsos positivos. Retorna true para 9, 35, 37, 38, por exemplo .
Geobits
@ Geobits oops, eu nem percebi isso, vai consertar quando tiver uma chance.
GamrCorps
1

C ++, 61 bytes

Eu acho que a resposta atual do C ++ está errada: ele retorna um valor verdadeiro para todos os números pares, por exemplo, 4. Isenção de responsabilidade: não consegui usar o compilador mencionado, então usei o g ++ 4.8.4. O problema está no uso do operador AND binário em vez do AND lógico, que é usado para interromper cedo quando o número de parênteses de fechamento excede o número de parênteses de abertura. Essa abordagem pode funcionar se truefor representada como uma palavra com um padrão de bits totalmente verdadeiro. No meu sistema, e provavelmente na maioria dos outros sistemas, trueé equivalente a 1; apenas um bit é verdadeiro. Além disso, n/=2é menor que n>>=1. Aqui está uma versão aprimorada como uma função:

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

𝔼𝕊𝕄𝕚𝕟 (muito incompetente), 6 caracteres / 8 bytes

!ïⓑĦⅩ

Try it here (Firefox only).

Decidi revisitar esse desafio depois de muito, muito tempo. G ficou muito melhor.

A razão pela qual essa resposta é separada é porque as duas versões são quase completamente diferentes.

Explicação

Converte a entrada em binário, substitui recursivamente as instâncias de 10 e verifica se o resultado é uma sequência vazia.

Mama Fun Roll
fonte
0

Bytes C # 98

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

aberto para sugestões. Eu gosto deste desafio, mesmo que seja antigo

downrep_nation
fonte