Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- This code runs in python 3.6.2
- The following game is the N-disk Tower of Hanoi (NTH).
- There are three pegs labelled, 1, 2, 3, and N disks (smaller upon larger) on peg 1. The goal is to transfer the
- disks in the same order to peg 3 using the following rules:
- 1) A top disc on a peg can be moved to an empty peg or on top of a larger disk on another peg.
- 2) Only one disk can be moved at a time.
- This program prints the peg/disc configurations at each step in the optimal solution to the NTH (2^N-1 moves).
- ________________________________________________________________________________________________________________________
- """
- # This segment of code stores the origin peg and destination peg for each move in the list peg_to_peg.
- # We sketch our inductive method below.
- # Let an ordered pair [a,b] denote a move from peg a to peg b, and H(n,p,q) be the minimal sequence of moves to
- # transfer a tower of n disks from peg p to peg q.
- # 1) Base case: H(1,1,3) = [[1,3]]
- # 2) Given H(n,1,3):
- # H(n,1,2) can be obtained from H(n,1,3) by replacing each pair [a,b] with [perm1(a), perm1(b)] where perm1 is
- # the permutation 1->1, 2->3, 3->2.
- # H(n,2,3) can be obtained from H(n,1,3) by replacing the pair [a,b] with [perm2(a), perm2(b)] where perm2 is the
- # permutation 1->2, 2->1, 3->3.
- # 3) H(n+1,1,3) is the concatenation of H(n,1,2), [1,3], H(n,2,3).
- N = int(input("What is the number of disks? (at least one): "))
- peg_to_peg = [[1,3]]
- def perm1(x):
- if x == 1:
- return 1
- if x == 2:
- return 3
- if x == 3:
- return 2
- def perm2(x):
- if x == 1:
- return 2
- if x == 2:
- return 1
- if x == 3:
- return 3
- for n in range(2,N+1):
- first_mod = []
- second_mod = []
- for entry in peg_to_peg:
- first_mod.append([perm1(entry[0]), perm1(entry[1])])
- second_mod.append([perm2(entry[0]), perm2(entry[1])])
- peg_to_peg = first_mod +[[1,3]]+ second_mod
- # This segment of code uses peg_to_peg to create game_log, a list of the peg/disk configurations at each step of the
- # solution.
- peg1_current = []
- for n in range(1,N+1):
- peg1_current.append(N+1-n)
- peg2_current = []
- peg3_current = []
- game_log = [[peg1_current, [],[]]]
- for k in range(1,2**N):
- # The following cases could be consolidated into a for-loop over a permutation, but that would require explicitly
- # indexing peg1_current, peg2_current, and peg3_current, which I'd rather avoid for the moment.
- if peg_to_peg[k-1][0] == 1 and peg_to_peg[k-1][1] == 3:
- peg3_current.append(peg1_current[-1])
- peg1_current.pop()
- if peg_to_peg[k-1][0] == 3 and peg_to_peg[k-1][1] == 1:
- peg1_current.append(peg3_current[-1])
- peg3_current.pop()
- if peg_to_peg[k-1][0] == 1 and peg_to_peg[k-1][1] == 2:
- peg2_current.append(peg1_current[-1])
- peg1_current.pop()
- if peg_to_peg[k-1][0] == 2 and peg_to_peg[k-1][1] == 1:
- peg1_current.append(peg2_current[-1])
- peg2_current.pop()
- if peg_to_peg[k-1][0] == 3 and peg_to_peg[k-1][1] == 2:
- peg2_current.append(peg3_current[-1])
- peg3_current.pop()
- if peg_to_peg[k-1][0] == 2 and peg_to_peg[k-1][1] == 3:
- peg3_current.append(peg2_current[-1])
- peg2_current.pop()
- game_log.append([tuple(peg1_current), tuple(peg2_current), tuple(peg3_current)])
- game_log.remove(game_log[0])
- # This segment of code prints/formats each entry in game_log after a prompt. Each configuration is stored as a list of
- # tuples, so the code mainly gets rid of unsightly commas and empty lists to make a nice output.
- for k in range(len(game_log)):
- if k == 0:
- print("Press enter to see the first move.")
- input()
- if k > 0:
- print("Press enter to see the next move.")
- input()
- print("Move %d:" %(k+1))
- print()
- for j in range(3):
- if len(game_log[k][j]) == 0:
- print("peg %d: " %(j+1))
- if len(game_log[k][j]) == 1:
- tuple_to_string = str(game_log[k][j])
- tuple_to_string = tuple_to_string.replace(",","")
- print("peg %d: %s" %(j+1, tuple_to_string))
- if len(game_log[k][j]) >=2:
- print("peg %d: %s" %(j+1, str(game_log[k][j])))
- print()
- if k == len(game_log)-1:
- print("Done!")
- ________________________________________________________________________________________________
- ________________________________________________________________________________________________
- Sample output for N=5:
- ________________________________________________________________________________________________
- ________________________________________________________________________________________________
- What is the number of disks? (at least one): 5
- Press enter to see the first move.
- Move 1:
- peg 1: (5, 4, 3, 2)
- peg 2:
- peg 3: (1)
- Press enter to see the next move.
- Move 2:
- peg 1: (5, 4, 3)
- peg 2: (2)
- peg 3: (1)
- Press enter to see the next move.
- Move 3:
- peg 1: (5, 4, 3)
- peg 2: (2, 1)
- peg 3:
- Press enter to see the next move.
- Move 4:
- peg 1: (5, 4)
- peg 2: (2, 1)
- peg 3: (3)
- Press enter to see the next move.
- Move 5:
- peg 1: (5, 4, 1)
- peg 2: (2)
- peg 3: (3)
- Press enter to see the next move.
- Move 6:
- peg 1: (5, 4, 1)
- peg 2:
- peg 3: (3, 2)
- Press enter to see the next move.
- Move 7:
- peg 1: (5, 4)
- peg 2:
- peg 3: (3, 2, 1)
- Press enter to see the next move.
- Move 8:
- peg 1: (5)
- peg 2: (4)
- peg 3: (3, 2, 1)
- Press enter to see the next move.
- Move 9:
- peg 1: (5)
- peg 2: (4, 1)
- peg 3: (3, 2)
- Press enter to see the next move.
- Move 10:
- peg 1: (5, 2)
- peg 2: (4, 1)
- peg 3: (3)
- Press enter to see the next move.
- Move 11:
- peg 1: (5, 2, 1)
- peg 2: (4)
- peg 3: (3)
- Press enter to see the next move.
- Move 12:
- peg 1: (5, 2, 1)
- peg 2: (4, 3)
- peg 3:
- Press enter to see the next move.
- Move 13:
- peg 1: (5, 2)
- peg 2: (4, 3)
- peg 3: (1)
- Press enter to see the next move.
- Move 14:
- peg 1: (5)
- peg 2: (4, 3, 2)
- peg 3: (1)
- Press enter to see the next move.
- Move 15:
- peg 1: (5)
- peg 2: (4, 3, 2, 1)
- peg 3:
- Press enter to see the next move.
- Move 16:
- peg 1:
- peg 2: (4, 3, 2, 1)
- peg 3: (5)
- Press enter to see the next move.
- Move 17:
- peg 1: (1)
- peg 2: (4, 3, 2)
- peg 3: (5)
- Press enter to see the next move.
- Move 18:
- peg 1: (1)
- peg 2: (4, 3)
- peg 3: (5, 2)
- Press enter to see the next move.
- Move 19:
- peg 1:
- peg 2: (4, 3)
- peg 3: (5, 2, 1)
- Press enter to see the next move.
- Move 20:
- peg 1: (3)
- peg 2: (4)
- peg 3: (5, 2, 1)
- Press enter to see the next move.
- Move 21:
- peg 1: (3)
- peg 2: (4, 1)
- peg 3: (5, 2)
- Press enter to see the next move.
- Move 22:
- peg 1: (3, 2)
- peg 2: (4, 1)
- peg 3: (5)
- Press enter to see the next move.
- Move 23:
- peg 1: (3, 2, 1)
- peg 2: (4)
- peg 3: (5)
- Press enter to see the next move.
- Move 24:
- peg 1: (3, 2, 1)
- peg 2:
- peg 3: (5, 4)
- Press enter to see the next move.
- Move 25:
- peg 1: (3, 2)
- peg 2:
- peg 3: (5, 4, 1)
- Press enter to see the next move.
- Move 26:
- peg 1: (3)
- peg 2: (2)
- peg 3: (5, 4, 1)
- Press enter to see the next move.
- Move 27:
- peg 1: (3)
- peg 2: (2, 1)
- peg 3: (5, 4)
- Press enter to see the next move.
- Move 28:
- peg 1:
- peg 2: (2, 1)
- peg 3: (5, 4, 3)
- Press enter to see the next move.
- Move 29:
- peg 1: (1)
- peg 2: (2)
- peg 3: (5, 4, 3)
- Press enter to see the next move.
- Move 30:
- peg 1: (1)
- peg 2:
- peg 3: (5, 4, 3, 2)
- Press enter to see the next move.
- Move 31:
- peg 1:
- peg 2:
- peg 3: (5, 4, 3, 2, 1)
- Done!
- Process finished with exit code 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement