# Gena playing Hanoi challenge

**Problem statement**

The Tower of Hanoi is a famous game consisting of 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:

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

Gena has a modified version of the Tower of Hanoi. His Hanoi has rods and 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 to . All discs are initially located on rod .

**Input Format**

The first line contains a single integer, , denoting the number of discs.

The second line contains space-separated integers, where the integer is the index of the rod where the disk with diameter is located.

**Constraints**

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

1 2 |
3 1 4 1 |

**Sample Output**

1 |
3 |

**Explanation**

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 since we can have a maximum of possible tower-disc allocations/states. Each state has an integer `key`

. For example, given a state , a `key`

is an integer representing that allocation. Bits and of the `key`

represent the tower (Tower = , Tower = , Tower = , Tower = ). For the `key`

is .

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
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<Integer[]> of valid directly subsequent states. */ private static Set<Integer[]> validMovesFromState(Integer[] state) { Set<Integer[]> 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; ans.add(newState); } } } 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) { Queue<Integer[]> queue = new LinkedList<Integer[]>(); int[] visited = new int[(int) Math.pow(4, n)]; int key = key(n, initialState); initialState[0] = 0; visited[key] = 0; queue.add(initialState); int min = Integer.MAX_VALUE; while (!queue.isEmpty()) { Integer[] current = queue.poll(); if (isGoal(current)) { min = Math.min(min, current[0]); } else { Set<Integer[]> 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; queue.add(state); } } } } 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); } } |