Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Gena playing Hanoi challenge

Sharing is caring!

Problem statement
The Tower of Hanoi is a famous game consisting of 3 rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

  1. Only one disc can be moved at a time.
  2. Each move consists of taking the topmost disc from a stack and moving it to the top of another stack.
  3. No disc may be placed on top of a smaller disc.

Gena has a modified version of the Tower of Hanoi. His Hanoi has 4 rods and N discs ordered by ascending size. He made a few moves (following the rules above), but stopped and lost his place. He wants to restore the tower to its original state by making valid moves. Given the state of Gena’s Hanoi, help him calculate the minimum number of moves needed to restore the tower to its original state.

Note: Gena’s rods are numbered from 1 to 4. All discs are initially located on rod 1.

Input Format
The first line contains a single integer, N, denoting the number of discs.
The second line contains N space-separated integers, where the i^{th} integer is the index of the rod where the disk with diameter i is located.

Constraints
1 \le N \le 10

Output Format
Print the minimum number of moves Gena must make to restore the tower to its initial, ordered state on the first rod.

Sample Input

Sample Output

Explanation
3 moves are enough to build the tower. Here is one possible solution:

Solution
We will use BFS to solve this challenge. We will use a helper array minForTower with minForTower[i] holding the size of the smallest disc located at tower i. The validMovesFromState() method will compute and return a Set<Integer[]> of all valid directly subsequent moves that can be made from a given tower-disc allocation. We will store visited states in an array int[] visited = new int[(int) Math.pow(4, n)] using a key. The array length is 4^N since we can have a maximum of 4^N possible tower-disc allocations/states. Each state has an integer key. For example, given a state \left[1, 4, 1\right], a key is an integer representing that allocation. Bits 2i and 2i+1 of the key represent the tower (Tower 0 = 00_b, Tower 1 = 01_b, Tower 2 = 10_b, Tower 3 = 11_b). For \left[1, 4, 1\right] the key is 12 = 001100_b.

We then do a BFS putting the states in a queue along with the depth of the given state. The depth or number of steps it took us to get to that state is stored at index 0 of the state array. Each time we reach our goal state we check we update our minimum if necessary.

The full code is listed below.

Full code