Making Tower of Hanoi more efficient

Question

I need help with making this code more efficient because right now if I input a really big number for n, like 100, it takes beyond days to fully compute. Also, I must use recursion since that is part of my task. However, this may be the fastest way and there may be no more efficient solution, but I am not sure of that and was hoping someone could clarify.

code:

def hanoi(n, start, end):
  if n==1:
    print(str(start)+ " -> " + str(end))
  else:
    other = 6 - (start+end)
    hanoi(n-1,start, other)
    print(str(start)+ " -> " + str(end))
    hanoi(n-1,other,end)
hanoi(3,1,3)

Here is a video for context about how the code works since it is quite abstract: https://www.youtube.com/watch?v=rf6uf3jNjbo

I considered monetization and tail recursion but I am confused on how approach implanting them here.

It is exponential. It takes O(2^n) to solve this problem so it grows very quickly. — MYousefi, Oct 30 '22 at 02:47
The optimization you can do is to memoize. Essentially you keep a record of the calls and solutions you have calculated and recognize states which are identical and return the answer from memory. — MYousefi, Oct 30 '22 at 02:51
@MYousefi I have tried memoization but did it not work. I tried keeping a record of each distinct (n, start, end). — EKmaster, Oct 30 '22 at 04:33
@MYousefi Memoization won't help here. The function is not pure. — Aadit M Shah, Oct 30 '22 at 04:59
A pure function is one which 1) does not have any side effects 2) always returns the same outputs for the same inputs. The `hanoi` function is not pure because it has side effects - it's printing to the console. Only pure functions can be memoized. For more information, see the following answer. https://stackoverflow.com/a/58749249/783743 — Aadit M Shah, Oct 30 '22 at 05:24
It seems impossible to improve the performance of this algorithm. It's been mathematically proven that the minimal number of moves required to solve a Tower of Hanoi puzzle is `2^n - 1` where `n` is the number of disks. Hence, solving a Tower of Hanoi puzzle with 100 disks will take more than a quadrillion quadrillion moves. That is more than 1 followed by 30 zeros. If you have a 4GHz processor it will still take you 8 trillion years to compute the answer. Memoization also doesn't help. First, because the cache hit rate is less than 1%. Second, you'll run out of memory before you can solve it. — Aadit M Shah, Oct 30 '22 at 05:44
Depends. How are you appending to a list? Can you show me the code? — Aadit M Shah, Oct 30 '22 at 12:09
@AaditMShah It is true but from a state space graph standpoint, you can see that many states are equivalent via a transformation. Such conditions would allow for some optimization via a lookup table. — MYousefi, Oct 30 '22 at 18:40
@AaditMShah `code myList = [] def hanoi(n, start, end): if n==1: myList.append(str(start)+ " -> " + str(end)) else: other = 6 - (start+end) hanoi(n-1,start, other) myList.append(str(start)+ " -> " + str(end)) hanoi(n-1,other,end) hanoi(3,1,3) print(myList) ` — EKmaster, Oct 30 '22 at 20:17
@MYousefi I have tried to set up a lookup table but it isn't working. Could you tell me when to add values to it? — EKmaster, Oct 30 '22 at 20:22
@MYousefi Actually, most states are not equivalent. I tried memoizing a pure version of the OPs solution, and the cache hit rate was almost 0%. Furthermore, the memory requirements make memoization unfeasible. You'll sooner run out of memory before you can solve the problem for 100 disks. Hence, memoization doesn't work. And even if it did work, you'd want to iterate over and print out the solution. However, the solution for 100 disks has over a quadrillion quadrillion moves. Solving this problem for 100 disks is simply intractable. — Aadit M Shah, Oct 31 '22 at 10:53
@AaditMShah why does adding: from functools import lru_cache @lru_cache(maxsize = 1000) to the top make 100 solvable? — EKmaster, Oct 31 '22 at 18:17
It doesn't make it solvable. At least not in a reasonable amount of time. Not sure what you wrote but I'm certain that it's incorrect. — Aadit M Shah, Nov 01 '22 at 03:48

Making Tower of Hanoi more efficient

0 Answers0