# Analysis of the Banana Game

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.

• 1) Please state the game here and/or give a robust reference to the literature; links break. 2) Please ask an actual question, but only one per post. 3) After doing 2, please choose a descriptive title. Commented Feb 14, 2018 at 22:41
• Does that mean I should make 3 separate questions? Wouldn't it be better for all discussion to be in one place? I also don't know how to make the title more descriptive... this is a made up game (as far as I know) and I can't really say anything to summarize it in the title since it will be too long. Perhaps I should be posting this question somewhere else? Commented Feb 14, 2018 at 22:49
• I also think that your post should be rephrased (possibly shortened). It seems like description is quite accurate, but the 3 questions are redundant. If you can find the shortest solution then you can use it to find if game is possible. Checking if solution is good, have you thought about this? if there is input, machine and solution you can emulate it, not very costly operation. "Optimal sequence of moves on stack to translate input into output" - an example title, not particularly good, but tells more than "banana game", which is not widely recognised game. As a reminder, this is Q&A site :)
– Evil
Commented Feb 15, 2018 at 6:00
• 1. What do you mean by shortest solution? 3. This is easy – you just simulate the steps and see what pops out. Commented Feb 15, 2018 at 8:27

When using a stack, there is no need to use operation PR, since it can be simulated by executing IN and then EX. It is a classical result that a sequence is stack-sortable iff it contains no instance of the pattern 231, that is, there are no three numbers $\ldots,a,\ldots,b,\ldots,c$ such that $c<a<b$.