Generalized Missionaries and Cannibals in Java

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 finder = 
                new BreadthFirstSearchPathFinder<>();

        long ta = System.currentTimeMillis();

        List 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 cla

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

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.

StackExchange Code Review Q#100457, answer score: 5