That’s One Hanoi-ed Teacher
This problem gives us an intermediate configuration of a game of "towers of hanoi" and asks us whether it is valid, and if so, how many moves are remaining.
Before trying to solve this problem, it behooves one to solve a few smaller games of towers of hanoi to see how the optimal solutions work, and how many moves it takes. One finds quickly that it is recursive in nature, and the number of moves is 2^n - 1. n is too large, however, to simulate all moves.
Given that n IS too large, we need some way to directly calculate from the state of the disks what our position is. It turns out this is quite simple. This is a classic select-an-element problem.
We know from our inspection that the game can be divided into 3 halves (jokes!):
- the moves before the largest disk is moved (2^(n-1)-1 moves)
- the move of the largest disk (1 move)
- the moves after the largest disk is moved (2^(n-1)-1 moves)
If the disk has NOT moved, the remaining moves are the sum of steps 2 and 3 above, plus a bit of extra. If the disk HAS moved, the remaining moves are just a bit of extra. We can calculate that "extra" recursively by removing the largest disk and repeating the steps.
We have one further issue, though. When we are in the first section above, the "work" required is to move all the smaller disks from column 1->2. In the third section, it is from 2->3. This means when we recurse, we have to pass in which our starting and target pillars are to know whether the largest disk for that next recursion has moved or not. Considering the example images in the problem statement, if we recurse "after step 5," we see that the second largest disk has NOT moved yet despite being on the second pillar already. This makes sense because starting at step 4 (the move of the largest disk), the "starting pillar" is the middle one, and the "target pillar" is the right hand one, so we are in the FIRST of the steps above.