Wygeneruj wszystkie fragmenty Brain-Flak

14

To pytanie jest drugim z kilku wyzwań urodzinowych Brain-flak zaprojektowanych z okazji pierwszych urodzin Brain-Flak! Więcej informacji na temat urodzin Brain-Flaka można znaleźć tutaj

Wyzwanie

Do tego wyzwania wygenerujesz wszystkie w pełni dopasowane ciągi z listy nawiasów. Aby pożyczyć definicję w pełni dopasowanego ciągu DJMcMayhem :

  • Dla celów niniejszego wyzwanie, „uchwyt” jest każdy z tych znaków: ()[]{}<>.

  • Para nawiasów jest uważana za „dopasowaną”, jeśli nawiasy otwierające i zamykające są w odpowiedniej kolejności i nie zawierają w sobie znaków, takich jak

    ()
    []{}
    

    Lub jeśli każdy podelement w nim również jest dopasowany.

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

    Elementy podrzędne można również zagnieżdżać na kilku warstwach.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Sznurek jest uważany za „w pełni dopasowany” wtedy i tylko wtedy, gdy każda para wsporników ma prawidłowy otwierający i zamykający wspornik we właściwej kolejności.


Wejście

Twój program lub funkcja pobierze listę czterech liczb nieujemnych w dowolnym wygodnym, spójnym formacie. Obejmuje to (ale nie wyłącznie) listę liczb całkowitych, ciąg znaków nieprzekraczających cyfr lub oddzielne argumenty. Te cztery liczby reprezentują liczbę dopasowanych par każdego rodzaju wspornika. Na przykład [1,2,3,4]reprezentowałby:

  • 1 para ()

  • 2 pary {}

  • 3 pary []i

  • 4 pary <>

Możesz wybrać, która para nawiasów odpowiada każdemu wejściu, o ile jest spójna.

Wynik

Powinieneś wypisać wszystkie w pełni dopasowane ciągi, które można utworzyć z tej listy nawiasów bez duplikatów. Dane wyjściowe mogą być w dowolnym rozsądnym formacie, który obejmuje wydrukowanie ciągów rozdzielanych bez nawiasów do STDOUT lub listy ciągów jako wartości zwracanej z funkcji.

Twój algorytm musi działać dla dowolnych dowolnych danych wejściowych, ale nie musisz się martwić limitami pamięci, czasu lub liczb całkowitych (np. Jeśli twoja odpowiedź jest w C, nie otrzymasz 2 33 jako danych wejściowych).

To jest , więc wygrywa najkrótsza odpowiedź w bajtach.

Przykład wejścia i wyjścia

W tych przykładach użyję tej samej kolejności wprowadzania, jak powyżej.

Dla każdego przykładu zostanie wprowadzony pierwszy wiersz, a kolejne wiersze będą wynikiem

Example 0:
[0,0,0,0]


Example 1:
[1,0,0,0]
()

Example 2:
[0,2,0,0]
{}{}
{{}}

Example 3:
[0,0,1,1]
[]<>
[<>]
<[]>
<>[]

Example 4:
[0,1,2,0]
{}[][]  {}[[]]  {[]}[]  {[][]}  {[[]]} 
[{}][]  [{}[]]  [{[]}]  []{}[]  []{[]} 
[][{}]  [][]{}  [[{}]]  [[]{}]  [[]]{}

Example 5:
[1,0,0,3]
()<><><>  ()<><<>>  ()<<>><>  ()<<><>>  ()<<<>>>  (<>)<><>  (<>)<<>>
(<><>)<>  (<><><>)  (<><<>>)  (<<>>)<>  (<<>><>)  (<<><>>)  (<<<>>>)
<()><><>  <()><<>>  <()<>><>  <()<><>>  <()<<>>>  <(<>)><>  <(<>)<>>
<(<><>)>  <(<<>>)>  <>()<><>  <>()<<>>  <>(<>)<>  <>(<><>)  <>(<<>>)
<><()><>  <><()<>>  <><(<>)>  <><>()<>  <><>(<>)  <><><()>  <><><>()
<><<()>>  <><<>()>  <><<>>()  <<()>><>  <<()><>>  <<()<>>>  <<(<>)>>
<<>()><>  <<>()<>>  <<>(<>)>  <<>>()<>  <<>>(<>)  <<>><()>  <<>><>()
<<><()>>  <<><>()>  <<><>>()  <<<()>>>  <<<>()>>  <<<>>()>  <<<>>>()

Example 6:
[1,1,1,1]

(){}[]<>  (){}[<>]  (){}<[]>  (){}<>[]  (){[]}<>  (){[]<>}  (){[<>]}
(){<[]>}  (){<>}[]  (){<>[]}  ()[{}]<>  ()[{}<>]  ()[{<>}]  ()[]{}<>
()[]{<>}  ()[]<{}>  ()[]<>{}  ()[<{}>]  ()[<>{}]  ()[<>]{}  ()<{}[]>
()<{}>[]  ()<{[]}>  ()<[{}]>  ()<[]{}>  ()<[]>{}  ()<>{}[]  ()<>{[]}
()<>[{}]  ()<>[]{}  ({})[]<>  ({})[<>]  ({})<[]>  ({})<>[]  ({}[])<>
({}[]<>)  ({}[<>])  ({}<[]>)  ({}<>)[]  ({}<>[])  ({[]})<>  ({[]}<>)
({[]<>})  ({[<>]})  ({<[]>})  ({<>})[]  ({<>}[])  ({<>[]})  ([{}])<>
([{}]<>)  ([{}<>])  ([{<>}])  ([]){}<>  ([]){<>}  ([])<{}>  ([])<>{}
([]{})<>  ([]{}<>)  ([]{<>})  ([]<{}>)  ([]<>){}  ([]<>{})  ([<{}>])
([<>{}])  ([<>]){}  ([<>]{})  (<{}[]>)  (<{}>)[]  (<{}>[])  (<{[]}>)
(<[{}]>)  (<[]{}>)  (<[]>){}  (<[]>{})  (<>){}[]  (<>){[]}  (<>)[{}]
(<>)[]{}  (<>{})[]  (<>{}[])  (<>{[]})  (<>[{}])  (<>[]){}  (<>[]{})
{()}[]<>  {()}[<>]  {()}<[]>  {()}<>[]  {()[]}<>  {()[]<>}  {()[<>]}
{()<[]>}  {()<>}[]  {()<>[]}  {([])}<>  {([])<>}  {([]<>)}  {([<>])}
{(<[]>)}  {(<>)}[]  {(<>)[]}  {(<>[])}  {}()[]<>  {}()[<>]  {}()<[]>
{}()<>[]  {}([])<>  {}([]<>)  {}([<>])  {}(<[]>)  {}(<>)[]  {}(<>[])
{}[()]<>  {}[()<>]  {}[(<>)]  {}[]()<>  {}[](<>)  {}[]<()>  {}[]<>()
{}[<()>]  {}[<>()]  {}[<>]()  {}<()[]>  {}<()>[]  {}<([])>  {}<[()]>
{}<[]()>  {}<[]>()  {}<>()[]  {}<>([])  {}<>[()]  {}<>[]()  {[()]}<>
{[()]<>}  {[()<>]}  {[(<>)]}  {[]()}<>  {[]()<>}  {[](<>)}  {[]}()<>
{[]}(<>)  {[]}<()>  {[]}<>()  {[]<()>}  {[]<>()}  {[]<>}()  {[<()>]}
{[<>()]}  {[<>]()}  {[<>]}()  {<()[]>}  {<()>}[]  {<()>[]}  {<([])>}
{<[()]>}  {<[]()>}  {<[]>()}  {<[]>}()  {<>()}[]  {<>()[]}  {<>([])}
{<>}()[]  {<>}([])  {<>}[()]  {<>}[]()  {<>[()]}  {<>[]()}  {<>[]}()
[(){}]<>  [(){}<>]  [(){<>}]  [()]{}<>  [()]{<>}  [()]<{}>  [()]<>{}
[()<{}>]  [()<>{}]  [()<>]{}  [({})]<>  [({})<>]  [({}<>)]  [({<>})]
[(<{}>)]  [(<>){}]  [(<>)]{}  [(<>{})]  [{()}]<>  [{()}<>]  [{()<>}]
[{(<>)}]  [{}()]<>  [{}()<>]  [{}(<>)]  [{}]()<>  [{}](<>)  [{}]<()>
[{}]<>()  [{}<()>]  [{}<>()]  [{}<>]()  [{<()>}]  [{<>()}]  [{<>}()]
[{<>}]()  [](){}<>  [](){<>}  []()<{}>  []()<>{}  []({})<>  []({}<>)
[]({<>})  [](<{}>)  [](<>){}  [](<>{})  []{()}<>  []{()<>}  []{(<>)}
[]{}()<>  []{}(<>)  []{}<()>  []{}<>()  []{<()>}  []{<>()}  []{<>}()
[]<(){}>  []<()>{}  []<({})>  []<{()}>  []<{}()>  []<{}>()  []<>(){}
[]<>({})  []<>{()}  []<>{}()  [<(){}>]  [<()>{}]  [<()>]{}  [<({})>]
[<{()}>]  [<{}()>]  [<{}>()]  [<{}>]()  [<>(){}]  [<>()]{}  [<>({})]
[<>{()}]  [<>{}()]  [<>{}]()  [<>](){}  [<>]({})  [<>]{()}  [<>]{}()
<(){}[]>  <(){}>[]  <(){[]}>  <()[{}]>  <()[]{}>  <()[]>{}  <()>{}[]
<()>{[]}  <()>[{}]  <()>[]{}  <({})[]>  <({})>[]  <({}[])>  <({[]})>
<([{}])>  <([]){}>  <([])>{}  <([]{})>  <{()}[]>  <{()}>[]  <{()[]}>
<{([])}>  <{}()[]>  <{}()>[]  <{}([])>  <{}[()]>  <{}[]()>  <{}[]>()
<{}>()[]  <{}>([])  <{}>[()]  <{}>[]()  <{[()]}>  <{[]()}>  <{[]}()>
<{[]}>()  <[(){}]>  <[()]{}>  <[()]>{}  <[({})]>  <[{()}]>  <[{}()]>
<[{}]()>  <[{}]>()  <[](){}>  <[]()>{}  <[]({})>  <[]{()}>  <[]{}()>
<[]{}>()  <[]>(){}  <[]>({})  <[]>{()}  <[]>{}()  <>(){}[]  <>(){[]}
<>()[{}]  <>()[]{}  <>({})[]  <>({}[])  <>({[]})  <>([{}])  <>([]){}
<>([]{})  <>{()}[]  <>{()[]}  <>{([])}  <>{}()[]  <>{}([])  <>{}[()]
<>{}[]()  <>{[()]}  <>{[]()}  <>{[]}()  <>[(){}]  <>[()]{}  <>[({})]
<>[{()}]  <>[{}()]  <>[{}]()  <>[](){}  <>[]({})  <>[]{()}  <>[]{}()
Riley
źródło
Powiązane
Riley

Odpowiedzi:

6

Haskell , 128 bajtów

fjest główną funkcją, pobiera listę Ints i zwraca listę Strings.

f=g.($zip"({[<"")}]>").zipWith replicate
g=max[""].(#g)
l#c=[b:s|x@(b,e):r<-l,s<-(r:filter(/=x:r)l)?(map(e:).c)]
l?c=c l++l#(?c)

Wypróbuj online!

Jak to działa

  • fprzekształca swoją listę wejściową w listę list krotek, każda krotka zawiera parę nawiasów, z każdym rodzajem nawiasu we własnej liście podrzędnej. Np . [1,2,0,0]Staje się [[('{','}')],[('[',']'),('[',']')]]. Następnie wywołuje gz przekształconą listą.
  • Pozostałe funkcje używają częściowo częściowo kontynuowanego stylu przeplatanego z manipulacją listą. Każda funkcja kontynuacji cpobiera listę lpozostałych krotek i zwraca listę możliwych ciągów znaków, które należy dodać do tego, co zostało już wygenerowane.
  • g lgeneruje listę w pełni dopasowanych ciągów, które można formować, używając wszystkich nawiasów w l.
    • Robi to, wywołując l#ggenerowanie ciągów zaczynających się od jakiegoś nawiasu. Sam gparametr rekurencyjny jest używany jako kontynuacja przez #, do generowania tego, co następuje po pierwszym podelementie w nawiasach.
    • W przypadku, gdy nie ma takich ciągów (ponieważ lnie ma w nich nawiasów), gzwraca [""]listę zawierającą tylko pusty ciąg. Ponieważ [""]porównuje mniejsze do wszystkich niepustych list produkowanych przez #, możemy to zrobić, stosując max.
  • l#cgeneruje łańcuchy od lpoczątku z co najmniej jednym podelementem w nawiasach, pozostawiając kontynuację w ccelu ustalenia, co następuje po elemencie.
    • bi esą wybraną parą nawiasów w krotce x, i rjest listą pozostałych krotek tego samego typu nawiasów.
    • r:filter(/=x:r)ljest lpo xusunięciu krotki , nieco przestawiony.
    • ?jest wywoływany w celu wygenerowania możliwych podelementów między bi e. Pobiera własną kontynuację map(e:).c, która jest prefiksem ekażdego generowanego ciągu sufiksów c.
    • #sam dodaje inicjał bdo wszystkich ciągów wygenerowanych przez ?i c.
  • l?cgeneruje w pełni dopasowane ciągi, które można formować przy użyciu zerowej lub większej liczby par nawiasów l, a następnie pozostawia do kontynuacji, caby obsłużyć to, co zostało. c lCzęść idzie bezpośrednio c, bez dodawania żadnych podelementów, natomiast l#(?c)zastosowania #do generowania jeden podelement a następnie zadzwonić (?c)rekursywnie dla ewentualnych dalszych nich.
Ørjan Johansen
źródło
4

Galaretka , 50 40 34 bajtów

-6 bajtów dzięki Leaky Nun (przejście do pracy tam, gdzie nie mogłem)

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ

Prosty i nieefektywny.

Wypróbuj online! (przekroczenie limitu czasu w TIO dla [1,1,1,1] - tak, nieefektywne.)

W jaki sposób?

Rekurencyjnie usuwa pary pasujących nawiasów, które znajdują się obok siebie, dopóki nie będzie można usunąć więcej dla każdego możliwego łańcucha, który można utworzyć, zachowując takie łańcuchy, które redukują się do zera (stąd wszystkie pasujące treści).

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ - Main link: list: [n(), n{}, n[], n<>]
“()“{}“[]“<>”                      - literal ["()", "{}", "[]", "<>"]
             ©                     - copy to register
               "                   - zip with:
              ẋ                    -   repeat list
                F                  - flatten
                 Œ!                - all permutations (yeah, it's inefficient!)
                   Q               - de-duplicate
                    µ              - monadic chain separation
                                Ðḟ - filter discard if (non empty is truthy):
                             µÐL   -   loop until no change:
                       ®           -     recall value from register
                     W             -     wrap loop variable in a list
                      ;            -     concatenate
                           ¥/      -     reduce with last two links as a dyad:
                        œṣ         -       split left on occurrences of sublist on the right
                          F        -       flatten the result
Jonathan Allan
źródło
1
Nie musisz używać sztuczek ewaluacyjnych ... zamiast tego użyj redukcji. 35 bajtów
Leaky Nun
1
Przeniesienie pierwszej linii do drugiej ... 34 bajtów
Leaky Nun
@LeakyNun Thanks! Próbowałem, ale nie mogłem dostać redukcji do pracy (stąd uciekłem się do używania eval).
Jonathan Allan
Fajnie, zastosowałem to samo podejście do œṣ- F- µÐLw nieco powiązanym problemie .
Zacharý
3

Pyth - 83 74 71 63 bajtów

K("\[]""{}""\(\)""<>")Fd{.psm*:@Kd*\\2k@QdU4JdVldFHK=:JHk))I!Jd

Spróbuj

1 : Kc "[] {} () <>") Fd {.ps * VR \ KQJdVldFHK =: JHk)) I! Jd

Również ta 53-bajtowa wersja dzięki Leaky Nun

Kc"\[] \{} \(\) <>")Fd{.ps*V-R\\KQJdVldFHK=:JHk))I!Jd

Tutaj

Maria
źródło
Galaretka pobita przez Pytha? Co to za czary?
ćpun matematyki
@mathjunkie Nie pokonałem Jelly; Zepsułem składnię wejściową.
Maria
... i myślę, że mogę to poprawić: D
Jonathan Allan
@JonathanAllan, więc może to odpowiedź.
Leaky Nun
1
Krok 1: zamiast tego ("\[]""{}""\(\)""<>")robimy c"\[] \{} \(\) <>")(podział na białe znaki); zamiast :@Kd*\\2ktego -@Kdnastępuje dwa odwrotne ukośniki; następnie zamiast mapowania U4robimy *V-R\\KQ(mnożymy równolegle dwie tablice). Pierwsza tablica jest generowana przy użyciu R, mianowicie -R\\kTo da ci 54-bajtową wersję
Leaky Nun
2

05AB1E , 33 32 30 27 25 bajtów

Zaoszczędź 7 bajtów dzięki Riley .

Kolejność wprowadzania to [(),<>,[],{}]

žu4äשJœJÙD[D®õ:DŠQ#]€g_Ï

Wypróbuj online!

Wyjaśnienie

žu                             # push the string "()<>[]{}"
  4ä                           # split in 4 parts
    ©                          # store a copy in register
     ×                         # repeat each bracket a number of times decided by input
      JœJÙ                     # get the unique permutations of the string of brackets
          D                    # duplicate
           [                   # start infinite loop
            D                  # duplicate current list of permutations
             ®õ:               # replace any instance of (), [], <>, {} 
                               # with an empty string
                DŠ             # duplicate and move down 2 places on stack
                  Q#           # if the operation didn't alter the list, exit loop
                    ]          # end loop
                     €g        # get the length of each subtring
                       _Ï      # keep only the strings in the original 
                               # list of unique permutations 
                               # that have a length of 0 in the resulting list
Emigna
źródło
1. Myślę, że :wektoryzacja (możesz pominąć większość nieskończonej pętli). 2. Jest o 1 bajt krótszy do użycia UXna początku i Xkiedy znów potrzebujesz listy nawiasów.
Riley
@ Riley: Próbowałem tylko na :początku, ale pojawiają się problemy, gdy na przykład wymiana na {}tworzy możliwe wymiany, ()ponieważ próbowaliśmy już wymienić wszystkie (). Dobra racja UXjednak. Możemy również uzyskać inny bajt ©®.
Emigna
Fakt, że Uwyskakuje na szczyt był zawsze frustrujący. Nie wiedziałam o tym ©®.
Riley
Patrzyłem na tę odpowiedź . Czy 05AB1E otrzymał aktualizację, która go zepsuła, czy też ta odpowiedź jest nieprawidłowa?
Riley
Ta odpowiedź działa na [([]{})<{[()<()>]}()>{}], ale nie na [({})<{[()<()>]}()>{}]. Jedyną różnicą jest usunięcie []. Zapytam o to w TNB.
Riley
2

Rubin , 123 bajty

->a{"<>{}[]()".gsub(/../){$&*a.pop}.chars.permutation.map(&:join).uniq.grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}

Wypróbuj online! Jest to jednak nieefektywne, więc nawet dane wejściowe przekroczą [1,2,1,1]limit czasu w Internecie. Przynajmniej wszystkie wymienione przykłady będą działać!

Wyjaśnienie

->a{                                        # Procedure with input a
    "<>{}[]()".gsub(/../){                  # For all pairs of brackets
                          $&*a.pop          # Pop last item in input, then repeat
                                            #   the bracket pair by that number
                                  }.chars   # Get characters
        .permutation                        # All permutations of characters
                    .map(&:join)            # For each permutation, join the chars
                                .uniq       # Get unique permutations only
            .grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}
                                            # Only return permutations that match
                                            #   this bracket-matching regex
Wartość tuszu
źródło