Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
4 of 6 deleted 18 characters in body

Wolves, Goats and Cabbages in Java

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 use project lombok to reduce standard Java boilerplate.

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:

@Data
@EqualsAndHashCode(of = "members")
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();
    }
}

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:

@Accessors(fluent = true)
@EqualsAndHashCode
@ToString
@Getter
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 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));
    }
}

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);

}

@Accessors(fluent = true, chain = false)
@Data()
@EqualsAndHashCode(of = "data")
@ToString(of = {"data"})
public class ActionImpl<T> implements Action<T> {

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

}

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]))