5
\$\begingroup\$

See the next iteration.

I was in the mood for some basic AI, and decided to code up an algorithm for solving "\$M\$ missionaries, \$C\$ cannibals in the boat with \$B\$ places" -problem:

Demo.java:

package net.coderodde.fun.cannibals;

import java.util.List;
import net.coderodde.fun.cannibals.support.BreadthFirstSearchPathFinder;

/**
 * This class implements a demonstration.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class Demo {

    public static void main(String[] args) {
        UnweightedShortestPathFinder<StateNode> finder = 
                new BreadthFirstSearchPathFinder<>();

        long ta = System.currentTimeMillis();

        List<StateNode> path = 
                finder.search(StateNode.getInitialStateNode(5, 5, 3), 
                             (StateNode node) -> 
                             { return node.isSolutionState(); });

        long tb = System.currentTimeMillis();

        System.out.println("Duration: " + (tb - ta) + " milliseconds.");

        int fieldLength = ("" + path.size()).length();

        if (path.isEmpty()) {
            System.out.println("No solution.");
        } else {
            for (int i = 0; i < path.size(); ++i) {
                System.out.printf("State %" + fieldLength + "d: %s\n", 
                                  (i + 1), 
                                  path.get(i));
            }
        }
    }
}

StateNode.java:

package net.coderodde.fun.cannibals;

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

/**
 * This class implements a state of the "Cannibals and Missionaries" puzzle. As 
 * crossing a river involves two banks, {@code missionaries} denotes the amount
 * of missionaries on the source bank, and 
 * {@code totalMissionaries - missionaries} is the amount of missionaries on the
 * target bank. Same arithmetics applies to cannibals.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class StateNode implements Iterable<StateNode> {

    /**
     * The minimum allowed amount of cannibals or missionaries.
     */
    private static final int MIN_TOTAL = 1;

    /**
     * The minimum boat capacity.
     */
    private static final int MIN_BOAT_CAPACITY = 1;

    /**
     * This enumeration enumerates all possible boat locations.
     */
    public enum BoatLocation {

        /**
         * The boat location where all figures start.
         */
        SOURCE_BANK,

        /**
         * The boat location all figures want to reach.
         */
        TARGET_BANK
    }

    /**
     * The amount of missionaries at the source bank.
     */
    private final int missionaries;

    /**
     * The amount of cannibals at the source bank.
     */
    private final int cannibals;

    /**
     * The total amount of missionaries involved in the game.
     */
    private final int totalMissionaries;

    /**
     * The total amount of cannibals involved in the game.
     */
    private final int totalCannibals;

    /**
     * The amount of places in the boat.
     */
    private final int boatCapacity;

    /**
     * The location of the boat.
     */
    private final BoatLocation boatLocation;

    /**
     * Constructs this state.
     * 
     * @param missionaries      amount of missionaries at a bank.
     * @param cannibals         amount of cannibals at the same ban.
     * @param totalMissionaries total amount of missionaries.
     * @param totalCannibals    total amount of cannibals.
     * @param boatCapacity      total amount of places in the boat.
     * @param boatLocation      the location of the boat.
     */
    public StateNode(int missionaries, 
                     int cannibals, 
                     int totalMissionaries,
                     int totalCannibals,
                     int boatCapacity,
                     BoatLocation boatLocation) {
        Objects.requireNonNull(boatLocation, "Boat location is null.");
        checkTotalMissionaries(totalMissionaries);
        checkTotalCannibals(totalCannibals);
        checkMissionaryCount(missionaries, totalMissionaries);
        checkCannibalCount(cannibals, totalCannibals);
        checkBoatCapacity(boatCapacity);

        this.missionaries = missionaries;
        this.cannibals = cannibals;
        this.totalMissionaries = totalMissionaries;
        this.totalCannibals = totalCannibals;
        this.boatCapacity = boatCapacity;
        this.boatLocation = boatLocation;
    }

    /**
     * Creates the source state node.
     * 
     * @param totalMissionaries the total amount of missionaries.
     * @param totalCannibals    the total amount of cannibals.
     * @param boatCapacity      the total amount of places in the boat.
     * @return the initial state node.
     */
    public static StateNode getInitialStateNode(int totalMissionaries,
                                                int totalCannibals,
                                                int boatCapacity) {
        return new StateNode(totalMissionaries,
                             totalCannibals,
                             totalMissionaries,
                             totalCannibals,
                             boatCapacity,
                             BoatLocation.SOURCE_BANK);
    }

    /**
     * Checks whether this state encodes a solution state, in which all figures
     * are safely at the target bank.
     * 
     * @return {@code true} if this state is a solution state.
     */
    public boolean isSolutionState() {
        return boatLocation == BoatLocation.TARGET_BANK 
                && missionaries == 0
                && cannibals == 0;
    }

    /**
     * Checks whether this state is terminal, which is the case whenever at some
     * bank cannibals outnumber missionaries.
     * 
     * @return {@code true} if this state is terminal.
     */
    public boolean isTerminalState() {
        if (missionaries > 0 && missionaries < cannibals) {
            // At the source bank, cannibals outnumber missionaries. Game over.
            return true;
        }

        int missionariesAtTargetBank = totalMissionaries - missionaries;
        int cannibalsAtTargetBank = totalCannibals - cannibals;

        if (missionariesAtTargetBank > 0
                && missionariesAtTargetBank < cannibalsAtTargetBank) {
            // At the target bank, cannibals outnumber missionaries. Game over.
            return true;
        }

        return false;
    }

    /**
     * Returns an iterator over this state's neighbor states.
     * 
     * @return an iterator.
     */
    @Override
    public Iterator<StateNode> iterator() {
        return new NeighborStateIterator();
    }

    /**
     * {@inheritDoc }
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        int missionaryFieldLength = ("" + totalMissionaries).length();
        int cannibalFieldLength = ("" + totalCannibals).length();

        // Situation at the source bank.
        sb.append(String.format("[m: %" + missionaryFieldLength + "d", 
                                missionaries));
        sb.append(String.format(", c: %" + cannibalFieldLength + "d]", 
                                cannibals));

        // Draw boat location.
        switch (boatLocation) {
            case SOURCE_BANK: {
                sb.append("v ~~~  ");
                break;
            }

            case TARGET_BANK: {
                sb.append("  ~~~ v");
                break;
            }
        }

        // Situation at the destination bank.
        sb.append(String.format("[m: %" + missionaryFieldLength + "d", 
                                totalMissionaries - missionaries));
        sb.append(String.format(", c: %" + cannibalFieldLength + "d]", 
                                totalCannibals - cannibals));
        return sb.toString();
    }

    /**
     * {@inheritDoc } 
     */
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof StateNode)) {
            return false;
        }

        StateNode other = (StateNode) o;
        return missionaries == other.missionaries 
                && cannibals == other.cannibals
                && totalMissionaries == other.totalMissionaries
                && totalCannibals == other.totalCannibals
                && boatLocation == other.boatLocation;
    }

    /**
     * {@inheritDoc } 
     */
    @Override
    public int hashCode() {
        // Generated by NetBeans.
        int hash = 7;
        hash = 31 * hash + this.missionaries;
        hash = 31 * hash + this.cannibals;
        hash = 31 * hash + this.totalMissionaries;
        hash = 31 * hash + this.totalCannibals;
        hash = 31 * hash + Objects.hashCode(this.boatLocation);
        return hash;
    }

    // Implements the actual iterator.
    private class NeighborStateIterator implements Iterator<StateNode> {

        private final Iterator<StateNode> iterator;

        public NeighborStateIterator() {
            this.iterator = generateNeighbors();
        }

        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public StateNode next() {
            return iterator.next();
        }

        // Populates the list of neighbor states.
        private Iterator<StateNode> generateNeighbors() {
            if (isTerminalState()) {
                // Ignore terminal state nodes.
                return Collections.<StateNode>emptyIterator();
            }

            List<StateNode> list = new ArrayList<>();

            switch (StateNode.this.boatLocation) {
                case SOURCE_BANK: {
                    trySendFromSourceBank(list);
                    break;
                }

                case TARGET_BANK: {
                    trySendFromTargetBank(list);
                    break;
                }
            }

            return list.iterator();
        }

        // Attempts to send some figures from the source bank to the target 
        // bank.
        private void trySendFromSourceBank(List<StateNode> list) {
            int availableMissionaries = Math.min(missionaries, boatCapacity);
            int availableCannibals = Math.min(cannibals, boatCapacity);

            for (int capacity = 1; capacity <= boatCapacity; ++capacity) {
                for (int m = 0; m <= availableMissionaries; ++m) {
                    for (int c = 0; c <= availableCannibals; ++c) {
                        if (0 < c + m && c + m <= capacity) {
                            list.add(new StateNode(missionaries - m,
                                                   cannibals - c,
                                                   totalMissionaries,
                                                   totalCannibals,
                                                   boatCapacity,
                                                   BoatLocation.TARGET_BANK));
                        }
                    }
                }
            }
        }

        // Attempts to send some figures from the target bank to the source
        // bank.
        private void trySendFromTargetBank(List<StateNode> list) {
            int availableMissionaries = 
                    Math.min(totalMissionaries - missionaries, boatCapacity);
            int availableCannibals = 
                    Math.min(totalCannibals - cannibals, boatCapacity);

            for (int capacity = 1; capacity <= boatCapacity; ++capacity) {
                for (int m = 0; m <= availableMissionaries; ++m) {
                    for (int c = 0; c <= availableCannibals; ++c) {
                        if (0 < c + m && c + m <= capacity) {
                            list.add(new StateNode(missionaries + m,
                                                   cannibals + c,
                                                   totalMissionaries,
                                                   totalCannibals,
                                                   boatCapacity,
                                                   BoatLocation.SOURCE_BANK));
                        }
                    }
                }
            }
        }
    }

    /**
     * Checks that the total amount of missionaries is sensible.
     * 
     * @param totalMissionaries total amount of missionaries.
     */
    private static void checkTotalMissionaries(int totalMissionaries) {
        checkIntNotLess(totalMissionaries, 
                        MIN_TOTAL, 
                        "The total amount of missionaries is too small: " +
                        totalMissionaries + ". Should be at least " +
                        MIN_TOTAL);
    }

    /**
     * Checks that the total amount of cannibals is sensible.
     * 
     * @param totalCannibals total amount of cannibals.
     */
    private static void checkTotalCannibals(int totalCannibals) {
        checkIntNotLess(totalCannibals, 
                        MIN_TOTAL, 
                        "The total amount of cannibals is too small: " +
                        totalCannibals + ". Should be at least " +
                        MIN_TOTAL);
    }

    /**
     * Checks that missionary count is in order.
     * 
     * @param missionaries      the amount of missionaries at the source bank.
     * @param totalMissionaries total amount of missionaries in the game.
     */
    private static void checkMissionaryCount(int missionaries,
                                             int totalMissionaries) {
        checkNotNegative(missionaries, 
                         "Negative amount of missionaries: " + missionaries);
        checkIntNotLess(totalMissionaries, 
                        missionaries,
                        "Missionaries at a bank (" + missionaries + "), " + 
                        "missionaries in total (" + totalMissionaries + ").");
    }

    /**
     * Checks that cannibal count is in order.
     * 
     * @param cannibals      the amount of cannibals at the source bank.
     * @param totalCannibals total amount of cannibals in the game.
     */
    private static void checkCannibalCount(int cannibals,
                                           int totalCannibals) {
        checkNotNegative(cannibals,
                         "Negative amount of cannibals: " + cannibals);
        checkIntNotLess(totalCannibals,
                        cannibals,
                        "Cannibals at a bank (" + cannibals + "), " +
                        "cannibals in total (" + totalCannibals + ").");
    }

    /**
     * Checks that boat capacity is sensible.
     * 
     * @param boatCapacity the boat capacity.
     */
    private static void checkBoatCapacity(int boatCapacity) {
        checkIntNotLess(boatCapacity, 
                        MIN_BOAT_CAPACITY, 
                        "Boat capacity too small: " + boatCapacity + ", " +
                        "must be at least " + MIN_BOAT_CAPACITY + ".");
    }

    /**
     * Checks that {@code integer} is no less than {@code minimum}, and if it
     * is, throws an exception with message {@code errorMessage}.
     * 
     * @param integer      the integer to check.
     * @param minimum      the minimum allowed value of {@code integer}.
     * @param errorMessage the error message.
     * @throws IllegalArgumentException if {@code integer < minimum}.
     */
    private static void checkIntNotLess(int integer,
                                        int minimum,
                                        String errorMessage) {
        if (integer < minimum) {
            throw new IllegalArgumentException(errorMessage);
        }
    }

    /**
     * Checks that {@code integer} is not negative.
     * 
     * @param integer      the integer to check.
     * @param errorMessage the error message for the exception upon failure.
     */
    private static void checkNotNegative(int integer, String errorMessage) {
        checkIntNotLess(integer, 0, errorMessage);
    }
}

UnweightedShortestPathFinder.java:

package net.coderodde.fun.cannibals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.function.Predicate;

/**
 * This interface defines the API for shortest path algorithms in unweighted 
 * graphs.
 * 
 * @author Rodion "rodde" Efremov
 * @param <N> the node type.
 */
public interface UnweightedShortestPathFinder<N extends Iterable<N>> {

    /**
     * Searches a shortest, unweighted path from {@code source} to any node for
     * which {@code targetPredicate.test} returns {@code true}. 
     * 
     * @param source          the source node.
     * @param targetPredicate the target node predicate.
     * @return a shortest path from {@code source} to the first node that passes
     *         the target node predicate, or an empty list if there is no such.
     */
    List<N> search(N source, Predicate<N> targetPredicate);

    /**
     * Constructs a shortest path.
     * 
     * @param target    the target node.
     * @param parentMap the map mapping each node to its predecessor on the 
     *                  shortest path.
     * @return a shortest path.
     */
    default List<N> tracebackPath(N target, Map<N, N> parentMap) {
        List<N> ret = new ArrayList<>();
        N current = target;

        while (current != null) {
            ret.add(current);
            current = parentMap.get(current);
        }

        Collections.<N>reverse(ret);
        return ret;
    }
}

BreadthFirstSearchPathFinder.java:

package net.coderodde.fun.cannibals.support;

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.function.Predicate;
import net.coderodde.fun.cannibals.UnweightedShortestPathFinder;

/**
 * This class implements the breadth-first search path finder.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <N> the node implementation type.
 */
public class BreadthFirstSearchPathFinder<N extends Iterable<N>> 
implements UnweightedShortestPathFinder<N> {

    /**
     * Searches for a shortest path using breadth-first search.
     * 
     * @param source          the source node.
     * @param targetPredicate the target node predicate.
     * @return the shortest path from source to the first node that passes the
     *         target node predicate.
     */
    @Override
    public List<N> search(N source, Predicate<N> targetPredicate) {
        Objects.requireNonNull(source, "The source node is null.");
        Objects.requireNonNull(targetPredicate, 
                               "The target predicate is null.");

        Map<N, N> parentMap = new HashMap<>();
        Deque<N> queue = new ArrayDeque<>();

        parentMap.put(source, null);
        queue.addLast(source);

        while (!queue.isEmpty()) {
            N current = queue.removeFirst();

            if (targetPredicate.test(current)) {
                return tracebackPath(current, parentMap);
            }

            for (N child : current) {
                if (!parentMap.containsKey(child)) {
                    parentMap.put(child, current);
                    queue.addLast(child);
                }
            }
        }

        return Collections.<N>emptyList();
    }
}

For \$(M, C, D) = (3, 3, 2)\$ I get

Duration: 83 milliseconds.
State  1: [m: 3, c: 3]v ~~~  [m: 0, c: 0]
State  2: [m: 3, c: 1]  ~~~ v[m: 0, c: 2]
State  3: [m: 3, c: 2]v ~~~  [m: 0, c: 1]
State  4: [m: 3, c: 0]  ~~~ v[m: 0, c: 3]
State  5: [m: 3, c: 1]v ~~~  [m: 0, c: 2]
State  6: [m: 1, c: 1]  ~~~ v[m: 2, c: 2]
State  7: [m: 2, c: 2]v ~~~  [m: 1, c: 1]
State  8: [m: 0, c: 2]  ~~~ v[m: 3, c: 1]
State  9: [m: 0, c: 3]v ~~~  [m: 3, c: 0]
State 10: [m: 0, c: 1]  ~~~ v[m: 3, c: 2]
State 11: [m: 0, c: 2]v ~~~  [m: 3, c: 1]
State 12: [m: 0, c: 0]  ~~~ v[m: 3, c: 3]

as should be. For example, with \$M = 5, N = 5, B = 3\$, I get:

Duration: 87 milliseconds.
State  1: [m: 5, c: 5]v ~~~  [m: 0, c: 0]
State  2: [m: 5, c: 3]  ~~~ v[m: 0, c: 2]
State  3: [m: 5, c: 4]v ~~~  [m: 0, c: 1]
State  4: [m: 5, c: 1]  ~~~ v[m: 0, c: 4]
State  5: [m: 5, c: 2]v ~~~  [m: 0, c: 3]
State  6: [m: 2, c: 2]  ~~~ v[m: 3, c: 3]
State  7: [m: 3, c: 3]v ~~~  [m: 2, c: 2]
State  8: [m: 0, c: 3]  ~~~ v[m: 5, c: 2]
State  9: [m: 0, c: 4]v ~~~  [m: 5, c: 1]
State 10: [m: 0, c: 2]  ~~~ v[m: 5, c: 3]
State 11: [m: 0, c: 3]v ~~~  [m: 5, c: 2]
State 12: [m: 0, c: 0]  ~~~ v[m: 5, c: 5]
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

main

        long tb = System.currentTimeMillis();

        System.out.println("Duration: " + (tb - ta) + " milliseconds.");

I'd prefer more descriptive names like startTime and endTime.

            for (int i = 0; i < path.size(); ++i) {
                System.out.printf("State %" + fieldLength + "d: %s\n", 
                                  (i + 1), 
                                  path.get(i));
            }

I'd prefer the for each version.

            int i = 0;
            for (StateNode step : path) {
                System.out.printf("State %" + fieldLength + "d: %s\n", 
                                  ++i, 
                                  step);
            }

This doesn't rely on the compiler implementing List.get and size() efficiently. Nor does it require proper handling of the boundaries. It does add an extra variable (step) and makes integration with i less strict, so your preference may vary.

StateNode

    /**
     * The total amount of missionaries involved in the game.
     */
    private final int totalMissionaries;

    /**
     * The total amount of cannibals involved in the game.
     */
    private final int totalCannibals;

    /**
     * The amount of places in the boat.
     */
    private final int boatCapacity;

Why store these values in every StateNode? You could have a Game object that holds this information and pass it to StateNode. Then each StateNode just needs to remember the location of Game.

A side benefit of this is that you would only need to check that totalMissionaries, totalCannibals, and boatCapacity are valid at the beginning of the game. You currently check each time a new StateNode is created.

            int availableCannibals = Math.min(cannibals, boatCapacity);

            for (int capacity = 1; capacity <= boatCapacity; ++capacity) {
                for (int m = 0; m <= availableMissionaries; ++m) {
                    for (int c = 0; c <= availableCannibals; ++c) {
                        if (0 < c + m && c + m <= capacity) {

It seems like you should be able to simplify this. For example, you don't seem to need capacity at all.

            for (int m = 0; m <= availableMissionaries; ++m) {
                for (int c = ((m == 0) ? 1 : 0), availableCannibals = Math.min(cannibals, boatCapacity - m); c <= availableCannibals; ++c) {

You also don't need the if, as that logic can be moved into the cannibal for loop. Now you only generate c/m pairs that meet the criteria of the original.

Originally you check on each iteration of the innermost loop. Now you only check on each iteration of the missionary loop.

This also adds fewer duplicate nodes to the list. Note that the original would attempt to add 0 missionaries and 1 cannibal to the list boatCapacity times. This only adds each combination once.

You can move the declaration of availableCannibals outside the cannibal for loop declaration if you want. I just did it this way as a demonstration. Of course, it has to stay inside the missionary for loop.

You could also limit the nodes you add to the list by checking that a trip will produce a valid state before creating the node.

N extends Iterable<N>

I don't agree with this implementation. Yes, it will work. But it does so by stomping on the meaning of Iterable. You say

            for (N child : current) {

I'd far rather see

            for (N child : current.generateNeighbors()) {

That's much clearer about the fact that it is generating a collection. The first notation implies that current is a collection.

Note that in the latter version, you don't have to override the Iterable methods at all. It will just work if you have generateNeighbors return the list rather than an iterator over the list.

This strikes me as the kind of neat idea that you try until you realize that it is actually making things more complicated for you. It's an interesting approach. I just don't think it adds anything for you. It's just extra work that obscures what you are actually doing.

You seem to be saying that you want N to be any type that iterates over itself. But that's not really what you want. You want N to be a type that generates neighbors. So create your own interface that calls for a generateNeighbors method.

As a general rule, if you find yourself redefining the meaning of something, you are probably going down the wrong path. This was a big problem with operator overloading in C++. People would create new meanings for operators which would then lead to code confusion as people expected + to do addition, not a set union or a string concatenation or whatever.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.