# 10.2. Tower of Hanoi

The followings demonstrate the Tower of Hanoi problem:

{% embed url="<https://www2.slideshare.net/jchoi7s/dynamic-programming-tower-of-hanoi>" %}

## Abstraction

Let us create the abstract class [`Hanoi`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/dynamic/hanoi/Hanoi.java):

```java
public abstract class Hanoi {
    /**
     * @param n            the total number of rings.
     * @param source       the source tower.
     * @param intermediate the intermediate tower.
     * @param destination  the destination tower.
     * @return a list of steps to move all rings in the source tower to the destination tower.
     */
    public abstract List<String> solve(int n, char source, char intermediate, char destination);

    protected String getKey(int n, char source, char destination) {
        return n + ":" + source + "->" + destination;
    }
}
```

* `L9`: returns a list of movements to solve the given problem.
  * `n`: the total number of rings.
  * `source`: the ID of the source tower.
  * `intermediate`: the ID of the intermediate tower.
  * `destination`: the ID of the destination tower.
* `L11`: returns the string representation of a movement.

## Recursion

Let us create the [`HanoiRecursive`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/dynamic/hanoi/HanoiRecursive.java) class inheriting `Hanoi`:

```java
public class HanoiRecursive extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination);
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination) {
        if (n == 0) return;
        solve(list, n - 1, source, destination, intermediate);
        list.add(getKey(n, source, destination));
        solve(list, n - 1, intermediate, source, destination);
    }
}
```

## Dynamic Programming

Let us create the [`HanoiDynamic`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/dynamic/hanoi/HanoiDynamic.java) class inheriting `Hanoi`:

```java
public class HanoiDynamic extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination, new HashMap<>());
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination, Map<String, int[]> map) {
        if (n == 0) return;
        int fromIndex = list.size();
        int[] sub = map.get(getKey(n - 1, source, intermediate));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, source, destination, intermediate, map);

        String key = getKey(n, source, destination);
        list.add(key);
        sub = map.get(getKey(n - 1, intermediate, destination));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, intermediate, source, destination, map);

        if (!map.containsKey(key))
            map.put(key, new int[]{fromIndex, list.size()});
    }

    private void addAll(List<String> list, int fromIndex, int toIndex) {
        for (int i = fromIndex; i < toIndex; i++)
            list.add(list.get(i));
    }
}
```

## Benchmark

The followings show performance comparison:

{% embed url="<https://www2.slideshare.net/jchoi7s/dynamic-programming-tower-of-hanoi-benchmark>" %}