## We will be simulating the ideal solution to Hanoi's tower
problem.
## The discs will be numers from 0 to n-1, with the larger number
being the smaller disc.
## each rod with discs will be encoded by a list, from bottom to
top. For example, a rod with discs 0, 3, 5 will be encoded as
[0,3,5]
## current configuration of rods will be encoded as a list of 3
lists. For example, starting state with 3 discs will be
[[0,1,2],[],[]]
## You need to fill out the missing parts from the function 'move'
and the function 'TowerHanoi_recur'
## Once you are finished, run TowerHanoi_start(5).
def initialize_rods(n): ##this function initializes the rods and
the discs. Rod 0 will have all discs 0~n-1.
global global_counter
global_counter = 0
L = []
for i in range(n):
L = L + [i]
return [L,[],[]]
def pop(L): ##Given a list L, gets the last entry.
i = len(L)
return L[i-1]
def after_pop(L): ##Given a list L, deletes the last
entry.
i = len(L)
return L[0:i-1]
def insert(i,L): ##Given a list L, adds i to the end. We make
sure disc i is the smaller than the current top-disc of the
rod.
j = len(L)
if j >0 and i < L[j-1]:
print('Illegal move!')
return L + [i]
def move(C,rod_from,rod_to): ##Given configuration C, moves a
top disc from rod_from to rod_to.
global global_counter
disc = ####FILL THIS PART : disc stores the disc we are
moving.
C_after = C
global_counter = global_counter+1
print('(Moving disc',disc,'Rod',rod_from,'-> Rod',rod_to,'Step
number :',global_counter,')')
C_after[rod_from] = ####FILL THIS PART#### : how the rod rod_from
would look like after the move
C_after[rod_to] = ####FILL THIS PART#### : how the rod rod_to would
look like after the move
return C_after
def report_status(L): ##prints out the current
configuration.
print('Rod 0:',L[0],'Rod 1:',L[1],'Rod 2:',L[2])
def TowerHanoi_recur(C,n,rod_from,rod_to,rod_other): ##This is the
main recurrence algorithm we are running. C is the current
configuration of rods and discs, we are trying to move n top
discs.
if n == 1:
report_status(C)
return move(C,rod_from,rod_to)
T = ####FILL THIS PART. The first half of our algorithm. Move top
n-1 discs from rod_from to rod_other.####
report_status(T)
Q = ####FILL THIS PART. Move the largest disc from rod_from to
rod_to.####
return ####FILL This PART. We return the result of the second half
of our algorithm: move the n-1 discs from rod_other to
rod_to.####
def TowerHanoi_start(n): ##This is the function we will be running.
n is the number of discs.
Current_Configuration = initialize_rods(n)
report_status(TowerHanoi_recur(Current_Configuration,n,0,2,1))
Get Answers For Free
Most questions answered within 1 hours.