My computer science professor introduced a very interesting game in order to get us (his students) familiar with the Stack and Queue ADTs. The description and rules of the game can be found here: 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:
- Finding the shortest solution
- Finding out whether a given game is possible
- 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.