Создать все фрагменты Brain-Flak

14

Этот вопрос является вторым из нескольких заданий на День Рождения Brain-flak, предназначенных для празднования первого Дня рождения Brain-Flak! Вы можете найти больше информации о Дне Рождения Brain-Flak здесь

Вызов

Для этой задачи вы будете генерировать все полностью совпадающие строки из списка скобок. Чтобы позаимствовать определение DJMcMayhem полностью совпадающей строки:

  • Для этого вызова, «скобка» представляет собой любая из этих символов: ()[]{}<>.

  • Пара скобок считается "совпавшей", если открывающая и закрывающая скобки расположены в правильном порядке и в них нет символов, например

    ()
    []{}
    

    Или если каждый подэлемент внутри него также совпадает.

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

    Субэлементы также могут быть вложены в несколько слоев.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Строка считается «Полностью сопоставленной» тогда и только тогда, когда каждая пара скобок имеет правильную открывающую и закрывающую скобки в правильном порядке.


вход

Ваша программа или функция получит список из четырех неотрицательных чисел в любом удобном и согласованном формате. Это включает (но не ограничивается) список целых чисел, строку без разделителей или отдельные аргументы. Эти четыре числа представляют количество совпавших пар каждого типа скобок. Например, [1,2,3,4]будет представлять:

  • 1 пара ()

  • 2 пары {}

  • 3 пары []и

  • 4 пары <>

Вы можете выбрать, какой паре скобок соответствует каждый вход, если он согласован.

Выход

Вы должны вывести всю полностью совпадающую строку, которая может быть сформирована из этого списка скобок без дубликатов. Вывод может быть в любом приемлемом формате, который включает в себя печать строки без разделителей в STDOUT или список строк в качестве возвращаемого значения из функции.

Ваш алгоритм должен работать для любого произвольного ввода, но вам не нужно беспокоиться о пределах памяти, времени или целочисленного размера (например, если ваш ответ находится в C, вы не получите 2 33 в качестве ввода).

Это , поэтому выигрывает самый короткий ответ в байтах.

Пример ввода и вывода

Для этого примера я буду использовать тот же порядок ввода, что и выше.

Для каждого примера будет введена первая строка, а следующие - выход

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]

(){}[]<>  (){}[<>]  (){}<[]>  (){}<>[]  (){[]}<>  (){[]<>}  (){[<>]}
(){<[]>}  (){<>}[]  (){<>[]}  ()[{}]<>  ()[{}<>]  ()[{<>}]  ()[]{}<>
()[]{<>}  ()[]<{}>  ()[]<>{}  ()[<{}>]  ()[<>{}]  ()[<>]{}  ()<{}[]>
()<{}>[]  ()<{[]}>  ()<[{}]>  ()<[]{}>  ()<[]>{}  ()<>{}[]  ()<>{[]}
()<>[{}]  ()<>[]{}  ({})[]<>  ({})[<>]  ({})<[]>  ({})<>[]  ({}[])<>
({}[]<>)  ({}[<>])  ({}<[]>)  ({}<>)[]  ({}<>[])  ({[]})<>  ({[]}<>)
({[]<>})  ({[<>]})  ({<[]>})  ({<>})[]  ({<>}[])  ({<>[]})  ([{}])<>
([{}]<>)  ([{}<>])  ([{<>}])  ([]){}<>  ([]){<>}  ([])<{}>  ([])<>{}
([]{})<>  ([]{}<>)  ([]{<>})  ([]<{}>)  ([]<>){}  ([]<>{})  ([<{}>])
([<>{}])  ([<>]){}  ([<>]{})  (<{}[]>)  (<{}>)[]  (<{}>[])  (<{[]}>)
(<[{}]>)  (<[]{}>)  (<[]>){}  (<[]>{})  (<>){}[]  (<>){[]}  (<>)[{}]
(<>)[]{}  (<>{})[]  (<>{}[])  (<>{[]})  (<>[{}])  (<>[]){}  (<>[]{})
{()}[]<>  {()}[<>]  {()}<[]>  {()}<>[]  {()[]}<>  {()[]<>}  {()[<>]}
{()<[]>}  {()<>}[]  {()<>[]}  {([])}<>  {([])<>}  {([]<>)}  {([<>])}
{(<[]>)}  {(<>)}[]  {(<>)[]}  {(<>[])}  {}()[]<>  {}()[<>]  {}()<[]>
{}()<>[]  {}([])<>  {}([]<>)  {}([<>])  {}(<[]>)  {}(<>)[]  {}(<>[])
{}[()]<>  {}[()<>]  {}[(<>)]  {}[]()<>  {}[](<>)  {}[]<()>  {}[]<>()
{}[<()>]  {}[<>()]  {}[<>]()  {}<()[]>  {}<()>[]  {}<([])>  {}<[()]>
{}<[]()>  {}<[]>()  {}<>()[]  {}<>([])  {}<>[()]  {}<>[]()  {[()]}<>
{[()]<>}  {[()<>]}  {[(<>)]}  {[]()}<>  {[]()<>}  {[](<>)}  {[]}()<>
{[]}(<>)  {[]}<()>  {[]}<>()  {[]<()>}  {[]<>()}  {[]<>}()  {[<()>]}
{[<>()]}  {[<>]()}  {[<>]}()  {<()[]>}  {<()>}[]  {<()>[]}  {<([])>}
{<[()]>}  {<[]()>}  {<[]>()}  {<[]>}()  {<>()}[]  {<>()[]}  {<>([])}
{<>}()[]  {<>}([])  {<>}[()]  {<>}[]()  {<>[()]}  {<>[]()}  {<>[]}()
[(){}]<>  [(){}<>]  [(){<>}]  [()]{}<>  [()]{<>}  [()]<{}>  [()]<>{}
[()<{}>]  [()<>{}]  [()<>]{}  [({})]<>  [({})<>]  [({}<>)]  [({<>})]
[(<{}>)]  [(<>){}]  [(<>)]{}  [(<>{})]  [{()}]<>  [{()}<>]  [{()<>}]
[{(<>)}]  [{}()]<>  [{}()<>]  [{}(<>)]  [{}]()<>  [{}](<>)  [{}]<()>
[{}]<>()  [{}<()>]  [{}<>()]  [{}<>]()  [{<()>}]  [{<>()}]  [{<>}()]
[{<>}]()  [](){}<>  [](){<>}  []()<{}>  []()<>{}  []({})<>  []({}<>)
[]({<>})  [](<{}>)  [](<>){}  [](<>{})  []{()}<>  []{()<>}  []{(<>)}
[]{}()<>  []{}(<>)  []{}<()>  []{}<>()  []{<()>}  []{<>()}  []{<>}()
[]<(){}>  []<()>{}  []<({})>  []<{()}>  []<{}()>  []<{}>()  []<>(){}
[]<>({})  []<>{()}  []<>{}()  [<(){}>]  [<()>{}]  [<()>]{}  [<({})>]
[<{()}>]  [<{}()>]  [<{}>()]  [<{}>]()  [<>(){}]  [<>()]{}  [<>({})]
[<>{()}]  [<>{}()]  [<>{}]()  [<>](){}  [<>]({})  [<>]{()}  [<>]{}()
<(){}[]>  <(){}>[]  <(){[]}>  <()[{}]>  <()[]{}>  <()[]>{}  <()>{}[]
<()>{[]}  <()>[{}]  <()>[]{}  <({})[]>  <({})>[]  <({}[])>  <({[]})>
<([{}])>  <([]){}>  <([])>{}  <([]{})>  <{()}[]>  <{()}>[]  <{()[]}>
<{([])}>  <{}()[]>  <{}()>[]  <{}([])>  <{}[()]>  <{}[]()>  <{}[]>()
<{}>()[]  <{}>([])  <{}>[()]  <{}>[]()  <{[()]}>  <{[]()}>  <{[]}()>
<{[]}>()  <[(){}]>  <[()]{}>  <[()]>{}  <[({})]>  <[{()}]>  <[{}()]>
<[{}]()>  <[{}]>()  <[](){}>  <[]()>{}  <[]({})>  <[]{()}>  <[]{}()>
<[]{}>()  <[]>(){}  <[]>({})  <[]>{()}  <[]>{}()  <>(){}[]  <>(){[]}
<>()[{}]  <>()[]{}  <>({})[]  <>({}[])  <>({[]})  <>([{}])  <>([]){}
<>([]{})  <>{()}[]  <>{()[]}  <>{([])}  <>{}()[]  <>{}([])  <>{}[()]
<>{}[]()  <>{[()]}  <>{[]()}  <>{[]}()  <>[(){}]  <>[()]{}  <>[({})]
<>[{()}]  <>[{}()]  <>[{}]()  <>[](){}  <>[]({})  <>[]{()}  <>[]{}()
Райли
источник

Ответы:

6

Haskell , 128 байт

fявляется основной функцией, она принимает список Ints и возвращает список 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)

Попробуйте онлайн!

Как это устроено

  • fпреобразует свой входной список в список списков кортежей, каждый из которых содержит пару скобок, с каждым типом скобок в своем собственном подсписке. Например [1,2,0,0]становится [[('{','}')],[('[',']'),('[',']')]]. Затем он вызывает gс преобразованным списком.
  • Остальные функции используют частично проходящий стиль, смешанный со списком манипуляций. Каждая функция продолжения cберет список lоставшихся списков скобочных кортежей и возвращает список возможных строк, которые должны быть добавлены к тому, что уже было сгенерировано.
  • g lгенерирует список полностью совпадающих строк, формируемых с использованием всех скобок в l.
    • Это делается путем вызова l#gдля генерации строк, начинающихся с некоторой скобки. Рекурсивный gпараметр сам по себе используется как продолжение #, чтобы сгенерировать то, что следует за первым заключенным в скобки подэлементом.
    • В случае, когда таких строк нет (поскольку lвнутри не осталось скобок), gвозвращается [""]список, содержащий только пустую строку. Так как [""]сравнивает меньшие со всеми непустыми списками, производимыми с помощью #, мы можем сделать это, применив max.
  • l#cгенерирует строки, lначиная с по крайней мере одного заключенного в скобки подэлемента, оставляя его для продолжения, cчтобы определить, что следует за элементом.
    • bи eявляются выбранной парой скобок в кортеже xи rявляются списком оставшихся кортежей того же типа скобок.
    • r:filter(/=x:r)lэто lс кортежем xудалены, слегка отредактированный.
    • ?вызывается для генерации возможных подэлементов между bи e. Он получает свое собственное продолжение map(e:).c, которое ставит префиксы eк каждой из строк суффикса, сгенерированных c.
    • #сам добавляет инициал bко всем строкам, сгенерированным ?и c.
  • l?cгенерирует полностью согласованные строки, которые можно сформировать, используя ноль или более пар скобок l, и затем cпереходит к его продолжению для обработки того, что осталось. c lЧасть идет непосредственно , cбез добавления каких - либо подэлементов, в то время как l#(?c)использование #для генерации одного подэлемента , а затем вызвать (?c)рекурсивно для возможных дальнейших них.
Орджан Йохансен
источник
4

Желе , 50 40 34 байта

-6 байт благодаря Leaky Nun (получить сокращение на работу, где я не мог)

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

Просто и неэффективно.

Попробуйте онлайн! (время ожидания в TIO для [1,1,1,1] - да, неэффективно.)

Как?

Рекурсивно удаляет пары совпадающих скобок, которые располагаются рядом друг с другом, пока больше не удастся удалить каждую возможную строку, которую можно сформировать, сохраняя такие строки, которые сводятся к нулю (следовательно, имеют все совпадающее содержимое).

“()“{}“[]“<>”©ẋ"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
Джонатан Аллан
источник
1
Не нужно использовать трюки eval ... используйте вместо этого уменьшение. 35 байт
Утренняя монахиня
1
Перемещение первой строки во вторую ... 34 байта
Leaky Nun
@ LeakyNun Спасибо! Я пытался, но не мог получить снижение к работе (следовательно, прибегли к использованию Eval).
Джонатан Аллан
Ницца, я использовал тот же подход œṣ- F- µÐLв несколько связанных с проблемой .
Захари
3

Pyth - 83 74 71 63 байта

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

Попытайся

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

Кроме того, эта 53-байтовая версия благодаря Leaky Nun

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

Вот

Мария
источник
Желе избит Пифом? Что это за колдовство?
математик наркоман
@mathjunkie Я не победил Желе; Я облажался входной синтаксис.
Мария
... и я думаю, что могу улучшить: D
Джонатан Аллан
@JonathanAllan, так что это может ответить.
Утренняя монахиня
1
Шаг 1: вместо ("\[]""{}""\(\)""<>"), мы делаем c"\[] \{} \(\) <>")(разбить на пробел); вместо этого :@Kd*\\2kмы делаем -@Kdдве обратные косые черты; затем вместо отображения U4мы делаем *V-R\\KQ(умножаем два массива параллельно). Первый массив генерируется с помощью R, а именно -R\\kЭто даст вам 54-байтовую версию
Leaky Nun
2

05AB1E , 33 32 30 27 25 байтов

Сохранено 7 байтов благодаря Райли .

Порядок ввода [(),<>,[],{}]

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

Попробуйте онлайн!

объяснение

ž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
источник
1. Я думаю, что :векторизация (вы можете пропустить большую часть бесконечного цикла). 2. Это на 1 байт короче, чтобы использовать UXв начале и Xкогда вам снова понадобится список скобок.
Райли
@Riley: Я попробовал только :сначала, но у нас возникают проблемы, когда, например, замена {}создает возможные замены, ()поскольку мы уже пытались заменить все (). Хороший вопрос о том, UXхотя. Мы можем получить еще один байт ©®.
Emigna
Тот факт, что Uпоп-топ всегда был разочаровывающим. Я не знал о ©®.
Райли
Я смотрел на этот ответ . Получил ли 05AB1E обновление, которое его сломало, или этот ответ недействителен?
Райли
Этот ответ работает для [([]{})<{[()<()>]}()>{}], но не для [({})<{[()<()>]}()>{}]. Разница лишь в том, что они удалены []. Я спрошу об этом в ТНБ.
Райли
2

Рубин , 123 байта

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

Попробуйте онлайн! Тем не менее, это неэффективно, поэтому даже такие входные данные, как [1,2,1,1]тайм-аут, будут в режиме онлайн. Все перечисленные примеры будут работать, по крайней мере!

объяснение

->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
Значение чернил
источник