Zbierz śmieci

9

Patrzysz na aleję, a ktoś wyrzucił śmieci! Musisz napisać program, który pomoże rozwiązać problem, umieszczając kosz w koszach.

Zadanie

Aleja składa się z ciągu drukowalnych znaków ASCII, np .:

[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)

Niektóre nawiasy tutaj nie mają sobie równych; to tylko wabiki. Dbamy o dopasowane zestawy nawiasów.

Kosza jest ciągiem zaczynając [i kończąc ], i wewnętrznie dopasowane nawiasów i nawiasów. Na przykład, []i [[](dust)[]]są kosze na śmieci w powyższym ciągu.

Worek śmieci jest ciągiem zaczynając (i kończąc ), i wewnętrznie dopasowane nawiasów i nawiasów. Na przykład (dust)jest worek na śmieci w powyższym sznurku.

Możliwe, że niektóre worki na śmieci są już w pojemnikach. Jednak przynajmniej jeden zostanie pominięty i musimy przenieść worki na śmieci, aby wszystkie znajdowały się w pojemnikach na śmieci. W szczególności dla każdego worka na śmieci, który nie znajduje się obecnie w koszu (tj. Podłoży tego kosza), musimy go usunąć z jego bieżącej lokalizacji w ciągu i zamiast tego wstawić do miejsca, które znajduje się w koszu .

Tutaj jest dodatkowa zasada. Ponieważ nie chcemy wydawać zbyt dużo pieniędzy na śmieciarki, a ich trasa wiedzie ich aleją od prawej do lewej, chcemy przenieść każdy worek na śmieci w lewo (najważniejsze kryterium, zakładając, że musimy go przenieść wszystkie) i najkrótszą możliwą odległość (o ile jest przesunięta w lewo). Na przykład jedyne prawidłowe wyjście dla

[can1](bag)[can2]

jest

[can1(bag)][can2]

(przesuwając torbę tylko jedną postać w lewo). Ponadto torby muszą pozostać w tej samej względnej kolejności:

[can](bag1)(bag2)

musi się stać

[can(bag1)(bag2)]

(tzn. nie możesz umieścić (bag2)na lewo od (bag1).)

Wyjaśnienia

  • Po lewej stronie lewej skrzynki na śmieci nie będzie żadnych worków na śmieci; zawsze będzie można zebrać wszystkie śmieci, przesuwając je w lewo.
  • Zawsze będzie co najmniej jedna torba do przeniesienia. Może być więcej niż jeden.
  • Nigdy nie będzie kosza na śmieci w koszu na śmieci (puszki są zbyt cenne, aby je wyrzucić).
  • Jeśli worek znajduje się już w puszce, zostaw go w spokoju.
  • Dopuszczalne jest, aby dane wejściowe i wyjściowe różniły się końcowymi spacjami (w tym znakami nowej linii).

Przykłady:

  • Wejście: [[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)

    Wynik: [[](dust)[]((paper)vomit)(broken(glass))] car [[(rotten)(dirty)] fence

  • Wejście: []] (unusable) door (filthy) car

    Wynik : [(unusable)(filthy)]] door car

Ewan Delanoy
źródło
5
Bliscy wyborcy, czy moglibyście wyjaśnić, co jest niejasne? Post będzie trudny do naprawienia bez wyraźnego przewodnika, co jest z nim nie tak.
@ ais523 Nie rozumiem, co to za zadanie. To prawda, że ​​jestem zmęczony, ale obecne brzmienie nie ma większego sensu
Blue
1
Zasadniczo dla każdego podłańcucha, który znajduje się w nawiasach, ale nie znajduje się w nawiasach, przesuń go w lewo, aż znajdzie się również w nawiasach.
Ponieważ problem ten jest wielokrotnie zamykany i ponownie otwierany, zredagowałem go, rozumiejąc problem. Mam nadzieję, że nie zmieniłem problemu w tym procesie.
@ ais523 To dla mnie w porządku. Dziękuję bardzo za całą edycję.
Ewan Delanoy,

Odpowiedzi:

3

JavaScript (ES6), 263 228 209 205 184 177 173 162 bajtów

Każda pomoc związana z kodem / wyrażeniami regularnymi jest bardzo mile widziana.

f=s=>s.match(t=/\[\[][\w()]*\[]]|\[]/g,g=/\([\w()]*\)/g,i=0,u=s.split(t).filter(e=>e)).map(e=>e.substr(0,e.length-1)+u[i].match(g).join``+`]`+u[i++].replace(g,``)).join``

Anonimowa funkcja; pobiera jeden Stringparametr si zwraca wynik.

/\[\[][\w()]*\[]]|\[]/g pasuje do pojemników na śmieci z zagnieżdżonymi workami na śmieci, ale nie sądzę, aby w razie potrzeby sprawdził zrównoważone wsporniki w workach na śmieci.

XavCo7
źródło