Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows. ``` Hanoi(n, src, dst, tmp): if n > 0 hanoi(n-1, src, dst, tmp) move disk n from src to dst hanoi(n-1, tmp, dst, src) ``` And iteratively, If n is even, swap pegs 1 and 2. At the ith step, make the only legal move that avoids peg i mod 3. If there is no legal move, then all disks are on peg i mod 3, and the puzzle is solved. ``` hanoi(n, s, t, d) pegs[s = [1,2,..,n], t, d] if n is even swap pegs[1], pegs[2] i the top of pegs[(avoid + 2) mod 3] move the top of pegs[(avoid + 1) mod 3] to pegs[(avoid + 2) mod 3] else move the top of pegs[(avoid + 2) mod 3] to pegs[(avoid + 1) mod 3] i++ ``` I'm having a hard time figuring out how to put this into mathematical expressions or a recurrence-relation which I can then perform induction on to show their equivalence. My searching has only brought me problems that deal with the complexity or correctness of algorithms, I'm interested in showing that every $i$th move the performed are identical.

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

Recently, I came across this problem, a variation of towers of hanoi. Problem statement: Consider the folowing variation of the well know problem Towers of Hanoi: We are given $n$ towers and m disks of sizes $1,2,3,\dots,m$ stacked on some towers. Your objective is to transfer all the disks to the $k^{\text{th}}$ tower in as few moves as you can manage, but taking into account the following rules: - moving only one disk at a time, - never moving a larger disk one onto a smaller one, - moving only between towers at distance at most $d$. (Limits in the original problem: $3 \le n \le 1000$ and $m \le 100$. Number of test cases $\le 1000$. You can assume that all the problems can be solved in not more than $20000$ moves.) It's an interesting one. The classic towers of hanoi problem has one source, destination and temporary tower that is used to move the disks from source to destination. The problem pitched on that site basically has an initial and final configuration. How does one approach this problem?

We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T_3$. If $T(p,q)$ is a recurrence relation of minimum number of moves we make to move $p$ disks from $T_1$ and $q$ disks from $T_2$ to $T_3$, we must find $T(n,n)$. If anyone has any idea, please share.

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments. - Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it to Victor (verifier). Victor can easily see that the final state of the solution is right (in linear time) but he'll have no option but to go through each of Peggy's moves to make sure she didn't make an illegal move. Since Peggy has to make a minimum of 2^|disks| - 1 moves (provable), Victor too has to follow suit. Thus Victor has no polynomial time verification (the definition of NP), and hence can't be in NP. - Is it in PSPACE ? Seems so, but I can't think of how to extend the above reasoning. - Is it PSPACE-complete? Seems not, but I have only a vague idea. Automated Planning , of which ToH is a specific instance, is PSPACE-complete. I think that Planning has far more hard instances than ToH. Updated : Input = $n$, the number of disks; Output = disk configuration at each step. After updating this, I realized that this input/output format doesn't fit a decision problem. I'm not sure about the right formalization to capture the notions of NP,PSPACE, etc. for this kind of problem. Update #2 : After Kaveh's and Jeff's comments, I'm forced to make the problem more precise: Let the input be the pair of ints $(n,i)$ where $n$ is the number of disks. If the sequence of moves taken by the disks is written down in the format (disk-number,from-peg,to-peg)(disk-number, from-peg, to-peg)... from the first move to the last, and encoded in binary, output the $i$th bit. Let me know if I need to be more specific about the encoding. I suppose Kaveh's comment applies in this case?