TowerOfHanoi.java

package g_79ff0bed607bef315c4353b374e1319e;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

import static java.util.Objects.requireNonNull;

/**
 * A program solves <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">Tower of Hanoi</a>.
 *
 * @author Jin Kwon &lt;onacit_at_gmail.com&gt;
 */
public class TowerOfHanoi {

    /**
     * Represents a disk movable between rods.
     */
    public static class Disk
            implements Comparable<Disk> {

        /**
         * Creates a new instance of given size.
         *
         * @param size the size of the newly created disk; must be positive.
         */
        public Disk(final int size) {
            super();
            if (size <= 0) {
                throw new IllegalArgumentException("size(" + size + ") <= 0");
            }
            this.size = size;
        }

        /**
         * Returns a string representation of this disk.
         *
         * @return a string representation of this disk.
         */
        @Override
        public String toString() {
            return super.toString() + '{'
                   + "size=" + size
                   + '}';
        }

        @Override
        public boolean equals(final Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null || getClass() != obj.getClass()) {
                return false;
            }
            final Disk disk = (Disk) obj;
            return size == disk.size;
        }

        @Override
        public int hashCode() {
            return Objects.hash(size);
        }

        /**
         * Compares this disk with the specified disk for order. Returns a negative integer, zero, or a positive integer
         * as this disk's {@code size} is less than, equal to, or greater than the specified disk's {@code size}.
         *
         * @param disk the disk whose {@code size} is compared.
         * @return a negative integer, zero, or a positive integer * as this disk's {@code size} is less than, equal to,
         * or greater than the specified disk's {@code size}.
         * @see Integer#compare(int, int)
         */
        public int compareTo(final Disk disk) {
            return Integer.compare(size, disk.size);
        }

        /**
         * The size of this disk.
         */
        public final int size;
    }

    /**
     * Represents a rod on which disks are stacked.
     */
    public static class Rod {

        /**
         * Create a new instance of given name with specified number of disks.
         *
         * @param name  the name of newly created rod.
         * @param disks initial number of disks; {@code 0} for an empty rod.
         */
        public Rod(final String name, final int disks) {
            super();
            this.name = requireNonNull(name);
            if (disks < 0) {
                throw new IllegalArgumentException("disks(" + disks + ") < 0");
            }
            this.disks = new ArrayList<>();
            for (int size = disks; size > 0; size--) {
                this.disks.add(new Disk(size));
            }
        }

        /**
         * Returns a string representation of this rod.
         *
         * @return a string representation of this rod.
         */
        @Override
        public String toString() {
            return super.toString() + '{'
                   + "name=" + name
                   + ",disks=" + disks
                   + '}';
        }

        /**
         * Moves a disk from this rod to specified rod.
         *
         * @param rod the rod to which a disk of this rod is moved.
         */
        public void moveDiskTo(final Rod rod) {
            if (requireNonNull(rod, "rod is null") == this) {
                throw new IllegalArgumentException("unable to move a disk to self");
            }
            if (disks.isEmpty()) {
                throw new IllegalStateException("no disk to move");
            }
            final Disk disk = take();
            System.out.println("Moving " + disk + " from " + this + " to " + rod);
            rod.put(disk);
        }

        private Disk take() {
            if (disks.isEmpty()) {
                throw new IllegalStateException("no disk to take");
            }
            return disks.remove(disks.size() - 1);
        }

        private void put(final Disk disk) {
            requireNonNull(disk, "disk is null");
            if (disks.contains(disk)) {
                throw new IllegalArgumentException("disk is already on this rod: " + disk);
            }
            if (!disks.isEmpty()) {
                final Disk top = disks.get(disks.size() - 1);
                if (top.compareTo(disk) < 0) {
                    throw new IllegalArgumentException("unable to put " + disk + " on top of " + top);
                }
            }
            disks.add(disk);
        }

        /**
         * The name of this rod.
         */
        public final String name;

        /**
         * The disks on this rod.
         */
        private final List<Disk> disks;
    }

    /**
     * Moves specified number of disks from specified source rod to specified target rod using specified auxiliary rod.
     *
     * @param disks     the number of disks to move.
     * @param source    the source rod from which disks are moved.
     * @param target    the target rod to which disks are moved.
     * @param auxiliary the auxiliary rod to use.
     */
    private static void move(final int disks, final Rod source, final Rod target, final Rod auxiliary) {
        if (disks <= 0) {
            throw new IllegalArgumentException("disks(" + disks + ") <= 0");
        }
        if (source == null) {
            throw new NullPointerException("source is null");
        }
        if (target == null) {
            throw new NullPointerException("target is null");
        }
        if (auxiliary == null) {
            throw new NullPointerException("auxiliary is null");
        }
        if (disks == 1) {
            // Move the disk from source directly to target.
            source.moveDiskTo(target);
            return;
        }
        // Move N-1 disks from source to auxiliary
        move(disks - 1, source, auxiliary, target);
        // Move a disk from source to target
        move(1, source, target, auxiliary);
        // Move N-1 disks from auxiliary to target
        move(disks - 1, auxiliary, target, source);
    }

    /**
     * The main method of this program.
     *
     * @param args command line arguments whose first element is the number of disks to move.
     */
    public static void main(final String... args) {
        final int disks;
        try {
            disks = Integer.parseInt(args[0]);
        } catch (final ArrayIndexOutOfBoundsException aioobe) {
            System.err.println("Please specify the number of disks.");
            return;
        }
        if (disks <= 0) {
            System.err.println("Negative number of disks specified: " + disks);
            return;
        }
        final Rod source = new Rod("source", disks);
        final Rod target = new Rod("target", 0);
        final Rod auxiliary = new Rod("auxiliary", 0);
        move(disks, source, target, auxiliary);
    }

    /**
     * Creates a new instance which is not possible.
     */
    private TowerOfHanoi() {
        throw new AssertionError("instantiation is not allowed");
    }
}