Gather the trash

Question

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

Answer 1

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.