In the famous Towers of Hanoi puzzle, you have three pegs, labeled A, B, and C, and n discs, of sizes 1 through n, inclusive.
The discs are initially stacked on peg A in order of size, with the smallest disc on top. The goal is move the entire stack from peg A to peg C, under the constraints that you can only move one disc at a time and you can never move a larger disc onto a smaller disc. In each move, you remove the top disc from one of the three pegs and place it on top of the discs on another peg. In some cases, you
move a disc to an empty peg, in which case the disc goes on the bottom of the peg.
There is a unique sequence of moves that solves the Towers of Hanoi puzzle in the minimum number of moves.
There are a total of 2n configurations of discs that are encountered during the course of this solution, counting the
Call each of these configurations valid and all other configurations invalid.
Your little sister dropped your Towers of Hanoi puzzle and put the discs back on random pegs. She remembered to always put smaller discs on top of larger discs, but did not necessarily make a valid configuration.
You would be embarrassed if your friends saw your puzzle in an invalid configuration, so you want to
move the discs back into a valid configuration. Naturally, you want to do so in the minimum number of moves. As usual, you can only move one disc at a time and you can never place a larger disc on top of a smaller disc.
You will be given the number of discs, n, and three int's, pegA, pegB, and pegC, representing the order of the discs on each of the pegs, with the top disc on each peg at the front of the int and the bottom disc at the back. Return the minimum number of moves required to reach a valid configuration.