Wsporniki blokujące

30

Napisz program lub funkcję, która pobiera ośmiobajtowy ciąg zawierający jeden z każdego ze znaków ()[]{}<>ułożonych w dowolny sposób, tak aby pasowały do ​​nich cztery odpowiednie typy nawiasów. Na przykład ]<([){}>niepoprawne dane wejściowe, ponieważ nawiasy kwadratowe nie pasują (chociaż wszystkie pozostałe się zgadzają).

Drukuj lub zwrócić liczbę całkowitą od 0do 6oznaczająca ilu z sześciu możliwych par z czterech typów zamków są zablokowane. Pary typów wsporników są uważane za powiązane, jeśli między wspornikami drugiego typu występuje dokładnie jeden wspornik jednego typu. Tak ([)]i [(])są blokowane, ale ()[], [](), ([]), i [()]nie są.

Najkrótszy kod w bajtach wygrywa.

Przykłady wejścia / wyjścia

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6
Hobby Calvina
źródło

Odpowiedzi:

17

CJam, 18 lat

l7~f&_f{\/~;&}s,2/

Dzięki isaacg za kilka pomysłów na golfa :)
Wypróbuj online lub wypróbuj wszystkie przykłady

Wyjaśnienie:

l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters
aditsu
źródło
1
Och, więc jesteś facetem, który stworzył CJam ?? Jesteś mi winien wszystkie utracone odpowiedzi, które zostały pobite przez odpowiedzi CJam! ;)
kirbyfan64sos
6
@ kirbyfan64sos dobrze, lepiej zacznij się uczyć, jeśli chcesz wygrać :)
aditsu
9
7~f&? Podoba mi się już ta odpowiedź i nawet jej nie przeczytałem.
Dennis
11

Python 2, 163 bajty

def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

Spogląda na rzeczy między każdą parą pasujących nawiasów i liczy liczbę obecnych lewych lub prawych nawiasów. Ich suma podzielona przez dwa stanowi wynik.

Jestem pewien, że golfiści mogliby grać o wiele lepiej niż ja.

Hobby Calvina
źródło
31
Tak się stało. Calvin opublikował odpowiedź. Czasy ostateczne nadchodzą.
Alex A.
4

GNU sed -r, 147

Dane wyjściowe są jednoargumentowe zgodnie z tą meta-odpowiedzią .

y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

Uwaga: Zamień na \trzeczywiste tabpostacie, aby uzyskać prawidłowy wynik. Jednak program będzie działał w obu przypadkach z GNU sed.

Wypróbuj online .

Cyfrowa trauma
źródło
3

Perl, 77 bajtów

76 kod + 1 przełącznik

perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

Pobiera dane wejściowe ze STDIN i program musi być uruchamiany od nowa dla każdego wejścia.

Wyjaśnienie

  1. Zastąp wszystkie nawiasy zamykające otwartymi odpowiednikami ( y/.../.../).
  2. Następnie dla każdego znaku w ciągu wejściowym ( for$x...) zwiększ licznik dla znaku ( $h{$x}++).
  3. Jeśli po raz drugi widzimy postać, uzyskaj odległość między dwoma wystąpieniami ( length $1) i usuń oba wystąpienia tego znaku z ciągu. Na przykład, jeśli ciąg był ([{([{<<, istnieją dwa znaki [i {między nimi (. Po (przetworzeniu s ciąg staje się [{[{<<i dodajemy 2 do całkowitej liczby ( $z) nawiasów blokujących.
  4. Wynik pochodzi z $z( $_=$z)
svsd
źródło
3

Pyth, 20 bajtów

JmC/CdTzlsm@FPcsJd{J

Zestaw testowy

JmC/CdTz: Po pierwsze, konwertuje każdą parę symboli na pojedynczy znak, odwzorowując każdy znak wejściowy na kod znaku ( Cd) podzielony przez 10 ( / T), który jest taki sam dla każdej pary, ale różny dla wszystkich par. Wynikowa liczba jest konwertowana z powrotem na znak w celu ujawnienia jej później ( C). Wynikowa lista znaków jest zapisywana w J.

lsm@FPcsJd{J: Teraz mapujemy unikalne znaki w J( {J). Zaczynamy od cięcia łańcucha utworzonego przez konkatenację Jprzy użyciu bieżącego znaku jako ogranicznika ( csJd). Para nawiasów pokrywa się z bieżącą parą, jeśli pojawia się w drugiej grupie i pierwszej lub trzeciej grupie. Aby uniknąć podwójnego liczenia, policzymy pierwszy i drugi przypadek grupy. Dlatego usuwamy trzecią grupę ( P) i przecinamy pozostałe grupy ( @F). Na koniec łączymy nakładające się znaki ( s) i drukujemy długość resut ( l).

isaacg
źródło
3

Python 3, 107

t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

Luźno oparty na moim rozwiązaniu CJam.

aditsu
źródło
3

Siatkówka , 128 108 64 62 55 bajtów

(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

Gdzie <empty>oznacza pustą linię końcową. Dla celów zliczania umieść każdą linię w osobnym pliku i zastąp \nrzeczywistymi znakami linii. Dla wygody możesz użyć tego równoważnego kodu z -sflagą z jednego pliku:

(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

Wyjście jest jednoargumentowe .

Wyjaśnienie

Pierwszy (mówi Retinie, aby wykonała cały kod w pętli, aż iteracja przestanie zmieniać ciąg. W takim przypadku zawsze będzie iterować cztery razy, raz dla każdego typu nawiasu.

T`)]>}`([<{

To po prostu zamienia każdy wspornik zamykający w odpowiedni wspornik otwierający, dzięki czemu możemy później dopasować odpowiednie wsporniki za pomocą prostego odsyłacza wstecznego. (Ten etap staje się brakiem operacji po pierwszej iteracji. Jest on zawarty tylko w pętli, ponieważ Tjuż wymagał backstick, więc dodanie (kosztuje tylko jeden zamiast dwóch bajtów.)

(\D)(.*)\1(.*)
\n$2\n$3

Zastępuje skrajnie lewą parę nawiasów znakiem nowej linii. Używamy \Ddo odróżnienia nawiasów od 1s, które dodajemy później w pętli do zliczania. Na (.*)końcu zapewnia zastąpienie tylko jednej pary (ponieważ dopasowania nie mogą się pokrywać).

(?=(\D).*\n.*\1)
1

Cała regex jest z wyprzedzeniem, więc pasuje do pozycji . Dokładniej, dopasowuje jedną pozycję dla każdej pary nawiasów, która została oddzielona przez inne nawiasy, które właśnie zamieniliśmy w nowe linie. A 1jest wstawiane w każdą z tych pozycji. Możemy po prostu zostawić 1tam s, ponieważ nie wpływają one na żadne inne wyrażenia regularne (ponieważ \Ds zapewniają, że nie dopasujemy ich przypadkowo).

\n
<empty>

Na koniec usuwamy znaki nowej linii (tj. Symbole zastępcze dla bieżącego typu nawiasów) - oznacza to, że zredukowaliśmy pozostały problem do ciągu o długości 6 zawierającego tylko 3 rodzaje nawiasów, ale w przeciwnym razie działa dokładnie tak samo.

Na końcu 1pozostaną tylko s, które wstawiliśmy, a ich ilość odpowiada dokładnie liczbie blokujących się nawiasów.

Martin Ender
źródło
2

JavaScript (ES7), 121 117 bajtów

x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

Łał. To było zabawne. Naszkicowałem pomysł na odpowiedź, kiedy to wyzwanie się pojawiło, ale miało ponad 150 bajtów i nie chciałem w to grać. Wczoraj natknąłem się na ten pomysł w zeszycie i zdecydowałem, że nie przestanę o nim myśleć, dopóki go w pełni nie zagram. Skończyło się na napisaniu dwóch zupełnie nowych algorytmów, z których pierwszy skończył kilka bajtów krócej po graniu w golfa około 25 bajtów z mnóstwem hackowania bitów.

Jak to działa

Najpierw musimy ustawić zmienne ai bdo 0. ato 4-bitowa tablica binarna, w której aktualnie znajdują się pary nawiasów, oraz b16-bitowa tablica binarna, której pary nawiasów są ze sobą połączone.

Następnie, pętla przez każdego znaku cw x, i każdego char dw '0123'. Najpierw określamy, jakiego rodzaju cjest nawias e=c.charCodeAt()/26-1|0. Kody dziesiętne dla każdego typu nawiasów są następujące:

() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

Dzieląc przez 26, odejmując 1 i podłogę, mapujemy je odpowiednio na 0, 1, 2 i 3.

Następnie sprawdzamy, czy liczba ta jest równa bieżącej wartości d. Jeśli tak, to wchodzimy lub wychodzimy z dnawiasów typu th, więc włączamy dth za apomocą a^=1<<d. Jeśli tak nie jest, ale wewnątrz d-tego wspornika, musimy odwrócić enieco th w dXX sekcji 4-bitowej b. Odbywa się to w następujący sposób:

b^=(a>>d&1)<<d*4+e

(a>>d&1)Zwraca dth th a. Jeśli jesteśmy wewnątrz dtypu nawiasów, zwraca 1; w przeciwnym razie zwraca 0. Następnie przesuwamy to w lewo o d*4+ebity, a XOR bo wynik. Jeśli jesteśmy wewnątrz dtypu nawiasów klamrowych, to XOR jest d*4+etym kawałkiem b; w przeciwnym razie nic nie robi.

Na końcu całego zapętlenia bbędzie zawierać liczbę 1 bitów równą dwukrotności pożądanej wartości zwrotnej. Ale nadal musimy dowiedzieć się, ile to jest bitów. Właśnie tutaj fpojawia się podfunkcja :

f=y=>y&&y%2+f(y>>1)

Jeśli yma wartość 0, to po prostu zwraca 0. W przeciwnym razie bierze ostatni bit yz y%2, a następnie dodaje wynik yponownego uruchomienia funkcji za wyjątkiem bitu ostatniego . Na przykład:

f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

Przeglądamy btę funkcję i dzielimy wynik przez 2, i jest nasza odpowiedź.

ETHprodukcje
źródło
1

Oracle SQL 11.2, 206 bajtów

WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

Bez golfa:

WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a 
           FROM   ( -- replace ending brackets by opening brakets and split the string  
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p 
                    FROM DUAL 
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets  
Jeto
źródło