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

Question

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 of the same letters to be together (continuous order) 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 their "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.

The characters in the 2nd stack don't have to be in any particular order, we just need to find a way so that in the 2nd set we have letters of the same kind together, without any different letter interrupting the sequence.

Here are some examples of accepted answers:

1. AAABCCCCCCCDDDDD
2. DDC
3. A
4. BBBDDDAAAAA
5. CCCCCCCC
6. ABCD
7. BBBCCCCCCBBB -> important example, this is also accepted because we consider 1st position neighbor to the last
8. AAAADAAAAA -> accepted for the same reason as 7)

Examples of not accepted answers:

1. AAAABBBBACCCDDDD -> Not accepted because As are not together
2. ABCDB -> Bs not grouped

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). Every time we perform an operation we have to check if the 2nd stack satisfies our constraints. If not then delete this node. If stack1 = empty for a node, then finish the program and return the sequence of moves.

In the above description I tried to think of an algorithm similar to backtracking, but with BFS instead of DFS and some improvements for this specific problem.

Questions

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

Answer 1

This can be solved in $O(n)$ time using BFS.

Consider any sequence of moves that ends in a valid solution (all letters are in the second stack and are grouped). At every intermediate point in this sequence, the letters on the second stack must be grouped. (If the letters in the second stack ever become ungrouped, then they stay ungrouped from there on -- there's no way to repair things from there on.)

Therefore, we can characterize the state at any intermediate point by the number of letters remaining in the first stack, whether the first stack was complemented or not, and the order of the letters in the second stack. In other words, the state is $\langle k, c, s \rangle$ where $0 \le k \le n$ and $c \in \{\text{True},\text{False}\}$ and $s \in \{A,B,C,D\}^*$ is a sequence of letters that describes the order the groups appear in the second stack. In particular, no letter can appear more than once in $s$, except that the first and last letter can be the same. Here I let $n$ denote the number of letters originally on the first stack. (Equivalently, you can let $s$ denote the sequence of letters in the second stack, but we only include states where the second stack is grouped.)

In particular, there are at most $178(n+1)$ states that you can be in at any intermediate point. (There are $n+1$ possible values for $k$, and $1+4+12+24+24+24=89$ possible values for $s$, and 2 values for $c$.)

You can explore the graph of possible states using breadth-first search. At each state, there are only three possible moves, so three edges out of that state; thus we explore a graph with at most $178(n+1)$ vertices and at most $3 \times 178(n+1)$ edges. The breadth-first search terminates when it reaches any state of the form $\langle n,c,s\rangle$. The running time is $O(n)$.