Wolves, Goats and Cabbages in Java

Question

I thought I would try and write a solution to the Wolf, Goat and Cabbage problem in Java 8 to try and get to grips with lambdas.

I am looking for any feedback you might provide. The feedback I am looking for is mainly on code structure and where I could make more, or more simple, use of new Java 8 features.

The basic idea of the code is to try and encapsulate the behaviour of the elements of the problem in an OO fashion and process them using lambdas.

I started with an enum Member to encapsulate the players of the game. It should be self explanatory.

enum Member {

    FARMER,
    WOLF,
    CABBAGE {
                @Override
                public boolean isSafe(final Set<Member> others) {
                    return others.contains(FARMER) || !others.contains(GOAT);
                }
            },
    GOAT {
                @Override
                public boolean isSafe(final Set<Member> others) {
                    return others.contains(FARMER) || !others.contains(WOLF);
                }
            };

    public boolean isSafe(final Set<Member> others) {
        return true;
    }
}

Next is the class Bank, this encalsulates a river bank:

import static com.google.common.base.Preconditions.checkState;

public final class Bank {

    public static Bank all() {
        return new Bank(EnumSet.allOf(Member.class));
    }

    public static Bank none() {
        return new Bank(ImmutableSet.of());
    }

    private final ImmutableSet<Member> members;

    public Bank(final Set<Member> members) {
        this.members = ImmutableSet.copyOf(members);
    }

    public Bank accept(final Member member) {
        checkState(!members.contains(member) && !members.contains(Member.FARMER));
        final Set<Member> ms = Sets.newHashSet(members);
        ms.add(member);
        ms.add(Member.FARMER);
        return new Bank(ms);
    }

    public Bank evict(final Member member) {
        checkState(members.contains(member) && members.contains(Member.FARMER));
        final Set<Member> ms = Sets.newHashSet(members);
        ms.remove(member);
        ms.remove(Member.FARMER);
        return new Bank(ms);
    }

    public boolean farmerIsHere() {
        return members.contains(Member.FARMER);
    }

    public boolean hasAllMembers() {
        return equals(all());
    }

    public boolean isEmpty() {
        return members.isEmpty();
    }

    public boolean isFeasible() {
        return members.stream().allMatch((m) -> m.isSafe(members));
    }

    public Stream<Member> stream() {
        return members.stream();
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 97 * hash + Objects.hashCode(this.members);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Bank other = (Bank) obj;
        return Objects.equals(this.members, other.members);
    }

}

This class allows the transferal of items from bank to bank according to the rules of the puzzle.

The next class encapsulates the state of play at any given time:

final class State {

    private final Bank leftBank;
    private final Bank rightBank;

    public State(final Bank leftBank, final Bank rightBank) {
        this.leftBank = leftBank;
        this.rightBank = rightBank;
    }

    public Bank leftBank() {
        return leftBank;
    }

    public Bank rightBank() {
        return rightBank;
    }

    public boolean isInitialState() {
        return leftBank.hasAllMembers() && rightBank.isEmpty();
    }

    public boolean isSolution() {
        return rightBank.hasAllMembers() && leftBank.isEmpty();
    }

    public boolean isFeasible() {
        return leftBank.isFeasible() && rightBank.isFeasible();
    }

    public State moveToRight(final Member member) {
        return new State(leftBank.evict(member), rightBank.accept(member));
    }

    public State moveToLeft(final Member member) {
        return new State(leftBank.accept(member), rightBank.evict(member));
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 97 * hash + Objects.hashCode(this.leftBank);
        hash = 97 * hash + Objects.hashCode(this.rightBank);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final State other = (State) obj;
        if (!Objects.equals(this.leftBank, other.leftBank)) {
            return false;
        }
        if (!Objects.equals(this.rightBank, other.rightBank)) {
            return false;
        }
        return true;
    }
}

This has various methods for determining whether that state is a solution etc.

Next I have the interface Action and class ActionImpl, this stores the "graph" of the solution - so that the path to the solution can be determined:

public interface Action<T> {

    Action<T> previous();

    T data();

    Collection<Action<T>> children();

    void children(Collection<Action<T>> children);

}

public class ActionImpl<T> implements Action<T> {

    private final Action<T> previous;
    private final T data;
    private Collection<Action<T>> children;

    public ActionImpl(final Action<T> previous, final T data) {
        this.previous = previous;
        this.data = data;
    }

    @Override
    public Action<T> previous() {
        return previous;
    }

    @Override
    public T data() {
        return data;
    }

    @Override
    public Collection<Action<T>> children() {
        return children;
    }

    @Override
    public void children(Collection<Action<T>> children) {
        this.children = children;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 43 * hash + Objects.hashCode(this.data);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final ActionImpl<?> other = (ActionImpl<?>) obj;
        return Objects.equals(this.data, other.data);
    }
}

Now for the meat of the puzzle, this is the class that solves the puzzle:

public class App {

    public static void main(final String[] args) throws Exception {
        final State initalState = new State(Bank.all(), Bank.none());
        final Action<State> finalState = calculateGraph(new ActionImpl<>(null, initalState));
        final List<State> solution = ImmutableList.copyOf(getSoltutionPath(finalState));
        final ListIterator<State> solIter = solution.listIterator(solution.size());
        while (solIter.hasPrevious()) {
            System.out.println(solIter.previous());
        }
    }

    private static Action<State> calculateGraph(final Action<State> parent) {
        final Collection<Action<State>> states = calculateChildren(parent);
        parent.children(states);
        return states.stream().filter((n) -> n.data().isSolution()).findFirst().orElse(parent);
    }

    private static Collection<Action<State>> calculateChildren(final Action<State> parent) {
        final State s = parent.data();
        if (s.leftBank().farmerIsHere()) {
            return process(parent, calculateMoves(s.leftBank(), (m) -> s.moveToRight(m)));
        }
        if (s.rightBank().farmerIsHere()) {
            return process(parent, calculateMoves(s.rightBank(), (m) -> s.moveToLeft(m)));
        }
        throw new IllegalStateException("We seem to have lost the farmer.");
    }

    private static Collection<Action<State>> process(final Action<State> parent, final Collection<State> children) {
        final Set<State> path = getSoltutionPath(parent);
        return children.stream().
                filter((s) -> !path.contains(s)).
                map((s) -> calculateGraph(new ActionImpl<>(parent, s))).
                collect(Collectors.toSet());
    }

    private static Set<State> calculateMoves(final Bank bank, final Function<Member, State> mover) {
        return bank.stream().map(mover).filter(State::isFeasible).collect(Collectors.toSet());
    }

    private static Set<State> getSoltutionPath(Action<State> leaf) {
        final ImmutableSet.Builder<State> lb = ImmutableSet.builder();
        while (leaf != null) {
            lb.add(leaf.data());
            leaf = leaf.previous();
        }
        return lb.build();
    }
}

The idea is to recursively walk the graph of feasible moves and bubble the target state up through the recursion. The solution can then be determined by walking back up the parent nodes in the solution graph.

For completeness the output of running the code is:

State(leftBank=Bank(members=[FARMER, WOLF, CABBAGE, GOAT]), rightBank=Bank(members=[]))
State(leftBank=Bank(members=[CABBAGE, WOLF]), rightBank=Bank(members=[GOAT, FARMER]))
State(leftBank=Bank(members=[CABBAGE, WOLF, FARMER]), rightBank=Bank(members=[GOAT]))
State(leftBank=Bank(members=[WOLF]), rightBank=Bank(members=[GOAT, CABBAGE, FARMER]))
State(leftBank=Bank(members=[GOAT, WOLF, FARMER]), rightBank=Bank(members=[CABBAGE]))
State(leftBank=Bank(members=[GOAT]), rightBank=Bank(members=[CABBAGE, WOLF, FARMER]))
State(leftBank=Bank(members=[GOAT, FARMER]), rightBank=Bank(members=[CABBAGE, WOLF]))
State(leftBank=Bank(members=[]), rightBank=Bank(members=[GOAT, CABBAGE, WOLF, FARMER]))

Answer 1

Commentry

So, this is not working code. I don't consider code to be working if needs pre-processing, and the pre-processor is not shipped as part of the standard toolchain.

This code is nearly useless to anyone unless they have lambok.

If I pull the code in to Eclipse, or any other standard tools, it is full of compiler errors, missing methods, broken annotations, etc.

As such the program is broken.

I understand that it works for you, and that is about the only reason I am not voting to close

I have created a Meta question to this effect.....

Review - Everything except the App class.

Apart from the App class, there is only one place where Java8 systems are used:

public boolean isFeasible() {
    return members.stream().allMatch((m) -> m.isSafe(members));
}

In this case, the code is quite clean and unambiguous. The only slight hesitation I have is the nested call to members... you are streaming the members, and for each member you call isSafe(members). I cannot think of a better way to do that, or even if it is wrong... but it is just a little odd. Maybe it will grow on me. It is too early to say whether it violates a 'best practice'. I can't imagine it can go wrong, as long as the isSafe call does not modify the contents of the members, then it is fine. I think that is my concern... you are 'leaking' access to the members Collection while simultaneously streaming it.

As for the rest of the code, it does indeed appear clean, and uncluttered. Not having any of the support methods like toString, hashCode, etc. means that there is less code to review, but that is a big concern because it is precisely in those sorts of methods where things can go wrong. Does the equals() method produce the right results? If it does not, it will be disastrous.

Do we have to review the Annotations?

App class

I dislike disconnected recursion. You have a complicated recursive call:

main() calls calculateGraph()
  calculateGraph() calls calculateChildren()
    calculateChildren() calls process()
      process() calls calculateGraph()   ( ... inside a lambda ...)

This disconnect makes the recursion really hard to follow. Recursive methods should be easy to see, clear, and uncomplicated.

This is not.

You use the class ImmutableList. I presume this is the Guava implementation.

In your method:

private static Set<State> getSoltutionPath(Action<State> leaf) {
    final ImmutableSet.Builder<State> lb = ImmutableSet.builder();
    while (leaf != null) {
        lb.add(leaf.data());
        leaf = leaf.previous();
    }
    return lb.build();
}

you take an ordered structure of data and load it in to a Set. This relies on the internals of Guava. You use the result of this method to populate the ordered data in your output. at no point though, is Set member order guaranteed. If you are using the properties of a specific Set implementation for any reason, then you should ensure that you return the right implementation type/subtype.

In this case, you should be returning ImmutableSet<State> and not Set<State>

Additionally, in the main() method, you take a 'copy of' the Set, except the copy is a List<State> instead of a Set<State>. This is because you need to do a backward iteration on the results.

    final List<State> solution = ImmutableList.copyOf(getSoltutionPath(finalState));
    final ListIterator<State> solIter = solution.listIterator(solution.size());
    while (solIter.hasPrevious()) {
        System.out.println(solIter.previous());
    }

The meaning and structure of your data as it passes through these different layers of obfuscation are completely lost. The fact that the order is significant is only apparent when you work backwards from the end... and understand that you need to loop backwards through this data to get the right-ordered report... then, you need a List to do that (for the ListIterator), and from that you realize that the (badly named) copyof method converts a Set to a List, and (magically, because the signatures do not tell you) despite being a Set, it actually has a pre-defined order (which Sets normally don't have), and that defined order is the result of a bottom-up traversal of a tree.

Just saying that is confusing. There has to be a better way.

Conclusion....

The Java8 parts of your code appear fine, but they are completely lost in the fog that comes up from needing to understand the lambok system, and the poor use of collections that are worsened by the use of inappropriate classes from Guava.

At a personal level, this was not much fun to review. Not enough background information was available. The use of Guava was undocumented. The lambok system is kludgey, and unfriendly for reviewers. Expecting a reviewer to learn an esoteric system to do a decent review is 'not cool'. If the meta question referenced above results in saying that questions like this are 'on topic', then I intend to ensure that they are all tagged appropriately so I can ignore them.