I need some help determining a tower of hanoi algorithm configuration after m moves

Question

I’m having an issue with this question and need help - I’ve been breaking my head over this tower of hanoi algorithm question whereby there are specific rules we need to follow. Would love some help to assess the logic of my code, and if anyone has any tips/hints it would be helpful :)

The answer needs to have

The correct output
And needs to use recursion in the code

Question Determine the number of disks on pegs A, B and C after m moves (the sum of the 3 numbers should be n since there are n disks). There are n disks and m moves. n is an integer between 1 and 64, and m is an integer between 0 and 2^n - 1.

Rules:

All disks are initially placed on peg A such that their sizes increase from top to bottom
Only 1 disk can move at a time, either:
1. To an empty peg
2. To a peg with a larger disk
Move the smallest disk (disk 1) in a circular manner ACBACB… on odd moves (i.e., 1, 3, 5 etc.)
Make the other moves not involving disk 1 on even moves (i.e., 2, 4, 6 etc.)

My code

`def tower_hanoi(n, m):  
  def inner_ToH(n, m, A, B, C):  
   if m == 0:  
    return A, B, C  
   if m <= (2**(n - 1) - 1):  
    return inner_ToH(n - 1, m, A, C, B)  
   A -= n  
   B += (n - 1)  
   C += 1  
   m -= 2**(n - 1)  
   return inner_ToH(n - 1, m, B, A, C)  
  return inner_ToH(n, m, n, 0, 0)  `

My output:
1 1 1
1 1 2 (wrong)
62 0 2 (wrong)
6 15 9 (wrong)

Desired output:
1 1 1
2 1 1
62 2 0
15 6 9

Sample Input (no. of disks, no. of moves):
3 5
4 11
64 12
30 100000009

btilly · Answer

First a stylistic note.

While Python can understand a 1 space indent, no human can see it correctly in a large body of code. Research finds that comprehension is optimized between a 2-4 space indent, and older people with poorer eyes benefit from 4 spaces. This is why standard Python style has a 4 space indent.

Next, before writing code, think about how it is going to work. Maybe do a few by hand. If you do that, you'll realize the following.

You are told that disc 1 should go A, C, B, A, C, B on moves 1, 3, 5, 7, ...

Disc 2 is forced to go A, B, C, A, B, C on moves 2, 6, 10, 14, ... for disc 1 to do that.

Now disc 3 is forced to go A, C, B, A, C, B on moves 4, 12, 20, 28, ...

And so on.

And now your logic looks like this:

Figure out how many moves disc 1 took.
Figure out where it is.
Reverse B and C, then figure out where everything else went in the rest of the moves. (This is your recursive step.)

(I would personally solve this problem in a very different way, by working from the largest disc to the smallest, but either way works.)

I need some help determining a tower of hanoi algorithm configuration after m moves

1 Answers