Tower of Hanoi solver

Question

Requesting code review, best practices, optimizations for this solution to the Tower of Hanoi problem.

final class PlatePair {

    private final String source;
    private final String destination;

    public PlatePair (String source, String destination) {
        this.source = source;
        this.destination = destination;
    }

    public String getSource() {
        return source;
    }

    public String getDestination() {
        return destination;
    }
}

public final class ToweOfHanoi {

    private ToweOfHanoi () { }

    /**
     * Solves the problem of tower of hanoi 
     * 
     * @param n     The number of plates
     * @return      The Set of sequential steps to take to solve the hanoi problem.
     */
    public static Set<PlatePair> solve(int n) {
        if (n <= 0) throw new IllegalArgumentException("The number of plates " + n  + " should be greater than zero.");

        final Set<PlatePair> platePair = new LinkedHashSet<PlatePair>();
        moveTowers(n, "A", "B", "C", platePair);
        return platePair;
    }

    public static void moveTowers(int n, String from, String using, String to, Set<PlatePair> platePair) {
        assert platePair != null;

        if (n == 0) return;

        moveTowers(n - 1, from, to, using, platePair);
        platePair.add(new PlatePair(from, to));
        moveTowers(n - 1, using, from, to, platePair);
    }

    public static void main(String[] args) {
        for (PlatePair getHanoi :  solve(3)) {
            System.out.println(getHanoi.getSource() + " : " + getHanoi.getDestination());
        }
    }
}

Answer 1

While your solution appears to work, and I cannot see any bugs, there are a number of best-practices that you are not employing in your solution. It is alsmost as if your code works by coincidence, rather than by design. There are a number of things that look like desperate attempts to make it work... and, like duct-tape, they work, but they are not pretty.

General

You have not described your algorithm in any detail. You have two recursive calls in your recursive method, and you have no documentation as to why. Recursion, in general, is relatively complex to understand, and can be unintuitive. You should help the person reading your code to understand.... and you do nothing. I had to debug the code to watch it happen to understand why you do things the way you do. This is not fair.

Naming conventions

Your Set<PlatePair> is called platePair. At minimum the variable name should be a plural, because, as it stands, it makes sense that platePair is a single PlatePair, and not a Set<PlatePair>. My preference would be 'moves' which indicates what the data represents

Oh, your class is called ToweOfHanoi, but should contain an 'r' as in TowerOfHanoi

Collections

Speaking of Set<PlatePair> ... really? Your actual implementation of the Set<PlatePair> is a LinkedHashSet. The LinkedHashSet will iterate the results in the same order they were inserted, which is why this solution actually works, but, you do not expose that property of the LinkedHashSet to the calling functions. There is nothing stopping a user from calling:

Set<PlatePair> result = new HashSet<>();
moveTowers(4, "A", "B", "C", result);

and this would produce crap results.

Frankly, you should not be using a set at all. You should be using a List.... because that is what it is, a List of moves to make.

This is your duct tape LinkedHashSet is a desperate solution to trying to bring order to a data collection that is designed to maintain unique contents (a Set) rather than an ordered collection of non-unique data (a List). Your moves are not unique... you often move a tile from tower A to tower C.... but, you use the the HashSet with unique move instances (instead of the neater move-reuse mechanism).

A more immediate solution is to change the moveTower from being a public method to being a private method, which you should do anyway. There is no need for it to be public. Making it private would also affect the assert in the method.... you assert that the platePair instance is not null, but you do not check the from/using/to instances. That is careless. If you are going to assert, then do it comprehensively. In this case, if the method is changed to be private, I would simply remove the asserts, and move on.... you do trust your own code, right?

PlatePair

Which comes down to the next problem, The PlatePair class. This class should have a number of differences. Firstly, the values should not be Strings, they should be an ENUM, one member for each tower.

public enum Tower {
    A, B, C;
}

public class PlatePair {
    private final Tower source, destination;

    public PlatePair(Tower source, Tower destination) {
        this.source = source;
        this.destination = destination;
    }

    public Tower getSource() {...}
    public Tower getDestination() {...}

}

I would also strongly encourage you to avoid creating so many PlatePair instances.... there are only 6 possible moves that can be made... each Tower can only be the source/destination of 2 possible moves. You should only have 6 PlatePair instances, and they should be immutable, and have good hashCode() and equals() methods.

Also, I don't like the class name PlatePair. It is not a pair of Plates, it is an ordered pair of Towers... a source, and a destination. I would rename it something like Transfer.

Conclusion

The code works, and gets the right answers. It does not read very well, and there are a few gotcha's in the code which mean you have to dig in to the code and understand the 'tricks' you are playing. The documentation/comments are really poor, and this code would fail any formal review in any sane business.

I have taken your code, and restructured it using the ideas I have shown above. This is closer to something that I would consider readable. Note, I have not changed the algorithm at all:

import java.util.ArrayList;
import java.util.EnumMap;
import java.util.List;

enum Tower {
    A, B, C;


    static {

        // make each tower know what moves are possible from that tower.
        // tower A can have a transfer to towers B, and C.
        // tower B can have a transfer to towers A, and C.
        // tower C can have a transfer to towers A, and B.
        // these 2 transfers per tower are available through the getMove(destination)
        // method for each tower.
        A.setupTransfers(B, C);
        B.setupTransfers(A, C);
        C.setupTransfers(A, B);

    }

    private EnumMap<Tower, Transfer> destinations = null;

    private void setupTransfers(Tower one, Tower two) {
        destinations = new EnumMap<Tower, Transfer>(Tower.class);
        destinations.put(one, new Transfer(this, one));
        destinations.put(two, new Transfer(this, two));
    }

    public Transfer getMove(Tower destination) {
        return destinations.get(destination);
    }
}

final class Transfer {

    private final Tower source;
    private final Tower destination;

    public Transfer(Tower source, Tower destination) {
        this.source = source;
        this.destination = destination;
    }

    public Tower getSource() {
        return source;
    }

    public Tower getDestination() {
        return destination;
    }

    @Override
    public int hashCode() {
        return (31 * source.hashCode()) ^ destination.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Transfer) {
            return ((Transfer) obj).source == source
                    && ((Transfer) obj).destination == destination;
        }
        return false;
    }
}

public final class TowerOfHanoi {

    private TowerOfHanoi() {
    }

    /**
     * Solves the Tower of Hanoi problem
     * 
     * @param n
     *        The number of plates on the starting tower
     * @return The sequential steps required to solve the problem.
     */
    public static List<Transfer> solve(int n) {
        if (n <= 0)
            throw new IllegalArgumentException("The number of plates " + n
                    + " should be greater than zero.");

        final List<Transfer> moves = new ArrayList<Transfer>();
        moveTowers(n, Tower.A, Tower.B, Tower.C, moves);
        return moves;
    }

    private static void moveTowers(int n, Tower from, Tower using, Tower to,
            List<Transfer> moves) {

        if (n == 0) {
            return;
        }

        // algorithm is:
        // we want to move the 'bottom' tile from the 'from' tower to the 'to'
        // tower.
        // we move everything on top of it to the 'using' tower
        // then we move the tile to the to tower,
        // then we move the things from the using tower back on top of the tile
        // we moved.

        // temporarily move everything on top to the using tower.
        moveTowers(n - 1, from, to, using, moves);
        // move the actual tile.
        moves.add(from.getMove(to));
        // move the temp stuff back on to the tile we just moved.
        moveTowers(n - 1, using, from, to, moves);
    }

    public static void main(String[] args) {
        for (final Transfer getHanoi : solve(4)) {
            System.out.println(getHanoi.getSource() + " : "
                    + getHanoi.getDestination());
        }
    }
}