Advertisement
Guest User

Untitled

a guest
Oct 19th, 2017
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.72 KB | None | 0 0
  1. """
  2. This code runs in python 3.6.2
  3.  
  4. The following game is the N-disk Tower of Hanoi (NTH).
  5.  
  6. There are three pegs labelled, 1, 2, 3, and N disks (smaller upon larger) on peg 1. The goal is to transfer the
  7. disks in the same order to peg 3 using the following rules:
  8.  
  9. 1) A top disc on a peg can be moved to an empty peg or on top of a larger disk on another peg.
  10. 2) Only one disk can be moved at a time.
  11.  
  12. This program prints the peg/disc configurations at each step in the optimal solution to the NTH (2^N-1 moves).
  13. ________________________________________________________________________________________________________________________
  14. """
  15.  
  16.  
  17. # This segment of code stores the origin peg and destination peg for each move in the list peg_to_peg.
  18. # We sketch our inductive method below.
  19.  
  20. # 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
  21. # transfer a tower of n disks from peg p to peg q.
  22.  
  23. # 1) Base case: H(1,1,3) = [[1,3]]
  24.  
  25. # 2) Given H(n,1,3):
  26.  
  27. # 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
  28. # the permutation 1->1, 2->3, 3->2.
  29.  
  30. # 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
  31. # permutation 1->2, 2->1, 3->3.
  32.  
  33. # 3) H(n+1,1,3) is the concatenation of H(n,1,2), [1,3], H(n,2,3).
  34.  
  35.  
  36. N = int(input("What is the number of disks? (at least one): "))
  37. peg_to_peg = [[1,3]]
  38.  
  39. def perm1(x):
  40.  
  41. if x == 1:
  42. return 1
  43. if x == 2:
  44. return 3
  45. if x == 3:
  46. return 2
  47.  
  48. def perm2(x):
  49.  
  50. if x == 1:
  51. return 2
  52. if x == 2:
  53. return 1
  54. if x == 3:
  55. return 3
  56.  
  57. for n in range(2,N+1):
  58.  
  59. first_mod = []
  60. second_mod = []
  61.  
  62. for entry in peg_to_peg:
  63.  
  64. first_mod.append([perm1(entry[0]), perm1(entry[1])])
  65. second_mod.append([perm2(entry[0]), perm2(entry[1])])
  66.  
  67. peg_to_peg = first_mod +[[1,3]]+ second_mod
  68.  
  69.  
  70. # This segment of code uses peg_to_peg to create game_log, a list of the peg/disk configurations at each step of the
  71. # solution.
  72.  
  73.  
  74. peg1_current = []
  75.  
  76. for n in range(1,N+1):
  77. peg1_current.append(N+1-n)
  78.  
  79. peg2_current = []
  80. peg3_current = []
  81.  
  82. game_log = [[peg1_current, [],[]]]
  83.  
  84. for k in range(1,2**N):
  85.  
  86. # The following cases could be consolidated into a for-loop over a permutation, but that would require explicitly
  87. # indexing peg1_current, peg2_current, and peg3_current, which I'd rather avoid for the moment.
  88.  
  89. if peg_to_peg[k-1][0] == 1 and peg_to_peg[k-1][1] == 3:
  90. peg3_current.append(peg1_current[-1])
  91. peg1_current.pop()
  92.  
  93. if peg_to_peg[k-1][0] == 3 and peg_to_peg[k-1][1] == 1:
  94. peg1_current.append(peg3_current[-1])
  95. peg3_current.pop()
  96.  
  97. if peg_to_peg[k-1][0] == 1 and peg_to_peg[k-1][1] == 2:
  98. peg2_current.append(peg1_current[-1])
  99. peg1_current.pop()
  100.  
  101. if peg_to_peg[k-1][0] == 2 and peg_to_peg[k-1][1] == 1:
  102. peg1_current.append(peg2_current[-1])
  103. peg2_current.pop()
  104.  
  105. if peg_to_peg[k-1][0] == 3 and peg_to_peg[k-1][1] == 2:
  106. peg2_current.append(peg3_current[-1])
  107. peg3_current.pop()
  108.  
  109. if peg_to_peg[k-1][0] == 2 and peg_to_peg[k-1][1] == 3:
  110. peg3_current.append(peg2_current[-1])
  111. peg2_current.pop()
  112.  
  113. game_log.append([tuple(peg1_current), tuple(peg2_current), tuple(peg3_current)])
  114.  
  115. game_log.remove(game_log[0])
  116.  
  117.  
  118. # This segment of code prints/formats each entry in game_log after a prompt. Each configuration is stored as a list of
  119. # tuples, so the code mainly gets rid of unsightly commas and empty lists to make a nice output.
  120.  
  121.  
  122. for k in range(len(game_log)):
  123.  
  124. if k == 0:
  125. print("Press enter to see the first move.")
  126. input()
  127.  
  128. if k > 0:
  129. print("Press enter to see the next move.")
  130. input()
  131.  
  132. print("Move %d:" %(k+1))
  133. print()
  134.  
  135. for j in range(3):
  136.  
  137. if len(game_log[k][j]) == 0:
  138. print("peg %d: " %(j+1))
  139. if len(game_log[k][j]) == 1:
  140. tuple_to_string = str(game_log[k][j])
  141. tuple_to_string = tuple_to_string.replace(",","")
  142. print("peg %d: %s" %(j+1, tuple_to_string))
  143. if len(game_log[k][j]) >=2:
  144. print("peg %d: %s" %(j+1, str(game_log[k][j])))
  145. print()
  146.  
  147. if k == len(game_log)-1:
  148. print("Done!")
  149. ________________________________________________________________________________________________
  150. ________________________________________________________________________________________________
  151.  
  152. Sample output for N=5:
  153.  
  154. ________________________________________________________________________________________________
  155. ________________________________________________________________________________________________
  156.  
  157. What is the number of disks? (at least one): 5
  158. Press enter to see the first move.
  159.  
  160. Move 1:
  161.  
  162. peg 1: (5, 4, 3, 2)
  163. peg 2:
  164. peg 3: (1)
  165.  
  166. Press enter to see the next move.
  167.  
  168. Move 2:
  169.  
  170. peg 1: (5, 4, 3)
  171. peg 2: (2)
  172. peg 3: (1)
  173.  
  174. Press enter to see the next move.
  175.  
  176. Move 3:
  177.  
  178. peg 1: (5, 4, 3)
  179. peg 2: (2, 1)
  180. peg 3:
  181.  
  182. Press enter to see the next move.
  183.  
  184. Move 4:
  185.  
  186. peg 1: (5, 4)
  187. peg 2: (2, 1)
  188. peg 3: (3)
  189.  
  190. Press enter to see the next move.
  191.  
  192. Move 5:
  193.  
  194. peg 1: (5, 4, 1)
  195. peg 2: (2)
  196. peg 3: (3)
  197.  
  198. Press enter to see the next move.
  199.  
  200. Move 6:
  201.  
  202. peg 1: (5, 4, 1)
  203. peg 2:
  204. peg 3: (3, 2)
  205.  
  206. Press enter to see the next move.
  207.  
  208. Move 7:
  209.  
  210. peg 1: (5, 4)
  211. peg 2:
  212. peg 3: (3, 2, 1)
  213.  
  214. Press enter to see the next move.
  215.  
  216. Move 8:
  217.  
  218. peg 1: (5)
  219. peg 2: (4)
  220. peg 3: (3, 2, 1)
  221.  
  222. Press enter to see the next move.
  223.  
  224. Move 9:
  225.  
  226. peg 1: (5)
  227. peg 2: (4, 1)
  228. peg 3: (3, 2)
  229.  
  230. Press enter to see the next move.
  231.  
  232. Move 10:
  233.  
  234. peg 1: (5, 2)
  235. peg 2: (4, 1)
  236. peg 3: (3)
  237.  
  238. Press enter to see the next move.
  239.  
  240. Move 11:
  241.  
  242. peg 1: (5, 2, 1)
  243. peg 2: (4)
  244. peg 3: (3)
  245.  
  246. Press enter to see the next move.
  247.  
  248. Move 12:
  249.  
  250. peg 1: (5, 2, 1)
  251. peg 2: (4, 3)
  252. peg 3:
  253.  
  254. Press enter to see the next move.
  255.  
  256. Move 13:
  257.  
  258. peg 1: (5, 2)
  259. peg 2: (4, 3)
  260. peg 3: (1)
  261.  
  262. Press enter to see the next move.
  263.  
  264. Move 14:
  265.  
  266. peg 1: (5)
  267. peg 2: (4, 3, 2)
  268. peg 3: (1)
  269.  
  270. Press enter to see the next move.
  271.  
  272. Move 15:
  273.  
  274. peg 1: (5)
  275. peg 2: (4, 3, 2, 1)
  276. peg 3:
  277.  
  278. Press enter to see the next move.
  279.  
  280. Move 16:
  281.  
  282. peg 1:
  283. peg 2: (4, 3, 2, 1)
  284. peg 3: (5)
  285.  
  286. Press enter to see the next move.
  287.  
  288. Move 17:
  289.  
  290. peg 1: (1)
  291. peg 2: (4, 3, 2)
  292. peg 3: (5)
  293.  
  294. Press enter to see the next move.
  295.  
  296. Move 18:
  297.  
  298. peg 1: (1)
  299. peg 2: (4, 3)
  300. peg 3: (5, 2)
  301.  
  302. Press enter to see the next move.
  303.  
  304. Move 19:
  305.  
  306. peg 1:
  307. peg 2: (4, 3)
  308. peg 3: (5, 2, 1)
  309.  
  310. Press enter to see the next move.
  311.  
  312. Move 20:
  313.  
  314. peg 1: (3)
  315. peg 2: (4)
  316. peg 3: (5, 2, 1)
  317.  
  318. Press enter to see the next move.
  319.  
  320. Move 21:
  321.  
  322. peg 1: (3)
  323. peg 2: (4, 1)
  324. peg 3: (5, 2)
  325.  
  326. Press enter to see the next move.
  327.  
  328. Move 22:
  329.  
  330. peg 1: (3, 2)
  331. peg 2: (4, 1)
  332. peg 3: (5)
  333.  
  334. Press enter to see the next move.
  335.  
  336. Move 23:
  337.  
  338. peg 1: (3, 2, 1)
  339. peg 2: (4)
  340. peg 3: (5)
  341.  
  342. Press enter to see the next move.
  343.  
  344. Move 24:
  345.  
  346. peg 1: (3, 2, 1)
  347. peg 2:
  348. peg 3: (5, 4)
  349.  
  350. Press enter to see the next move.
  351.  
  352. Move 25:
  353.  
  354. peg 1: (3, 2)
  355. peg 2:
  356. peg 3: (5, 4, 1)
  357.  
  358. Press enter to see the next move.
  359.  
  360. Move 26:
  361.  
  362. peg 1: (3)
  363. peg 2: (2)
  364. peg 3: (5, 4, 1)
  365.  
  366. Press enter to see the next move.
  367.  
  368. Move 27:
  369.  
  370. peg 1: (3)
  371. peg 2: (2, 1)
  372. peg 3: (5, 4)
  373.  
  374. Press enter to see the next move.
  375.  
  376. Move 28:
  377.  
  378. peg 1:
  379. peg 2: (2, 1)
  380. peg 3: (5, 4, 3)
  381.  
  382. Press enter to see the next move.
  383.  
  384. Move 29:
  385.  
  386. peg 1: (1)
  387. peg 2: (2)
  388. peg 3: (5, 4, 3)
  389.  
  390. Press enter to see the next move.
  391.  
  392. Move 30:
  393.  
  394. peg 1: (1)
  395. peg 2:
  396. peg 3: (5, 4, 3, 2)
  397.  
  398. Press enter to see the next move.
  399.  
  400. Move 31:
  401.  
  402. peg 1:
  403. peg 2:
  404. peg 3: (5, 4, 3, 2, 1)
  405.  
  406. Done!
  407.  
  408. Process finished with exit code 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement