I don't have time to really work up a solution but your problem is screaming regex to me. I would look at the possibility of compiling a regex representing all the possible solutions. Then match that regex against the input string to obtain the shortest solution. If a regex isn't flexible enough you might look at a parser module like Parse::Yapp or Parse::RecDescent.

-sam