1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Can you credit the source where you encountered this task? What are the requirements on the final state of the second stack? You say "grouped", but what exactly does that mean? Must the letter be in any particular order? $\endgroup$ – D.W. Aug 7 '20 at 23:08
  • $\begingroup$ We just need all of the same letters to be together,not in any particular order.Thanks for your time,i will edit the post to make the problem clear.This question was a programming assignment in my university a year ago. We need this kind of sequence -> AAACCBD (all of the same letters together) $\endgroup$ – Ermolai Aug 8 '20 at 2:04
  • $\begingroup$ Did you try to run BFS? If you ignore infeasible states (which already violate conditions) and encode the second stack properly (as groups, i.e. $AABCCCCDA \to ABCDA$), I think it should be as efficient as one can get, up to a constant factor. $\endgroup$ – Dmitry Aug 8 '20 at 2:33
  • $\begingroup$ Running BFS in this problem is something like O(3^n) or O(2^n) because from each node there are at least 2-3 possible moves(hence new nodes).The example you wrote is not possible,because we can only use the 3 moves. In your example(AABCCCCDA) the solution is 7 "push moves" and then "reverse" and then 2 push. (ppppppprpp). The 2nd stack would become :(each set represents the 2nd stack after a move): {A}, {DA}.{CDA},{CCDA},{CCCDA},{CCCCDA},{BCCCCDA},{ADCCCCB},{AADCCCCB}. I hope my explanation is clear, let me know if i didn't explained it properly. BFS is definetely a solution though.... $\endgroup$ – Ermolai Aug 8 '20 at 3:08
  • $\begingroup$ Please edit the question to provide a more careful definition of "grouped". Don't just put it in the comments or just in the examples. $\endgroup$ – D.W. Aug 8 '20 at 8:38
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ @Dmitry, thanks! Fixed. $\endgroup$ – D.W. Aug 8 '20 at 8:42
  • $\begingroup$ Great answer! Could you explain how you arrive at 89 possible values for s. I don't seem to understand the sum or how s describes the order of the groups in the second stack. $\endgroup$ – droptop Aug 9 '20 at 10:18
  • $\begingroup$ @droptop, it's just counting. The exact number doesn't matter too much; the key part is that it's finite and not too large. s is something like ABC or CAD or ADA. ABC represents all possible second stacks of the form A*B*C* (e.g., AABBBBBBC). $\endgroup$ – D.W. Aug 9 '20 at 17:12
  • $\begingroup$ @D.W. Thank you for your help $\endgroup$ – Ermolai Aug 13 '20 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.