Analysis of the Banana Game

Question

My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.

Game Description

The banana game is played with a container -- e.g., a queue or a stack. The object of the game is to find a sequence of steps that will read a given string (i.e., sequence of letters) and print a given output string. There are 3 types of steps.

• IN: Read the next letter from input and insert it into the container.
• PR: Read the next letter from input and print it.
• EX: Extract a letter from the container and print it.

If such a sequence exists, then we want to find a shortest one. Otherwise we want to briefly and clearly explain why no such sequence exists. Link to original text: https://www.utsc.utoronto.ca/~nick/CSCA48/banana.html

Since the purpose of the game was only to play it, our professor never discussed any theory, or strategy for the game. Some students have come up with ways to generate solutions (for example by enumerating all sequences of valid moves and seeing if any of the results are equal to the destination string), but being first year students, none of our solutions were particularly novel or interesting. I have searched for a similar game, but my searches have not been fruitful. I am really interested in seeing the minimum time complexity algorithms for:

1. Finding the shortest solution
2. Finding out whether a given game is possible
3. Checking if a given solution is correct

Perhaps there are ways of representing this game that will make these thing easier to do (a graph or a tree)? I have also thought about this as some special version of The Tower of Hanoi (at least for the Stack ADT), but in this game you are not allowed to transfer characters back to the original "peg" so I guess it isn't very helpful. Note: this game can also be played with an ADT called Bucket which can only store one element.