## [f]izzbuzzer

### 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

3
1 4 1


Sample Output

3


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

public class GenaPlayingHanoi {
private static final int TOWERS = 4;
private static final int MAX = 100;

private static boolean isGoal(Integer[] state) {
for (int i = 1; i < state.length; i++) {
if (!Integer.valueOf(0).equals(state[i])) {
return false;
}
}

return true;
}

/**
* Given a tower-disc allocation [0, 3, 0] returns a Set of valid directly subsequent states.
*/
private static Set validMovesFromState(Integer[] state) {
Set ans = new HashSet<>();

Integer[] minForTower = minForTower(state.length - 1, state);

for (int t = 0; t < TOWERS; t++) {
int discToMove = minForTower[t];

for (int t2 = 0; t2 < TOWERS; t2++) {
if (t2 != t && minForTower[t2] > discToMove) {
// move i from tower t to tower t2
Integer[] newState = state.clone();
newState[discToMove] = t2;
}
}
}

return ans;
}

/**
* Returns array int[] a = int[TOWERS+1] with t[i] holding the size of the
* top (smallest) disc located at tower i
*
*/
private static Integer[] minForTower(int n, Integer[] t) {
Integer[] ans = { MAX, MAX, MAX, MAX, MAX };

for (int i = 1; i <= n; i++) {
ans[t[i]] = Math.min(ans[t[i]], i);
}

return ans;
}

/**
* Given a state e.g. [1, 4, 1] returns an integer representing that state. Bit 2i and 2i+1 represent the tower (tower 0 = 00, tower 1 = 01, tower 2 = 10, tower 3 = 11).
*
* For [1, 4, 1] the method returns 12 = 00-11-00
*
*/
private static int key(int n, Integer[] t) {
int ans = 0;

for (int disc = 1; disc <= n; disc++) {
int tower = t[disc];
int towerBits = tower << 2 * (disc - 1);
ans |= towerBits;
}

return ans;
}

/**
* BFS
*/
private static void solve(int n, Integer[] initialState) {
int[] visited = new int[(int) Math.pow(4, n)];

int key = key(n, initialState);
initialState[0] = 0;
visited[key] = 0;

int min = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
Integer[] current = queue.poll();

if (isGoal(current)) {
min = Math.min(min, current[0]);
} else {
Set next = validMovesFromState(current);
for (Integer[] state : next) {
key = key(n, state);
if (visited[key] == 0 || visited[key] > current[0] + 1) {
// state[0] is used to hold the number of steps it took us to get there
state[0] = current[0] + 1;
visited[key] = current[0] + 1;
}
}
}
}

System.out.println(min);
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Integer[] t = new Integer[n + 1];
for (int i = 1; i <= n; i++) {
t[i] = in.nextInt() - 1;
}

solve(n, t);
}
}