Вывернуть строку наизнанку

21

Сбалансированная строка - это строка скобок, ()так что каждая скобка может быть сопоставлена ​​с другой. Более строго они - последовательности, натянутые этой грамматикой:

S → (S)S | ε

Мы можем перевернуть строку "наизнанку":

  • Переключение всех вхождений (и )друг с другом

  • Перемещение символов от начала строки до конца, пока строка снова не будет сбалансирована.


Давайте сделаем пример.

Начнем со сбалансированной строки:

(()(())())

Затем мы переключаем парены, чтобы сделать

))())(()((

Затем переместите символы от начала строки до конца строки, пока строка не будет сбалансирована.

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

Вот наш результат!


Обратите внимание, что некоторые строки можно вывернуть наизнанку несколькими способами, например, строку

(()())

Когда вывернута наизнанку может быть:

()(())

или

(())()

Однако каждая строка имеет хотя бы одно решение .

задача

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

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

Тестовые случаи

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
Мастер пшеницы
источник
Гарантируется ли, что всегда есть решение?
Луис Мендо
@ LuisMendo Да, я доказал это. Если вы хотите увидеть доказательства, не стесняйтесь пинговать меня в чате.
Пшеничный волшебник
Спасибо. Мне достаточно знать это. Может быть, вам стоит записать это в задание, в противном случае вам нужно будет определить, что выводить, если нет решения
Луис Мендо,
по теме
officialaimm

Ответы:

9

Haskell , 124 120 119 117 113 110 109 106 105 104 101 98 байт

4 байта сэкономлено благодаря bartavelle!

3 байта сохранены благодаря Zgarb

1 байт сохранен благодаря Питеру Тейлору

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

until(!0)g.map d
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0
g(a:b)=b++[a]
d '('=')'
d _='('

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

объяснение

Эта программа определяет 4 функции, первая (!)определяет, сбалансирована ли строка. Его определяют следующим образом:

_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0

Эта проверка предполагает, что вход имеет одинаковое количество открытых и закрытых парен, благодаря предложению Питера Тейлора.

Следующий gбудет вращать строку один раз.

g(a:b)=b++[a]

Тогда у нас есть, dкоторый просто берет парен и отражает его

d '('=')'
d _='('

Наконец, у нас есть функция, которая нас интересует. Здесь мы используем представление без точек, until(!0)gсоставленное с map d, которое отображается dна вход и применяется, gпока результат не будет сбалансирован. Это точный процесс, описанный в вопросе.

until(!0)g.map d
Мастер пшеницы
источник
1
Вы можете очистить несколько байтов g x@(a:b)|x!0=x|1>0=g$b++[a]и снять с них символы d '('=')'.
bartavelle
@bartavelle Удаление паренов для dвызывает ошибку компилятора, поверьте мне, я пробовал. Но первое предложение приветствуется. Благодарность!
Пшеничный волшебник
1
Вы можете сохранить еще один байт, !потому что вам не нужно обрабатывать случаи, когда строка содержит неодинаковое количество открытых и закрытых скобок, поэтому вы можете поменять местами первые два случая и получить_!1=1<0 []!_=0<1
Питер Тейлор,
1
Используйте untilдля сокращения g: TiO
Zgarb
2
Я думаю , что должна быть достойной экономии, сделав dкарту '('на (-1)и что - нибудь еще 1, а затем две длинные случаи !могут быть объединены (i:a)!x=a!(x+i). Затем структура верхнего уровня нуждается в доработке, чтобы перейти map dв untilсостояние, и мне нужно бежать, чтобы у меня сейчас не было времени выяснить, какие комбинаторы требуются, чтобы склеить все это вместе.
Питер Тейлор
7

SOGL V0.12 , 12 11 байтов

↔]»:l{Ƨ()øŗ

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

Объяснение:

↔            mirror characters
 ]           do ... while the top of stack is truthy
  »            put the last letter at the start
   :           duplicate it
    l{         length times do
      Ƨ()        push "()"
         ø       push ""
          ŗ      replace ["()" with ""]
             if the string left on stack is empty (aka all matched parentheses could be removed), then stop the while loop

Примечание: l{можно заменить на ( для 10 байтов, но, к сожалению, это не реализовано.

dzaima
источник
Вы уверены, что зеркалирование персонажей работает? Я не знаю точно, что это значит, но моя интуиция подсказывает мне, что это также меняет порядок символов, что, я думаю, не сработает.
Пшеничный волшебник
1
@Olmman Он был предназначен, чтобы полностью изменить символы, но не делает (что сохраняет байт здесь!). Это в очереди V0.13s, чтобы изменить корыто. Пример
дзайма
5

CJam (20 символов)

q1f^0X${~_}%_:e>#)m<

Онлайн демо

или для того же количества символов

q1f^_,,{0W$@<~}$W=m<

Онлайн демо

рассечение

Две версии имеют общий колонтитул

q1f^    e# Read input and toggle least significant bit of each character
        e# This effectively swaps ( and )

m<      e# Stack: swapped_string index
        e# Rotates the string to the left index characters

Тогда бит в середине, очевидно, вычисляет, как далеко нужно повернуть. Оба они используют оценку и полагаются на (то, чтобы быть оператором декремента CJam и )оператором приращения.

0X$     e# Push 0 and a copy of the swapped string
{~_}%   e# Map: evaluate one character and duplicate top of stack
        e# The result is an array of the negated nesting depth after each character
_:e>    e# Copy that array and find its maximum value
#       e# Find the first index at which that value occurs
)       e# Increment

против

_,,     e# Create array [0 1 ... len(swapped_string)-1]
{       e# Sort with mapping function:
  0W$@  e#   Rearrange stack to 0 swapped_string index
  <~    e#   Take first index chars of swapped_string and evaluate
}$      e# The result is an array of indices sorted by the negated nesting depth
W=      e# Take the last one
Питер Тейлор
источник
3

JavaScript (ES6), 111 105 байт

(Сохранено 2 байта благодаря @CraigAyre, 2 байта благодаря @PeterTaylor, 2 байта благодаря @Shaggy.)

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

Ungolfed:

s=>(
  r=[...s].map(c=>'()'[c<')'|0]),  //switch "(" and ")"
  r.some(_=>(
    r.push(r.shift(i=0)),          //move last element to beginning of array, initialize i
    !r.some(c=>(i+=c<')'||-1)<0)   //check if balanced (i should never be less than 0)
  )),
  r.join``
)

Тестовые случаи:

Рик Хичкок
источник
3

Сетчатка , 46 38 байт

T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Редактировать: 8 байтов с помощью @MartinEnder. Первый этап просто переносит скобки, а второй этап ищет самый длинный суффикс, который является действительным сбалансированным префиксом, что, по-видимому, является достаточным условием для полной сбалансированности вращения. Балансировка определяется с помощью балансировочных групп. Конструкция ((\()|(?<-4>\)))+соответствует любому количеству (s плюс любое количество )s, если мы уже ( <-4>) видели столько же (s. Так как мы ищем только действительный префикс, нам не нужно совпадать с остальными )s.

Нил
источник
Обычно вместо того, чтобы повторять обе скобки, вы просто помещаете их в чередование, которое сохраняет байт ((\()|(?<-2>\))). Но ваша попытка просто вдохновил меня , чтобы найти совершенно новый подход , который позволяет экономить еще два: (?<-1>(\()*\))+. Это, безусловно, пригодится в будущем, так что спасибо. :)
Мартин Эндер
Еще короче определить вращение, сопоставляя первый суффикс, через который вы можете достичь конца строки, не получая отрицательной глубины стека: tio.run/…
Martin Ender
@MartinEnder Изначально я попробовал чередование, но я не мог заставить его работать в то время, но я не вижу, как оно (?<-1>(\()*\))+работает, так как кажется, что он хочет выскочить из 1стека, прежде чем что-то действительно совпадет ...
Нил
@MartinEnder Как оказалось, альтернативная версия кажется более подходящей для сопоставления сбалансированных префиксов.
Нил
1
Фактическое появление происходит в конце группы, а не в начале. Хороший вопрос с чередованием, чтобы избежать дублирования, \(*хотя.
Мартин Эндер
2

PHP, 110 108 байт

for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;

Запустите как трубу с -nRили проверьте это онлайн .

сломать

for($s=$argn;               # import input
    ;                       # infinite loop
    $p?die(strtr($s,"()",")(")) # 2. if balanced: invert, print and exit
    :$s=substr($s,1).$s[$i=0]   #    else: rotate string, reset $i to 0
)                               # 1. test balance:
    for($p=1;                   # init $p to 1
        $p&&$c=$s[$i++];)       # loop through string while $p is >0
        $p-=$c<")"?:-1;             # increment $p for ")", decrement else
Titus
источник
2

Октава, 62 байта

@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)

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

Функция, которая принимает строку в качестве входных данных и печатает все результаты.

Объяснение:

           hankel(a,shift(a,1))                                % generate a matrix of n*n where n= length(s) and its rows contain incresing circulraly shifted s
         x=...                 -39                             % convert matrix of "(" and ")" to a mtrix of 1 and 2
    ")("(x                        )                            % switch the parens
                                               2*x'-3          % convert [1 2] to [-1 1]
                                        cumsum(      )         % cumulative sum along the rows
                                    all(              >=0)'    % if all >=0
                                   (                       ,:) % extract the desired rows
rahnema1
источник
2

Mathematica, 78 байт

""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&
alephalpha
источник
1

JavaScript (ES6), 97 байт

f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')

Работает, рекурсивно вращая входную строку, пока ее транспонирование не будет сбалансировано, затем транспонируя ее.

Нил
источник
Просто красиво.
Рик Хичкок
1

APL (Dyalog Unicode) , 35 30 байт

Игра в гольф по-новому благодаря @ Adám

1⌽⍣{2::01∊⍎⍕1,¨⍺}')('['()'⍳⎕]

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

Игра в гольф продолжается.

объяснение

'()'⍳⎕              Find the index of each character of the input in the string '()'
                    (this is 1-indexed, so an input of '(())()' would give 1 1 2 2 1 2)
')('[...]           Find the index of the vector in the string ')('
                    This essentially swaps ')'s with '('s and vice versa
                   On this new string, do:
 1                   rotate it one to the left
                    Until this results in 1:
 1,¨⍺                 Concatenate each element of the argument with a 1
                      This inserts 1 one before each parenthesis
                     Stringify it
                     And evaluate it, if the parentheses are balanced, this produces no errors
 1                   Check if 1 belongs to evaluated value
                      If the parentheses were not matches during ⍎, this causes a syntax error
 2::0                 This catches a syntax error and returns 0
                      Essentially this code checks if the brackets are balanced or not
Kritixi Lithos
источник
0

Python 2 , 99 байт

r=[0];S=''
for c in input():b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
n=r.index(min(r))
print S[n:]+S[:n]

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

В функциональной форме для простых тестовых случаев:

Python 2 , 108 байт

def f(s):
 r=[0];S=''
 for c in s:b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
 n=r.index(min(r))
 return S[n:]+S[:n]

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

При этом используется немного другой подход - вместо рекурсивного поворота строки, если мы думаем о паренах как о приращении и уменьшении некоторого счетчика баланса, тогда у сбалансированной строки никогда не должно быть общей суммы приращений - приращений меньше 0.

Итак, мы берем

(()(())())

инвертировать парены:

))())(()((

и преобразовать его в список сумм приращений / уменьшений:

[-1,-2,-1,-2,-3,-2,-1,-2,-1,0]

-3 - минимум по индексу 4 (на основе нуля); поэтому мы хотим сдвинуться на этот индекс + 1. Это гарантирует, что совокупный прирост / уменьшение никогда не будет меньше 0; и составит до 0.

Час Браун
источник
На моем телефоне, поэтому я не могу проверить, но не могли бы вы сделать r=0,вместо r=[0]?
Cyoce
Если вы собираетесь с @ предложением Cyoce, вам нужно будет заменить r+=[r[-1]+2*b-1]с r+=r[-1]+2*b-1,а
овс
0

Clojure, 118 байт

#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))

Возвращает последовательность символов, поэтому я бы назвал это так:

(apply str (f "(()(())())"))
; "(()(())())"

Сначала переворачивайте скобки, затем повторяйте циклы до тех пор, пока кумулятивная сумма количества скобок станет отрицательной в некоторой точке последовательности.

NikoNyrh
источник
0

брейкфук , 82 байта

,[++[->->++<<]-[--->+>-<<]>-->+[-[-<<+>>>>+<<]],]+[<<]>>>[.[-]>>]<[<<]<[<<]>>[.>>]

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

объяснение

С каждым прочитанным символом счетчик изменяется следующим образом:

  • Счетчик начинается с 0.
  • После каждого )счетчик увеличивается на 1.
  • После каждого (счетчик уменьшается на 1, если только счетчик не был равен 0, в этом случае счетчик не изменяется.

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

,[                   Take input and start main loop
                     The cell one space right is the output cell (0 at this point),
                     and two spaces right is a copy of the previous counter value
  ++                 Add 2 to input
  [->->++<<]         Negate into output cell, and add twice to counter
  -[--->+>-<<]       Add 85 to output cell, and subtract 85 from counter
  >-->+              Subtract 2 from output cell and add 1 to counter
                     The output cell now has (81-input), and the counter has been increased by (2*input-80)
  [-[-<<+>>>>+<<]]   If the counter is nonzero, decrement and copy
,]
+[<<]                Go to the last position at which the counter is zero
>>>                  Go to following output character
[.[-]>>]             Output from here to end, clearing everything on the way
                     (Only the first one needs to be cleared, but this way takes fewer bytes)
<[<<]                Return to the same zero
<[<<]>>              Go to beginning of string
[.>>]                Output remaining characters
Nitrodon
источник