In a slightly modified TOH we have 4 pegs. So in turn we have total of 4^N disk positions. Now in one of the solutions which I was going through, a given state is represented using below code -
for(int disc = 0; disc < N; disc++){
state += tower[disc]<<(disc*2);
}
tower[disc] --> tower where disc is currently located, which can be (0,1,2,3)
if I use N=3 in above code, it gives me 63, which is 4^N -1. So the formula works, i.e 0-63 all 64 positions can be represented. but I am not able to understand the mathematical correlation.
Can you please explain how above formula can represent all possible disk positions and how it will change if we further change number of pegs or N to lets say 5.
Since you only have 4 pegs, the position of any disk can be encoded in just 2 bits (00, 01, 10, 11 => 0, 1, 2, 3). Thus the multiplication by 2 gives each disk 2 bits of independent memory space within the integer state, with the first disk starting at bit 0, second at bit 2, and so on... ith disk at (i - 1) * 2. The left shift << moves the data for each disk to its correct bit position.
However this code can be "unsafe" - if there were a mistake in the game logic somewhere else which caused a value of tower to be greater than 3, when shifted it will overflow its designated 2 bits of space. To prevent this, do a bitwise AND to clamp the data to [0, 3]:
state += (tower[disc] & 3) << (i * 2);
Note that you can also use bitwise OR instead of addition - state |= ....
From the example N = 3 provided it looks like all plates are starting from peg 4 (i.e. tower[3]). If you change to N = 5 it will once again give you 4^N - 1 = 1023, as all bits below N * 2 will be set to 1.