Jeśli wyrazisz pewną liczbę całkowitą dodatnią w postaci binarnej bez zer wiodących i zamienisz każdą na 1a, (a każdą na 0a ), to czy wszystkie nawiasy się zgadzają?

W większości przypadków nie będą. Na przykład 9 ma 1001postać binarną, która staje się tym ())(, gdzie pasują tylko dwa pierwsze nawiasy.

Ale czasami będą pasować. Na przykład 44 ma postać 101100binarną, co oznacza ()(()), że wszystkie lewe nawiasy mają pasujący prawy nawias.

Napisz program lub funkcję, która przyjmuje dodatnią liczbę całkowitą dziesiętną i wypisuje lub zwraca prawdziwą wartość, jeśli wersja liczby w nawiasach binarnych ma wszystkie pasujące nawiasy. Jeśli nie, wydrukuj lub zwróć wartość fałszowania .

Najkrótszy kod w bajtach wygrywa.

Powiązana sekwencja OEIS.

Prawdziwe przykłady poniżej 100:

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

Przykłady Falsy poniżej 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

TeaScript , 9 bajtów 16 18 20 22 24

Zaoszczędź 2 bajty dzięki @ETHproductions

!x÷W(n,¢)

Łał To krótko. Wykorzystuje podejście @ xnor. Spowoduje to użycie funkcji zastępowania rekurencyjnego ( W), która zastąpi wszystko 10równe ()zeru. Jeśli łańcuch jest pusty, jest zrównoważony.

Używanie wersji TeaScript wykonanej po opublikowaniu tego wyzwania może mieć 7 bajtów:

!x÷W(n)

Nie golfił

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

Wyjaśnienie

!      // NOT, returns true if empty string, else false
 xT(2)   // To binary
 W(n,``) // n is 10, reclusive replaces 10 or (), with nothing.

Pyth, 10 bajtów

!uscG`T.BQ

Wypróbuj ten zestaw testów w kompilatorze Pyth.

Jak to działa

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

Python2, 87 bajtów

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

Straszna implementacja, która nadużywa błędów składniowych.

JavaScript (ES6), 55 54 51 bajtów

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

Zapisane bajty dzięki @ Vɪʜᴀɴ i @xsot !

Wyjaśnienie

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

Python 2, 45 bajtów

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

Funkcja rekurencyjna. Odczytuje cyfry binarne nod końca, zachowując ibieżący poziom zagnieżdżenia parens. Jeśli spadnie poniżej 0, odrzuć. Kiedy osiągniemy początek, sprawdza, czy liczba jest 0.

W rzeczywistości zaczynamy od zliczenia, i=1aby ułatwić sprawdzenie, czy do niego doszło 0. Jedynym przypadkiem sukcesu terminalu jest n==0i i==1, sprawdzone za pomocą n<i<2. Wymuszamy sprawdzenie, które nastąpi n==0, lub jeśli ido niego wpadnie 0, w którym to przypadku automatycznie się nie powiedzie.

feersum zaoszczędziło dwa bajty, restrukturyzując przypadki nierekurencyjne z nierównościami do zwarcia.

CJam, 11 bajtów

ri2b"}{"f=~

Jest to odrobinę nieczyste: w przypadku liczb, które można zmienić dla rodzica, wydrukuje jeden lub więcej bloków. W przypadku numerów, które nie podlegają ochronie rodzicielskiej, nastąpi awaria bez drukowania niczego do STDOUT. Jeśli wypróbujesz to online w interpretatorze CJam , pamiętaj, że nie rozróżnia on STDOUT i STDERR.

Ponieważ niepuste / puste ciągi znaków w CJam są zgodne z prawdą / fałszem, a wydruk jest zawsze ciągiem, prawdopodobnie jest zgodny z regułami. Przy dodatkowym koszcie 3 kolejnych bajtów, w sumie 14 bajtów , możemy faktycznie pozostawić ciąg stosu prawdy lub fałszu na stosie, który zostanie wydrukowany:

Lri2b"}{"f=~]s

To nadal zawiesza się w przypadku numerów, które nie podlegają zmianie dla rodzica, co jest domyślnie dozwolone .

Testy przebiegają

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

Jak to działa

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 bajtów

ri2bs_,{As/s}*!

Wypróbuj to skrzypce w interpretatorze CJam lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Jak to działa

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.

Python, 51 bajtów

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

Anonimowa funkcja. Ocenia wyrażenie, które wygląda

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

Każda wymiana usuwa wszystkie 10, które odpowiadają (). Po dokonaniu wszystkich zamian funkcja zwraca, czy pozostał tylko binarny prefiks 0b. nZastępowanie jest więcej niż wystarczające , ponieważ kcyfra-cyfra wymaga co najwyżej kilku k/2kroków, a jej wartość jest największa 2**k.

Ruby, 40

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

Prosta manipulacja ciągiem. Upuszcza „10”, dopóki nie zostanie żaden.

Poważnie , 17 bajtów

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

Dane wyjściowe 0dla false i 1true. Wypróbuj online .

Wyjaśnienie:

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

Japt, 23 bajty

Japt to skrócona wersja Ja vaScri pt . Interpretator

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

To przypomina mi, jak daleko Japt musi jeszcze iść w porównaniu do TeaScript. Po przeróbce interpretera w ciągu najbliższych kilku dni chciałbym dodać znaki „skrótowe”, takie jak Vɪʜᴀɴ.

Jak to działa

       // 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

Krótko po tym wyzwaniu @ Vɪʜᴀɴ (obecnie znany jako @Downgoat) pomógł mi zaimplementować funkcję zastępowania rekurencyjnego, jak Ww odpowiedzi TeaScript. Oznacza to, że wyzwanie można teraz wykonać w zaledwie 5 bajtach:

!¢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).

Przetestuj online!

Mathematica, 49 bajtów

(#~IntegerDigits~2//.{x___,1,0,y___}:>{x,y})=={}&

Oktawa, 48 bajtów

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

C ++, 104 94 bajty

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

Uruchom z tym kompilatorem , musi określić standardowe wejście przed uruchomieniem.

Wyjaśnienie

• Deklaracje poza głównym inicjują na 0.
• Czytanie dziesiętne domyślnie konwertuje na binarne, ponieważ jest to komputer.
• Z tego powodu sprawdzamy bity / nawiasy od prawej do lewejn>>=1 .
• c+=n&1?-1:1utrzymuje liczbę otwartych nawiasów ).
• n&c>=0 zatrzymuje się, gdy pozostają tylko wiodące zera lub nawias zamyka się bardziej niż otwiera.

Haskell, 49 46 bajtów

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

Przykład użycia: f 13-> False.

Śledzę poziom zagnieżdżenia, lpodobnie jak wiele innych odpowiedzi. Jednak przypadek „zrównoważony” jest reprezentowany przez 1, tak więc przypadek „bardziej )niż niż (” 0.

PS: znaleziono dopasowanie poziomu zagnieżdżenia l+(-1)^nw odpowiedzi xnora .

Python 2, 60 57 56 55 53 52 50 49 bajtów

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

Dzięki xnor za zaoszczędzenie dwóch bajtów i feersum za doprowadzenie końcowej liczby bajtów do 49!

Wyjaśnienie

Numer wejściowy n, jest przetwarzany z jego najmniej znaczącego bitu. ijest licznikiem, który śledzi liczbę zer i jedynek. Zauważ, że inicjowanie polega 1na zapisaniu bajtu. Pętla zostanie przerwana, zanim nosiągnie 0, jeśli liczba 1 przekroczy liczbę 0 ( i<=0).

Aby nawiasy były zrównoważone, wymagane są dwa warunki:

• Liczba zer i jedynek jest równa (tj. i==1)
• Liczba 1 nigdy nie przekracza liczby 0 podczas tego procesu (tzn. Pętla nie przerywa przedwcześnie, więc n==0). Edycja: Zdałem sobie sprawę, że ten warunek nie jest konieczny, ponieważ imusi być nie dodatni, jeśli n!=0tak, poprzedni warunek jest wystarczający.

JavaScript ES5, 118 87 85 82 77 bajtów

Ciekawa technika moim zdaniem. Pomijając całe mnóstwo, dzięki @ETHproductions i @NotthatCharles

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

JavaScript ES6, 77 57 56 54 bajtów

-21 bajtów do produkcji ETH.

x=>[...x=x.toString(2)].map(_=>x=x.replace(10,""))&&!x

D, 209 170 bajtów

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);}

To robi dokładnie to, co powinno się robić bez żadnych dodatków i korzyści.

C, 67 bajtów

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

Prawie część mojego zgłoszenia w Pythonie.

Prolog, 147 bajtów

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

Jak to działa

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

Konwertuje liczbę dziesiętną N na jej reprezentację binarną jako listę (odwróconą). Znaczenie:

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

Następnie:

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

Powtarza się nad listą [H | T], zwiększając N, jeśli element głowicy wynosi 0, w przeciwnym razie zmniejszając go.
Jeśli N w którymkolwiek momencie stanie się ujemne lub jeśli N na końcu nie jest równe 0, zwróć fałsz, w przeciwnym razie prawda.

Wcięcie

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

Czy istnieje zapobieganie cofaniu się i znajdowaniu niebinarnych rozwiązań

testowania b (N, [N])
Wypróbuj tutaj online
Uruchom go z zapytaniem takim jak:

p(42).

PowerShell, 106 bajtów

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

_{Na pewno nie wygram żadnych konkursów o najkrótszej długości. Ale hej, przynajmniej wygrywa z Javą?}

Używa bardzo długiego wywołania .NET [convert]::ToString($a,2)do konwersji naszego numeru wejściowego na ciąg reprezentujący cyfry binarne. Następnie przepuszczamy pętlę przez ten ciąg za pomocą 1..$b.length|%{..}. Każda pętla, jeśli nasza cyfra jest 1(oceniana za pomocą %2zamiast -eq1zapisywania kilku bajtów), zwiększamy nasz licznik; w przeciwnym razie zmniejszamy to. Jeśli kiedykolwiek osiągniemy wartość ujemną, oznacza to, że do tej pory było więcej )niż (napotkane, więc generujemy 0i exit. Gdy przejdziemy przez pętlę, $cmamy jedną 0lub jakąś liczbę >0, więc logicznie się nie !przyjmujemy, co daje wynik.

Ma to dziwactwo wyprowadzania 0jeśli nawiasy są niedopasowane ponieważ mamy więcej ), ale wyprowadzanie Falsejeśli nawiasy są niedopasowane ponieważ mamy więcej (. Zasadniczo funkcjonalnie równoważne stwierdzenia fałszowania, po prostu interesujące. Jeśli parens wszystkie pasują, wyniki True.

GNU Sed (z rozszerzeniem eval), 27

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

Sed tak naprawdę nie ma zdefiniowanego pojęcia „prawda” i „falsey”, więc tutaj twierdzę, że pusty ciąg oznacza „prawda”, a wszystkie inne ciągi oznaczają „falsey”.

Jeśli nie jest to do zaakceptowania, możemy wykonać następujące czynności:

GNU Sed (z rozszerzeniem eval), 44

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

Daje to 1 dla prawdy i 0 w przeciwnym razie.

𝔼𝕊𝕄𝕚𝕟 (ESMin), 21 znaków / 43 bajty

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

Try it here (Firefox only).

Zauważ, że używa to zmiennych predefiniowanych do liczb (w szczególności 2 i 0). Istnieją predefiniowane zmienne liczbowe od 0 do 256.

19 znaków / 40 bajtów, niekonkurencyjny

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

Try it here (Firefox only).

Podjęto decyzję o wdrożeniu niejawnego wyniku ... Jednak poprzednie formularze wyjściowe są nadal obsługiwane, więc masz kilka opcji wyjściowych!

Java, 129 131 bajtów

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;}

Prawdopodobnie można go skrócić. Wyjaśnienie, które nastąpi. Dzięki Geobits za 4 bajty!

C ++, 61 bajtów

Myślę, że obecna odpowiedź w C ++ jest niepoprawna: zwraca prawdziwą wartość dla wszystkich liczb parzystych, np. 4. Oświadczenie: Nie byłem w stanie użyć wspomnianego kompilatora, więc użyłem g ++ 4.8.4. Problem polega na użyciu binarnego operatora AND zamiast logicznego AND, który jest używany do przerwania wcześniej, gdy liczba zamykających nawiasów przekroczy liczbę otwierających nawiasów. To podejście może działać, jeśli truejest reprezentowane jako słowo z prawdziwym wzorem bitowym. W moim systemie i prawdopodobnie w większości innych systemów truejest to równoważne 1; tylko jeden bit jest prawdziwy. Jest także n/=2krótszy niż n>>=1. Oto ulepszona wersja jako funkcja:

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

𝔼𝕊𝕄𝕚𝕟 (bardzo niekonkurencyjne), 6 znaków / 8 bajtów

!ïⓑĦⅩ

Try it here (Firefox only).

Po bardzo, bardzo długim czasie postanowiłem wrócić do tego wyzwania. 𝔼𝕊𝕄𝕚𝕟 stało się o wiele lepsze.

Jest to osobna odpowiedź, ponieważ dwie wersje są prawie całkowicie różne.

Wyjaśnienie

Konwertuje dane wejściowe na binarne, rekurencyjnie zastępuje wystąpienia 10, a następnie sprawdza, czy wynikiem jest pusty ciąg.

C # 98 bajtów

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

otwarte na wszelkie sugestie. podoba mi się to wyzwanie, nawet jeśli jest stare