Этот вопрос является вторым из нескольких заданий на День Рождения 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]
(){}[]<> (){}[<>] (){}<[]> (){}<>[] (){[]}<> (){[]<>} (){[<>]}
(){<[]>} (){<>}[] (){<>[]} ()[{}]<> ()[{}<>] ()[{<>}] ()[]{}<>
()[]{<>} ()[]<{}> ()[]<>{} ()[<{}>] ()[<>{}] ()[<>]{} ()<{}[]>
()<{}>[] ()<{[]}> ()<[{}]> ()<[]{}> ()<[]>{} ()<>{}[] ()<>{[]}
()<>[{}] ()<>[]{} ({})[]<> ({})[<>] ({})<[]> ({})<>[] ({}[])<>
({}[]<>) ({}[<>]) ({}<[]>) ({}<>)[] ({}<>[]) ({[]})<> ({[]}<>)
({[]<>}) ({[<>]}) ({<[]>}) ({<>})[] ({<>}[]) ({<>[]}) ([{}])<>
([{}]<>) ([{}<>]) ([{<>}]) ([]){}<> ([]){<>} ([])<{}> ([])<>{}
([]{})<> ([]{}<>) ([]{<>}) ([]<{}>) ([]<>){} ([]<>{}) ([<{}>])
([<>{}]) ([<>]){} ([<>]{}) (<{}[]>) (<{}>)[] (<{}>[]) (<{[]}>)
(<[{}]>) (<[]{}>) (<[]>){} (<[]>{}) (<>){}[] (<>){[]} (<>)[{}]
(<>)[]{} (<>{})[] (<>{}[]) (<>{[]}) (<>[{}]) (<>[]){} (<>[]{})
{()}[]<> {()}[<>] {()}<[]> {()}<>[] {()[]}<> {()[]<>} {()[<>]}
{()<[]>} {()<>}[] {()<>[]} {([])}<> {([])<>} {([]<>)} {([<>])}
{(<[]>)} {(<>)}[] {(<>)[]} {(<>[])} {}()[]<> {}()[<>] {}()<[]>
{}()<>[] {}([])<> {}([]<>) {}([<>]) {}(<[]>) {}(<>)[] {}(<>[])
{}[()]<> {}[()<>] {}[(<>)] {}[]()<> {}[](<>) {}[]<()> {}[]<>()
{}[<()>] {}[<>()] {}[<>]() {}<()[]> {}<()>[] {}<([])> {}<[()]>
{}<[]()> {}<[]>() {}<>()[] {}<>([]) {}<>[()] {}<>[]() {[()]}<>
{[()]<>} {[()<>]} {[(<>)]} {[]()}<> {[]()<>} {[](<>)} {[]}()<>
{[]}(<>) {[]}<()> {[]}<>() {[]<()>} {[]<>()} {[]<>}() {[<()>]}
{[<>()]} {[<>]()} {[<>]}() {<()[]>} {<()>}[] {<()>[]} {<([])>}
{<[()]>} {<[]()>} {<[]>()} {<[]>}() {<>()}[] {<>()[]} {<>([])}
{<>}()[] {<>}([]) {<>}[()] {<>}[]() {<>[()]} {<>[]()} {<>[]}()
[(){}]<> [(){}<>] [(){<>}] [()]{}<> [()]{<>} [()]<{}> [()]<>{}
[()<{}>] [()<>{}] [()<>]{} [({})]<> [({})<>] [({}<>)] [({<>})]
[(<{}>)] [(<>){}] [(<>)]{} [(<>{})] [{()}]<> [{()}<>] [{()<>}]
[{(<>)}] [{}()]<> [{}()<>] [{}(<>)] [{}]()<> [{}](<>) [{}]<()>
[{}]<>() [{}<()>] [{}<>()] [{}<>]() [{<()>}] [{<>()}] [{<>}()]
[{<>}]() [](){}<> [](){<>} []()<{}> []()<>{} []({})<> []({}<>)
[]({<>}) [](<{}>) [](<>){} [](<>{}) []{()}<> []{()<>} []{(<>)}
[]{}()<> []{}(<>) []{}<()> []{}<>() []{<()>} []{<>()} []{<>}()
[]<(){}> []<()>{} []<({})> []<{()}> []<{}()> []<{}>() []<>(){}
[]<>({}) []<>{()} []<>{}() [<(){}>] [<()>{}] [<()>]{} [<({})>]
[<{()}>] [<{}()>] [<{}>()] [<{}>]() [<>(){}] [<>()]{} [<>({})]
[<>{()}] [<>{}()] [<>{}]() [<>](){} [<>]({}) [<>]{()} [<>]{}()
<(){}[]> <(){}>[] <(){[]}> <()[{}]> <()[]{}> <()[]>{} <()>{}[]
<()>{[]} <()>[{}] <()>[]{} <({})[]> <({})>[] <({}[])> <({[]})>
<([{}])> <([]){}> <([])>{} <([]{})> <{()}[]> <{()}>[] <{()[]}>
<{([])}> <{}()[]> <{}()>[] <{}([])> <{}[()]> <{}[]()> <{}[]>()
<{}>()[] <{}>([]) <{}>[()] <{}>[]() <{[()]}> <{[]()}> <{[]}()>
<{[]}>() <[(){}]> <[()]{}> <[()]>{} <[({})]> <[{()}]> <[{}()]>
<[{}]()> <[{}]>() <[](){}> <[]()>{} <[]({})> <[]{()}> <[]{}()>
<[]{}>() <[]>(){} <[]>({}) <[]>{()} <[]>{}() <>(){}[] <>(){[]}
<>()[{}] <>()[]{} <>({})[] <>({}[]) <>({[]}) <>([{}]) <>([]){}
<>([]{}) <>{()}[] <>{()[]} <>{([])} <>{}()[] <>{}([]) <>{}[()]
<>{}[]() <>{[()]} <>{[]()} <>{[]}() <>[(){}] <>[()]{} <>[({})]
<>[{()}] <>[{}()] <>[{}]() <>[](){} <>[]({}) <>[]{()} <>[]{}()
Ответы:
Haskell , 128 байт
f
является основной функцией, она принимает списокInt
s и возвращает списокString
s.Попробуйте онлайн!
Как это устроено
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)
рекурсивно для возможных дальнейших них.источник
Желе ,
50 4034 байта-6 байт благодаря Leaky Nun (получить сокращение на работу, где я не мог)
Просто и неэффективно.
Попробуйте онлайн! (время ожидания в TIO для [1,1,1,1] - да, неэффективно.)
Как?
Рекурсивно удаляет пары совпадающих скобок, которые располагаются рядом друг с другом, пока больше не удастся удалить каждую возможную строку, которую можно сформировать, сохраняя такие строки, которые сводятся к нулю (следовательно, имеют все совпадающее содержимое).
источник
œṣ
-F
-µÐL
в несколько связанных с проблемой .Pyth -
83747163 байтаПопытайся
1 : Kc "[] {} () <>") Fd {.ps * VR \ KQJdVldFHK =: JHk)) I! Jd
Кроме того, эта 53-байтовая версия благодаря Leaky Nun
Вот
источник
("\[]""{}""\(\)""<>")
, мы делаемc"\[] \{} \(\) <>")
(разбить на пробел); вместо этого:@Kd*\\2k
мы делаем-@Kd
две обратные косые черты; затем вместо отображенияU4
мы делаем*V-R\\KQ
(умножаем два массива параллельно). Первый массив генерируется с помощьюR
, а именно-R\\k
Это даст вам 54-байтовую версию05AB1E ,
3332302725 байтовСохранено 7 байтов благодаря Райли .
Порядок ввода
[(),<>,[],{}]
Попробуйте онлайн!
объяснение
источник
:
векторизация (вы можете пропустить большую часть бесконечного цикла). 2. Это на 1 байт короче, чтобы использоватьUX
в начале иX
когда вам снова понадобится список скобок.:
сначала, но у нас возникают проблемы, когда, например, замена{}
создает возможные замены,()
поскольку мы уже пытались заменить все()
. Хороший вопрос о том,UX
хотя. Мы можем получить еще один байт©®
.U
поп-топ всегда был разочаровывающим. Я не знал о©®
.[([]{})<{[()<()>]}()>{}]
, но не для[({})<{[()<()>]}()>{}]
. Разница лишь в том, что они удалены[]
. Я спрошу об этом в ТНБ.Рубин , 123 байта
Попробуйте онлайн! Тем не менее, это неэффективно, поэтому даже такие входные данные, как
[1,2,1,1]
тайм-аут, будут в режиме онлайн. Все перечисленные примеры будут работать, по крайней мере!объяснение
источник