Пузырьковые скобки!

27

Там являются несколько вопросов на этом сайте о балансировании скобки, и проверок , является ли уравновешиваются скобки. Я предлагаю, что пришло время использовать эти сбалансированные скобки для чего-то!

В математике и программировании скобки похожи на пузыри, изолирующие все внутри от всего, что находится внутри, так что все, что внутри, может делать свое дело в мире, а то, что снаружи, видит только один объект. Тем не менее, цепочка скобок является одномерной, в то время как пузыри, как правило, по крайней мере двумерные. Это означает, что пузырьки могут свободно перемещаться друг относительно друга, если они никогда не касаются друг друга и не пересекаются между внутренней и внешней частью любых других пузырьков.

Вызов

Входные данные представляют собой строку совпадающих скобок одного типа: круглую (), квадратную [], фигурную {}или угловую <>. Вам решать, какой тип вы хотите, чтобы ваша программа принимала, и программа, которая принимает только один вид скобок, принимается. (Воображаемый бонус, если ваша программа может обработать любой из них, огромные воображаемые бонусные баллы, если он может обрабатывать все их в одном входе.) Вход не может содержать ничего в скобках, хотя конечные пробелы разрешены.

Выходными данными являются все возможные реорганизации (в произвольном порядке, включая исходный ввод) тех скобок, которые дают одинаковую конфигурацию пузырьков, без двух одинаковых строк. Это означает, что при вводе ()(), вывод также является простым ()(), хотя технически это два пузыря, которые могут поменяться местами. Для огромного воображаемого бонуса, {}[]()конечно , ввод воли приведет к выводу 6 различных элементов / строк / линий.

Две конфигурации пузырьков "одинаковы", если вы можете превратить один в другой, перемещая пузырьки, не позволяя ни одному пузырю пересекаться из другого пузырька наружу или снаружи внутрь. Если вы сравниваете вложенные скобки с деревьями (каждая совпавшая пара является одним узлом, и каждая совпавшая пара внутри является подузлом, и каждая совпавшая пара внутри имеет подузел тех же и т. Д.), Где подузлы любого данного узла упорядочены тогда единственная конфигурация пузырьков - это дерево, где узлы неупорядочены.

Любой разумный формат вывод будет делать, как и возвращает список строк или список списка отдельных символов или одной строки с каким - то пробелом, или печатью на stdoutили stderrс какой - либо формой видимого символа пробела (обычно перевод строки или пробела) между каждая реорганизация.

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

Оценка - это количество байтов в коде; самый низкий счет для каждого языка выигрывает. Вы можете заметить, получаете ли вы воображаемый бонус, обычный или массовый, но это не влияет на ваш счет. Реальные бонусы слишком сложно сбалансировать правильно.

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

Пример 1:

Входные данные:

()(())

Выход:

()(())
(())()

Пример 2:

Входные данные:

(()())()()

Выход:

(()())()()
()(()())()
()()(()())

Пример 3:

Входные данные:

(()(()))()

Выход:

((())())()
()((())())
(()(()))()
()(()(()))
Артур
источник
Почему мы не можем получить ((()))в примере 1? или ()()()? Кажется, вам не хватает перестановок для каждого входа.
Пшеничный Волшебник
@WheatWizard Это не даст такую ​​же конфигурацию пузырьков: один большой пузырь с двумя пустыми пузырьками внутри.
Артур
@WheatWizard, насколько я понимаю, вы не можете вынести пузырь из другого пузыря наружу или наоборот.
Гжегож Пулавски
@WheatWizard Я добавил небольшое объяснение.
Артур
7
Кстати, добро пожаловать в PPCG! Хороший первый вызов!
г-н Xcoder

Ответы:

4

CJam , 18 байт

{~{_{{B}%e!}&}:B~}

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

-2 благодаря Business Cat .

Получает входные данные в виде строки, содержащей только []. Возвращает список перестановок (пустые списки такие же, как пустые строки в CJam, поэтому вместо них []вы получите "").

Эрик Outgolfer
источник
Почему выход для [][]всего ""? - Должен ли вход заключаться в дополнительный набор []? Если так, то почему существует дополнительный набор, []который (возможно?) Представляет собой вывод для вышеупомянутого примера? Кроме того, вопрос гласит: «Вы должны использовать в выводе те же скобки, что и в вводе. Помимо скобок, переносов и пробелов, как указано здесь, и независимо от того, какой разделитель вы используете, ничего не должно печататься», поэтому я ' Я не уверен, что сочетание []и ""является приемлемым.
Джонатан Аллан
@JonathanAllan Да, я думаю, вам нужно заключить [][]дополнительную пару []. Для других я не совсем уверен, что они недействительны.
Эрик Outgolfer
Я думаю, что вы можете сделать _{{B}%e!}&вместо_!!{{B}%e!}*
Business Cat
@BusinessCat ли &короткое замыкание или что-то?
Эрик Outgolfer
&запускает блок, только если другое значение верно
Business Cat
4

Haskell , 227 210 208 205 байт

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

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

Этот был жестким!

Немного поиграл в гольф

Сохранено два байта благодаря Laikoni

Сэкономьте два байта благодаря Брюсу Форте

Я не уверен, что это работает в каждом случае. Некоторые объяснения:

  • a!xдобавить строку xв последний список строк в a(тип a [[String]])

  • snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])использует более короткое условное выражение для выражения простой идеи: разбить строку на корень )( s. Например "(()(()))()"дает ["()(())", ""].

  • Нам нужно обработать каждую часть разбиения, затем собрать и объединить все строки, чтобы получить правильный вывод:

    1. hобрабатывает список частей: он применяется vк первой части и объединяет результат с процессом остальных частей.

    2. v агрегирует результаты для каждой перестановки частей и удаляет дубликаты.

Чтобы добавить более широкое представление: у вас есть в основном дерево (не двоичное) с пустыми узлами. Оставь это (). Вы должны произвести все перестановки ветвей для каждого узла, но вы не можете взять ветку из узла и поместить ее в другой узел. Я сделал своего рода углубленный первый поиск.

jferard
источник
Вы можете опустить круглые скобки init a.
Лайкони
2

Python 2, 353 350 331 байт

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Получает строку в ()качестве входных данных и печатает результат.

Попробуй это здесь!

Я избегал использовать itertools.permutationsс помощью ответа Паоло на этот вопрос .

Спасибо Business Cat за то, что он нашел 3 байта, и спасибо мистеру Xcoder за невероятные 19 байтов!

объяснение

  1. Создайте список кортежей индексов каждой ()пары во входной строке.
  2. Удалите любые кортежи из списка, которые окружены другой ()парой.
  3. Нарезать строку по индексам оставшихся кортежей.
  4. Составьте список каждой перестановки из списка срезов.
  5. Присоединяйтесь к списку с новой строкой для печати.
Сольватация
источник
Я вижу несколько байтов, которые можно побрить. У вас есть пробелы, которые можно удалить, а именно после printи в таких местах, как i+1 if(может быть i+1if). Кроме того, в одном месте вы y[0:i]можете опустить 0.
Business Cat
Спасибо, @BusinessCat! Моя IDE жалуется на некоторые из них, поэтому я все еще изучаю некоторые хитрости в гольф-коде.
Сольватация
342 байта (-8 байтов) , переупорядочив некоторые условные выражения для удаления пробелов.
г-н Xcoder
340 байтов (-10 байтов) с помощью лексикографического сравнения по проверке равенства.
г-н Xcoder
331 байт (-19 байт), поскольку запрос позволяет вернуть список строк. ура, мы победили Mathematica :-)
г-н Xcoder
2

JavaScript (Firefox 30-57), 222 байта

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Принимает []строки. Объяснение:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s
Нил
источник
0

Mathematica, 337 байт

Не для того, чтобы получить очки для игры в гольф, но чтобы показать использование Permutationsи Distributeв этой проблеме. Хотя могут быть и лучшие подходы.

( seq: последовательность,: altальтернативы)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Возьмите ввод как строку, используя фигурные скобки {и }. Выведите многострочную строку.

user202729
источник