# 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.