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. – Raphael Feb 14 '18 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? – nakamin Feb 14 '18 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 Feb 15 '18 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. – Yuval Filmus Feb 15 '18 at 8:27

Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming.

The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other direction – given numbers in increasing order, output them in a prescribed order).

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

When using a queue, if we don't use PR then the string would come out unchanged. When PR is allowed (which seems to go against Knuth's original intention), we obtain that a sequence is queue-sortable iff it contains no instance of the pattern 321.

Since then, the same problem has been studied with various other data structures (mostly, it seems, in the 1970s). The recent papers Permutations sortable by two stacks in parallel and quarter plane walks and Permutations sortable by deques and by two stacks in parallel contain many references on this interesting combinatorial pursuit.