Minimum number of given operations in order to group letters in a string


Description

Suppose we have a string containing letters ‘A’,’B’,’C’,’D’, and the characters are placed in a stack.We also have an empty stack.Ultimately,we want all letters grouped in the 2nd stack,using only 3 operations:

  • push("p"): Removes an items from the bottom of the 1st stack and place it to the top of the 2nd
  • complement("c"): Replace every all letters of the 1st stack with they "complements".The pairs are A – B and C – D
  • reverse("r"): Reverse the content of the 2nd stack.The top becomes bottom and bottom->top.

Example of moves

| Move | First Stack | Second Stack | +------+-------------+--------------+ |      | DBACA       |              | +------+-------------+--------------+ | p    | DBAC        | A            | +------+-------------+--------------+ | p    | DBA         | CA           | +------+-------------+--------------+ | r    | DBA         | AC           | +------+-------------+--------------+ | p    | DB          | AAC          | +------+-------------+--------------+ | c    | CA          | AAC          | +------+-------------+--------------+ | p    | C           | AAAC         | +------+-------------+--------------+ | r    | C           | CAAA         | +------+-------------+--------------+ | p    |             | CCAAA        | +------+-------------+--------------+ 

Note that the example above finds a solution,but not the minimum solution.The correct answer would be "ppr ppp"

Correct examples

Spaces in the sequence have no meaning and are added for readability purposes.

+------------------------+-------------------------------------+ | First Stack (input)    | Moves (output)                      | +------------------------+-------------------------------------+ | DD                     | pp                                  | +------------------------+-------------------------------------+ | BADA                   | ppr pp                              | +------------------------+-------------------------------------+ | DADA                   | ppc pp                              | +------------------------+-------------------------------------+ | DBACA                  | pprppp                              | +------------------------+-------------------------------------+ | BDA CACA               | ppr prp rppp                        | +------------------------+-------------------------------------+ | CAC DCDC               | pcp cpc pcp cpp                     | +------------------------+-------------------------------------+ | ADA DBD BCB DBCB       | ppr pcr pcr prp rpr prp rpr prp rp  | +------------------------+-------------------------------------+ | DAB BCC DCC BDC ACD CC | ppc pcp cpp rpp rpp cpc ppr ppc prp | +------------------------+-------------------------------------+ 

Brute force approach

We could just use brute force approach,calculating all possible moves until the first stack is empty.This could be done using BFS or A* algorithms.

For example,we could initialize an empty queue,start from a parent node and create 3 new nodes for every possible move.Then add these nodes to the queue.Every time remove a node from the queue and apply the operations.Save the sequence of moves while nodes are created.If the last move was a "c",then skip "c" operation for this node.The same is true about "r" operation (no repetitive c’s or r’s).If stack1 = empty for a node,then finish the program and return the sequence of moves.

Questions

Is there a better way to solve this problem? Can we apply some heuristics as improvement in the brute force approach? Thank you in advance.