CSC A48: BANANA GAME

CSC A48: banana game

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.

For example, using a stack as our container, it is possible to read BANANA and print ANANAB. This can be done with the sequence IN,IN,IN,IN,IN,IN,EX,EX,EX,EX,EX,EX. However, that is not as short as possible. The shortest sequence is IN,PR,PR,PR,PR,PR,EX.

Also, it is not possible to read BANANA and print AAABNN. This is because in order to print AAA first, we must insert BNN into the stack, at which point it is not possible to print B before N.

Let's try playing the banana game.

Suppose we use a stack as our container.
1. Is it possible to read BANANA and print NAANBA?
2. Is it possible to read GRAPE and print PAGER?
3. Is it possible to read PEACH and print CHEAP?
4. Can we read APRICOT and print something interesting?
Repeat question 1 using a queue instead of a stack.
Invent a new container and/or new input/output strings, and challenge your classmates/friends.