Otrzymasz ciąg znaków s. Gwarantuje to, że ciąg ma równych i przynajmniej jeden [s i ]s. Zagwarantowane jest również wyważenie wsporników. Ciąg może mieć także inne znaki.

Celem jest wyprowadzenie / zwrócenie listy krotek lub listy list zawierającej indeksy każdego [i ]pary.

Uwaga: ciąg znaków jest indeksowany od zera.

Przykład: !^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][]powinien wrócić

[(8, 41), (20, 33), (21, 27), (36, 39), (42, 48), (49, 50)]lub coś równoważnego z tym. Krotki nie są konieczne. Można również używać list.

Przypadki testowe:

input:[[asdf][][td([)ty54g% ]hg[[f]u][f[[jhg][gfd]sdf]sdfs]ghd]fr43f]
output:[(0, 62),(1, 6), (7, 8), (9, 56), (13, 22), (25, 30), (26, 28), (31, 52), (33, 47), (34, 38), (39, 43)]
input:[[][][][]][[][][][[[[(]]]]]))
output:[(0, 9), (1, 2), (3, 4), (5, 6), (7, 8), (10,26),(11, 12), (13, 14), (15, 16), (17, 25), (18, 24), (19, 23), (20, 22)]
input:[][][[]]
output:[(0, 1), (2, 3), (4, 7), (5, 6)]
input:[[[[[asd]as]sd]df]fgf][][]
output:[(0, 21), (1, 17), (2, 14), (3, 11), (4, 8), (22, 23), (24, 25)]
input:[]
output:[(0,1)]
input:[[(])]
output:[(0, 5), (1, 3)]

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach dla każdego języka programowania.

Brain-Flak Classic , 108 bajtów

{((((((([][][]){}){}){}()){}){}{}[])()()){{}<>{}(<>)}{}((){[](<{}>)}{}){{}<>[({}<[{}]>)](<>)}{}<>(({}()))<>}

Wypróbuj online!

Przechowuje każdy otwór [w odpowiednim stosie i wysyła za każdym razem, gdy trafimy a ].

Python 2 , 74 bajty

s=[];i=0
for c in input():
 if'['==c:s+=i,
 if']'==c:print s.pop(),i
 i+=1

Wypróbuj online!

JavaScript, 69 62 bajtów

Szybki golf w pociągu do domu. Prawdopodobnie można to poprawić.

Pobiera dane wejściowe jako tablicę znaków i wysyła obiekt z kluczami będącymi wskaźnikami [s, a ich wartości są wskaźnikami odpowiadających im ]s.

a=>a.map((x,y)=>x==`]`?o[a.pop()]=y:x==`[`&&a.push(y),o={})&&o

Wypróbuj online

Haskell , 92 79 bajtów

g(u:a)n(']':x)=(u,n):g a(n+1)x
g a n(s:x)=g([n|s=='[']++a)(n+1)x
g[]_[]=[]
g[]0

Wypróbuj online!

Wyjaśnienie

Tworzymy funkcję, gktóra przyjmuje 3 argumenty.

• a, czyli lokalizacje wszystkich niedopasowanych [s.

• n, czyli liczba przetworzonych znaków

• x czyli znaki nieprzetworzone.

Jeśli naszą pierwszą postacią jest to, ]że usuwamy uz przodu naszą ai wracamy (u,n)plus wszystko, co pozostanie.

g(u:a)n(']':x)=(u,n):g a(n+1)x

Jeśli naszą pierwszą postacią nie jest ], to jest albo [coś innego, zwiększamy ni dodajemy [n|s=='[']z przodu a. [n|s=='[']będzie, [n]jeśli s=='['i []inaczej.

g a n(s:x)=g([n|s=='[']++a)(n+1)x

Jeśli brakuje nam znaków, zwracamy pustą listę.

g[]_[]=[]

Java 10, 95 bajtów

Pusta lambda przyjmująca ciąg wejściowy jako punkt int[]kodu Unicode.

s->{int r=0,w=0;for(var c:s){if(c==91)s[w++]=r;if(c==93)System.out.println(s[--w]+","+r);r++;}}

Wypróbuj online

Nie golfił

s -> {
    int r = 0, w = 0;
    for (var c : s) {
        if (c == 91)
            s[w++] = r;
        if (c == 93)
            System.out.println(s[--w] + "," + r);
        r++;
    }
}

Podziękowanie

• dzięki Jonathanowi Frechowi za pomysł użycia ciągu wejściowego jako stosu ( tutaj )

vim, 89 bajtów

:s/\(.\)/\1<C-V><C-M>/g|g/^\[/ :norm %mm%:pu! =line('.').','.line(\"'m\")<C-V><C-M><C-X>$<C-X>J
:v/\[/d|%s/\[//g

Adnotacja

:s/\(.\)/\1<C-V><C-M>/g            " one character per line
|g/^\[/                            " for each opening square bracket:
  :norm %mm%                       "   mark the line with the matching bracket
  :pu! =line('.').','.line(\"'m\") "   write the line numbers to preceeding line
  <C-V><C-M><C-X>$<C-X>J           "   convert to 0-based counting and join lines
:v/\[/d                            " remove all non-opening bracket lines
|%s/\[//g                          " remove brackets

<C-V>to 0x16. <C-M>to 0x0d. <C-X>to 0x18.

Wypróbuj online!

QBasic (QB64), 137 127 112 bajtów

INPUT a$
for i=0to len(a$)
c$=mid$(a$,i+1,1)
if"["=c$then
b(n)=i
n=n+1
elseif"]"=c$then
n=n-1
?b(n),i
endif
next

Potrzebujemy czterech dwóch bajtów, ponieważ wyzwanie wymaga 0-indeksowania. Mój pierwszy post QBasic, opinie są mile widziane.

• 10 bajtów dzięki steenbergh
• 3 bajty dzięki Erikowi Outgolferowi
• 12 bajtów, zapisując w formacie pliku unix ( \r\n-> \n)

Po wykonaniu wygląda tak:

Pyth, 26 bajtów

VQIqN\[=+YZ)IqN\],.)YZ)=hZ

Wypróbuj tutaj

Wyjaśnienie

VQIqN\[=+YZ)IqN\],.)YZ)=hZ
VQ                     =hZ   For each character in the input (indexed by Z)...
  IqN\[=+YZ)                 ... if the character is [, add the index to Y...
            IqN\],.)YZ)      ... if the character is ], output the previous index
                             and current index.

R , 141 133 115 112 108 bajtów

function(y,x=utf8ToInt(y)){for(i in seq(x)){if(x[i]==91)F=c(i,F);if(x[i]==93){T=c(T,F[1],i);F=F[-1]}};T[-1]}

Wypróbuj online!

Nic specjalnego. 1-indeksowany, bo tak powiedziałem. R tak naprawdę nie ma stosy, więc pierwotnie stosowany c, headoraz tailaby uzyskać ten sam efekt dosłownego. Niegolfowana wersja oryginalna (aktualizuje za pomocą, utf8ToIntaby usunąć niektóre bajty, używając początku wektora jako górnej części stosu oraz nadużywając Ti Fwbudowanych, aby uniknąć inicjowania stosów.):

f <- function(y, x=el(strsplit(y,""))) {
  p <- l <- NULL
  for(i in seq_along(x)) {
    if(x[[i]]=='[') {
      p <- c(p, i)
    }
    if(x[[i]]==']') {
      l <- c(l, tail(p, 1), i)
      p <- head(p, -1)
    }
  }
  l # Because I said so. Change to l-1 if you want to check the test cases.
}

Dalej (gforth) , 75 bajtów

: f 0 do dup i + c@ dup 91 = if i s>f then 93 = if f>s . i . cr then loop ;

Wypróbuj online!

Nadużywa stosu zmiennoprzecinkowego, ale pozwala na użycie, do loopponieważ kod nie (ręcznie) dotyka stosu zwrotnego.

Wyjaśnienie

1. Pętlę znaków w ciągu
2. Sprawdź każdą postać
   1. Jeśli jest równy [, umieść stos zmiennoprzecinkowy
   2. jeśli równa się ]pop z stosu zmiennoprzecinkowego i wyjście z bieżącą pozycją

Objaśnienie kodu

0 do                 \ start a loop from 0 to string-length
  dup                \ duplicate the starting address to avoid losing it
  i + c@             \ get the address of the current position and retrieve the character
  dup                \ duplicate the character, to allow checking twice
  91 = if            \ if char = [
    i s>f            \ store the current address on the floating point stack
  then               \ end the if-statement
  93 = if            \ if char = ]
    f>s .            \ pop the starting position from the float-stack and print
    i .              \ print the current position
    cr               \ output a newline
  then               \ end the if-statement
loop                 \ end the loop

Siatkówka , 36 bajtów

L$v`\[((\[)|(?<-2>])|[^]])*
$.`,$.>`

Wypróbuj online! Wyjaśnienie:

L

Wygeneruj listę z wyników dopasowania.

$

Użyj poniższego podstawienia, aby wygenerować listę zamiast dopasowań.

v`

Pozwól, aby mecze się nakładały.

\[((\[)|(?<-2>])|[^]])*

Jest to aplikacja grup bilansujących .NET. [Jest dopasowany dosłownie, to jak wiele znaków jak to możliwe są konsumowane. Po [dopasowaniu każdego kolejnego dopasowanie jest dodawane do $2stosu. Jeśli ten stos nie jest pusty, możemy dopasować a ], usuwając dopasowanie ze stosu. W przeciwnym razie możemy dopasować wszystko, co nie jest ]( [zostało już wcześniej dopasowane). Dopasowanie kończy się, gdy spełnia dopasowanie ]dla [, ponieważ $2stos jest (teraz) pusty w tym momencie.

$.`,$.>`

Podstawienie składa się z dwóch zmiennych oddzielonych przecinkiem. .Wskazuje długość zmienną zamiast wartości być stosowane. >Wskazuje, że zmienna powinna być oceniana pod względem separatora prawej zamiast meczu. $`Zmienna oznacza prefiks meczu, co oznacza, $.`daje pozycję z poniższych [; że >modyfikator zmienia to prefiksem właściwym separatorem meczu, co daje pozycję dopasowywania ].

Galaretka ,  22 21 20  19 bajtów

^{Bez wątpienia jest możliwe w galaretce w połowie tej liczby bajtów: p ...}

n€Ø[ḅ-µMịÄÐƤi€0ĖƊ’Ä

Monadyczny link akceptujący listę znaków, który zwraca listę list liczb całkowitych.
Jako pełny program przyjmuje ciąg znaków i wyświetla reprezentację tej listy.

Wypróbuj online!

W jaki sposób?

n€Ø[ḅ-µMịÄÐƤi€0ĖƊ’Ä - Link: list of characters    e.g. "[f[o]o!]"
  Ø[                - list of characters = ['[', ']']
n€                  - not equal? for €ach              [[0,1],[1,1],[0,1],[1,1],[1,0],[1,1],[1,1],[1,0]]
                    -     ...relating to the characters:  [     f     [     o     ]     o     !     ]
    ḅ-              - convert from base -1             [1,0,1,0,-1,0,0,-1]
                    -     ...i.e.: 1 where '['; -1 where ']'; and 0 elsewhere
      µ             - start a new monadic chain with that as the argument, say V
                Ɗ   - last 3 links as a monad (function of V):
          ÐƤ        -   for post-fixes:
         Ä          -     cumulative sum               [[1,1,2,2,1,1,1,0],[0,1,1,0,0,0,-1],[1,1,0,0,0,-1],[0,-1,-1,-1,-2],[-1,-1,-1,-2],[0,0,-1],[0,-1],-1]
            i€0     -   1st index of 0 in €ach (or 0)  [8,1,3,1,0,1,1,0]
               Ė    -   enumerate                      [[1,8],[2,1],[3,3],[4,1],[5,0],[6,1],[7,1],[8,0]]
       M            - maximal indices of V             [1,3]
        ị           - index into                       [[1,8],[3,3]]
                 ’  - decrement                        [[0,7],[2,2]]
                  Ä - cumulative sum (vectorises)      [[0,7],[2,4]]

SWI-Prolog 254 bajty

d([']'|T],I,[S|Z],M,R):-J is I+1,d(T,J,Z,[',','(',S,',',I,')'|M],R).
d(['['|T],I,S,M,R):-J is I+1,d(T,J,[I|S],M,R).
d([_|T],I,S,M,R):-J is I+1,d(T,J,S,M,R).
d(_,_,_,R,R).
m(X):-atom_chars(X,A),d(A,0,[],[']'],[_|R]),atomic_list_concat(['['|R],S),print(S).

Przykład:

?- m('!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][]').
'[(49,50),(42,48),(8,41),(36,39),(20,33),(21,27)]'
true 

C (gcc) , 87 bajtów

f(char*Z){for(char*z=Z,*q=z;*z;*z++-93||printf("%d,%d;",*--q,z-1-Z))*z-91||(*q++=z-Z);}

Wypróbuj online!

Wyjaśnienie

Aby śledzić indeksy łańcuchów otwierających nawias, łańcuch wejściowy jest nadpisywany i używany jako stos.

f(char*Z){          // take mutable input string
 for(char*z=Z,*q=z; // copy pointer to current string index, current stack index
 *z;                // loop through the entire string
 *z++-93||          // if z == ']'
   printf("%d,%d;", // decrement stack pointer,
    *--q,z-1-Z))    //  write bracket pair position
  *z-91||           // if z == '['
   (*q++=z-Z);}     // write bracket position onto stack, increment stack pointer

Wypróbuj online!

Galaretka , 20 bajtów

=©ⱮØ[_/aÄ$+®ŻĠḊẎ_2s2

Wypróbuj online!

Ma efekt uboczny w rejestrze, mam nadzieję, że może być funkcją.

Japt v1.4.5, 23 bajty

;Ë¥']?ApENo):D¥'[©NpE
A

Wypróbuj online!

Rozpakowane i jak to działa

;UmDE{D==']?ApENo):D=='[&&NpE
A

;                              Use alternative set of initial variables
                               A = [] is used here
 UmDE{                         Map over each char of input string...
      D==']?                     If the char is closing bracket...
            ApENo)                 Push the current index and N.pop() to A
                  :D=='[&&       Otherwise, if the char is opening bracket...
                          NpE      Push the current index to N

A     Output A

Dane wyjściowe to spłaszczona tablica [closing index, opening index]. Jeśli odwrotna kolejność nie jest pożądana, dodanie wna końcu wykonuje zadanie (+1 bajty).

Common Lisp, 95 bajtów

(lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#\[(push p s))(#\](print`(,(pop s),p))))))

(defun par (string &aux stack)
  (dotimes (pos (length string))
    (case (char string pos)
      (#\[ (push pos stack))
      (#\] (print (list (pop stack) pos))))))

((lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#\[(push p s))(#\](print`(,(pop s),p))))))
 "!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][] ")

drukuje:

(21 27) 
(20 33) 
(36 39) 
(8 41) 
(42 48) 
(49 50)

K (ngn / k) , 38 37 bajtów

{b@0N 2#,/=(|':+\-/a)b:&|/a:"[]"=\:x}

Wypróbuj online!

{ } funkcja z argumentem x

"[]"=\:xdwie listy boolowskie dla wystąpienia "["i"]"

a: Przypisać do a

|/ boolean ”lub” z dwóch list

& gdzie (przy jakich indeksach) są nawiasy?

b: Przypisać do b

-/lista z 1 dla "[", -1 dla "]"i 0 wszędzie indziej

+\ sumy częściowe

|': parami maksima (każdy element maksymalny z poprzednim, element początkowy pozostaje taki sam)

Reprezentuje głębokość nawiasu dla każdego znaku. Indeksujemy go za pomocą b(zestawienie indeksuje) i uzyskujemy głębokość nawiasów tylko dla nawiasów.

= „grupuj według” - słownik odwzorowuje głębokości odwzorowujące indeksy, w których występują

,/ konkatenuj wartości ze słownika, ignorując klucze

0N 2# przekształć macierz w 2 kolumny (lista list)

b@indeksuj bz każdym elementem macierzy

Galaretka , 20 18 bajtów

Zapisane 1 bajt dzięki @ user202729 informując mnie, że µ€jest)

ẹⱮØ[µ³ḣċþØ[_/Ụị)Z’

Wypróbuj online!

Po kilku godzinach zmagania się z tym po to, żeby go uruchomić ... Jestem szczerze zaskoczony, że stało się tak krótko :-)

Wyjaśnienie

ẹⱮØ[µ³ḣċþØ[_/Ụị)Z’   Main link. Argument: s (string)  '[a[b]c[]][d]'
  Ø[                 Shortcut for the string "[]".
 Ɱ                   For each char in the "[]":
ẹ                      Find the indices of each occurrence in the input.
                     For our example, this gives the array [[1, 3, 7, 10], [5, 8, 9, 12]].

    µ                Begin a new monadic chain, with said array as its argument.
               )     For each of the two sub-arrays q within the array:
                         [[1, 3, 7, 10], [5, 8, 9, 12]]
     ³ḣ                For each item n in q, take the first n chars of the input.
                         [['[',     '[a[',      '[a[b]c[',   '[a[b]c[]]['],
                          ['[a[b]', '[a[b]c[]', '[a[b]c[]]', '[a[b]c[]][d]']]
        þØ[            For each string s in this, and each char c in "[]":
       ċ                 Count the occurrences of c in s.
                         [[[1, 0],  [2, 0],     [3, 1],      [4, 3]],
                          [[2, 1],  [3, 2],     [3, 3],      [4, 4]]]
           _/          Reduce each pair by subtraction. This is the number of open brackets
                         at each position.
                         [[1, 2, 2, 1], [1, 1, 0, 0]]
             U         Sort the indices by their values, using position as a tiebreaker.
                         [[1, 4, 2, 3], [3, 4, 1, 2]]
              ị        Index these values back into q.
                         [[1, 10, 3, 7], [9, 12, 5, 8]]

               )     Start a new monadic chain with the result as its argument.
                Z    Zip; transpose rows and columns.
                         [[1, 9], [10, 12], [3, 5], [7, 8]]
                 ’   Decrement; switch to 0-indexing.
                         [[0, 8], [9, 11], [2, 4], [6, 7]]

CJam , 25 bajtów

0q{"[]"#"_ \p_p "S/=~)}/;

Zaskakująco konkurencyjny - przegrywa tylko z Japt i Jelly [ Edytuj : oraz Węgiel drzewny i Stax :(]

Wypróbuj online!

Wyjaśnienie

0                          Push 0.
 q                         Push the input.
  {                   }/   For each character in the input:
   "[]"#                     Find index of this character in the string "[]" (or -1 if not found).
                   =         Use this index to choose
        "       "S/            one of the following snippets
                    ~          and execute it:
         _                       If it was 0 ('['), duplicate the number on the stack.
           \p_p                  If it was 1 (']'), print the current number and the one under it.
                                 If it was -1, do nothing.
                     )       Increment the number on top of the stack.
                        ;  Delete the number.

Python 2 , 109 bajtów

def a(s,r=[],i=0):
 o=[]
 while i<len(s):exec["r+=[i]","o+=[(r.pop(),i)]",'']['[]'.find(s[i])];i+=1
 return o

Wypróbuj online!

Pyth ,  28  26 bajtów

{I#.e,t+lhfSI/LT`Y+._>Qk\]

Zestaw testowy.

W tej chwili jest to dłuższe niż podejście Mnemonica , ale wydaje mi się, że mogę trochę pograć w golfa i to na szczęście również nie korzysta z takich struktur imperatywnych w języku Python V. Początkowa wersja miała 36 bajtów i zawierała także wiele błędów.

Jak to działa

{I # .e, t + lhfSI / LT`Y + ._> Qk \] - Pełny program. Pobiera cytowany ciąg Q ze STDIN.
   .e - Wyliczona mapa. k = wskaźnik iteracji, b = aktualny element.
                     > Qk - Uzyskaj elementy Q o indeksach większych niż k.
                   ._ - Generuje wszystkie przedrostki tego.
                  + \] - I dodaj „]” (do obsługi niektórych przypadków krawędzi).
          f - Filtruj tę listę za pomocą T = bieżący element.
              L `Y - Dla każdego znaku w str ([]),„ [] ”...
             / T - ... Policz wystąpienia tego w T.
           SI - I sprawdź, czy wartości są coraz częściej sortowane.
         h - głowa. Odzyskaj pierwszy element.
       + l - Uzyskaj długość tego + k.
      t - Zmniejszenie (o 1).
     , - I sparuj tę wartość z k. Zwraca [i, k] gdzie i
                             indeks odpowiadającego] i k jest indeksem [.
  # - Filtruj tę listę według:
{I - Para jest niezmienna w stosunku do deduplikacji.

Perl 5, 53 bajtów

say"$-[0] ".($+[0]-1)while s/\[[^][]*\]/1x length$&/e

Uruchom jako perl -nE '<above code snippet>'. Pobiera dane wejściowe przez standardowe wejście.

Jak zwykle optymalnym rozwiązaniem problemu dla Perla jest wyrażenie regularne. Próbujemy dopasować dowolną parę nawiasów, która nie zawiera żadnych par, używając raczej głupio wyglądającej klasy znaków ( s/\[[^][]*\]/.../). Jeśli dopasowanie się powiedzie, zastępujemy dopasowany tekst cyfrą1 w kółko, aby przypadkowo nie dopasować tych nawiasów i drukujemy wskaźniki dopasowania. Wypłukać i powtórzyć.

Stax , 13 bajtów

é√p(l▓1½\á²ë(

Uruchom i debuguj

Używa stosu wejściowego do śledzenia otwartych par nawiasów klamrowych. Oto program rozpakowany, nieposortowany i skomentowany.

F       iterate over input characters
 .][I   get the index of the character in the string "[]", or -1
 ^|cv   skip the rest of this iteration if index was -1
 i~     push the current iteration index to the input stack
 C      skip the rest of this iteration if index was 0
 \      form a pair with the top two items from the input stack
 JP     join with space, and print

Uruchom ten

Węgiel drzewny , 20 bajtów

ＦＬθ≡§θι[⊞υι]«Ｉ⊟υ,Ｉι⸿

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

ＦＬθ

Pętla w niejawnym zakresie długości ciągu wejściowego.

≡§θι

Włącz aktualny znak.

[⊞υι

Jeśli jest to [a, wypchnij bieżący indeks do predefiniowanej zmiennej tablicowej.

]«Ｉ⊟υ,Ｉι⸿

Jeśli jest to a ]następnie usuń najnowszy indeks ze zmiennej tablicowej i wydrukuj go, a bieżący indeks oddzielamy przecinkiem i rozpoczynamy nowy wiersz. Alternatywne formaty wyjściowe, jeśli są akceptowalne, mogłyby zaoszczędzić niektóre bajty: ]Ｉ⟦⊟υιωzapisuje 2 bajty, ale drukuje każdy indeks w osobnej linii, podwójnie rozmieszczając pary indeksów; ]Ｉ⟦⊟υιpo prostu drukuje indeksy w osobnych wierszach, co utrudnia ich rozróżnienie.