Created
September 12, 2016 00:09
-
-
Save not-napoleon/812279c1491fcaeb36643e878ee03c5e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Iterative towers of Hanoi solution. | |
This is based on the idea that essentially, the towers problem is a binary | |
counter, with the disk that gets moved being equal to the bit that would be | |
set on any iteration of the counter. | |
The solution exploits a few other mathematical properties of the problem: | |
To solve an N disk towers of Hanoi requires (2^n)-1 moves (easy to prove | |
by induction) | |
The disks move in circular (i.e. modular) patterns, with even disks moving | |
clockwise and odd disks moving anti-clockwise (or the other way around, | |
n depending on how you want to think of it). Another way to think of this | |
is that if we moved disk N-1 one space, we need to move disk N two spaces. | |
This is implemented in the modulo 3 calculations below. | |
""" | |
POSTS = ['A', 'B', 'C'] | |
def move(n): | |
"""Compute the nth move | |
""" | |
disk = ((~(n-1)) & n).bit_length() | |
times_moved = n // 2**disk | |
from_stack = (((disk % 2) + 1) * times_moved) % 3 | |
to_stack = (((disk % 2) + 1) * (times_moved + 1)) % 3 | |
print "Move disk %s from %s to %s" % (disk, POSTS[from_stack], | |
POSTS[to_stack]) | |
def hanoi(n): | |
for i in range(2**n - 1): | |
move(i+1) | |
if __name__ == '__main__': | |
hanoi(5) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment