Skip to content

Instantly share code, notes, and snippets.

@WitherOrNot
Last active August 30, 2020 19:46
Show Gist options
  • Save WitherOrNot/04644e9ac72e5147f0b95c825fa0c596 to your computer and use it in GitHub Desktop.
Save WitherOrNot/04644e9ac72e5147f0b95c825fa0c596 to your computer and use it in GitHub Desktop.
Towers of Hanoi solver without recursion
import sys
import itertools
no_of_disks = int(raw_input("No. of disks: ")) if len(sys.argv) < 2 else int(sys.argv[1])
def disk_to_move(move_number):
diff = move_number ^ (move_number + 1)
return bin(diff)[2:].count("1") - 1
def generate_move(disk_to_move, disk_states):
destination_peg = 0
leftwards_peg = (disk_states[disk_to_move]+2)%3
rightwards_peg = (disk_states[disk_to_move]+1)%3
smaller_disks = disk_states[:disk_to_move]
origin_peg = disk_states[disk_to_move]
if len(disk_states) % 2 == 0:
if rightwards_peg in smaller_disks:
destination_peg = leftwards_peg
else:
destination_peg = rightwards_peg
else:
if leftwards_peg in smaller_disks:
destination_peg = rightwards_peg
else:
destination_peg = leftwards_peg
return (disk_to_move, origin_peg, destination_peg)
disk_states = [0]*no_of_disks
print("Peg A All")
for move_number in iter(itertools.count().next, 2**no_of_disks - 1):
disk, from_peg, to_peg = generate_move(disk_to_move(move_number), disk_states)
disk_states[disk] = to_peg
peg_names = ["A", "B", "C"]
print("Move "+str(move_number+1)+" - "+"Disk "+str(disk+1)+": Peg "+peg_names[from_peg]+" -> Peg "+peg_names[to_peg])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment