9
\$\begingroup\$

You're looking at an avenue, and someone has left the trash out! You need to write a program to help fix the problem, by putting the trash into trashcans.

The task

The avenue is made up of a string of printable ASCII characters, e.g.:

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

Some of the brackets here are unmatched; those are just decoys. What we care about are the matched sets of brackets.

A trash can is a string starting with [ and ending with ], and with internally matched brackets and parentheses. For example, [] and [[](dust)[]] are trash cans in the above string.

A trash bag is a string starting with ( and ending with ), and with internally matched brackets and parentheses. For example, (dust) is a trash bag in the above string.

It's possible that some of the trash bags are in trash cans already. However, at least one will have been left out, and we need to move the trash bags so that they're all inside trash cans. Specifically, for each trash bag that isn't currently inside a trash can (i.e. a substring of that trash can), we need to remove it from its current location in the string, and insert it into a location that's inside a trash can instead.

There's an additional rule here. Because we don't want to spend too much money on garbage collectors, and their route takes them along the avenue from right to left, we want to move each trash bag to the left (most important criterion, assuming we have to move it at all) and the shortest distance possible (as long as it's moved to the left). So for example, the only correct output for

[can1](bag)[can2]

is

[can1(bag)][can2]

(moving the bag just one character leftwards). Additionally, the bags need to stay in the same relative order:

[can](bag1)(bag2)

has to become

[can(bag1)(bag2)]

(i.e. you can't put (bag2) to the left of (bag1).)

Clarifications

  • There won't be any trash bags to the left of the leftmost trash can; it will always be possible to can all the trash by moving it to the left.
  • There will always be at least one bag to move. There might be more than one.
  • There will never be a trash can inside a trash bag (the cans are too valuable to just throw away).
  • If a bag is already inside a can, just leave it alone.
  • It's OK for the input and output to differ in trailing whitespace (including newlines).

Examples:

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

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

  • Input: []] (unusable) door (filthy) car

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Close voters, could you explain what you're finding unclear? The post's going to be hard to fix without an explicit guide as to what's wrong with it. \$\endgroup\$ – user62131 Dec 6 '16 at 18:14
  • \$\begingroup\$ @ais523 I can't understand what the task is. Granted that might be because I'm tired but the current wording doesn't make much sense \$\endgroup\$ – Blue Dec 6 '16 at 18:38
  • 1
    \$\begingroup\$ Basically, for each substring that's inside parentheses but isn't inside brackets, move it to the left until it's also inside brackets. \$\endgroup\$ – user62131 Dec 6 '16 at 18:40
  • \$\begingroup\$ Because this problem's getting repeatedly closed and reopened, I edited it with my understanding of the problem. Hopefully I haven't changed the problem in the process. \$\endgroup\$ – user62131 Dec 7 '16 at 22:21
  • \$\begingroup\$ @ais523 This is fine by me. Thank you very much for all your editing. \$\endgroup\$ – Ewan Delanoy Dec 8 '16 at 7:46
3
\$\begingroup\$

JavaScript (ES6), 263 228 209 205 184 177 173 162 bytes

Any help with the code / regular expressions is greatly appreciated.

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``

An anonymous function; takes one String parameter, s, and returns the output.

/\[\[][\w()]*\[]]|\[]/g matches trash cans with nested trash bags, however I don't think it could check balanced brackets within trash bags if needed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.