Question

## We will be simulating the ideal solution to Hanoi's tower problem. ## The discs will...

## 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))