The Wolf, Goat and Cabbage Game

Everybody knows this river crossing puzzle solving game. I was playing a river crossing game in my cellphone and decided to try to implement every single game mode this app has.

In case by any chance someone doesn't know what this popular river crossing puzzle is about, here's an explanation:


A man once had to travel with a wolf, a goat and a cabbage. He had to
take good care of them, since the wolf would like to taste a.piece of
goat if he would get the chance, while the goat appeared to long for a
tasty cabbage. After some traveling, he suddenly stood before a river.
This river could only be crossed using the small boat laying nearby at
a shore. The boat was only good enough to take himself and one of his
loads across the river. The other two subjects/objects he had to leave
on their own. How must the man row across the river back and forth, to
take himself as well as his luggage safe to the other side of the
river, without having one eating another?

I think it's a good exercise because it has been a very long time since I studied AI and problem solving algorithms and I feel like my mind is getting more stupid over time.

Since I am implementing different river crossing games I made a RiverCrossingFactory and a RiverCrossingGame interface. There's not much to it so I am just going to show the code related to the Wolf, Goat and Cabbage game, which is the WolfGoatCabbageGame class.

I decided to represent the wolf, goat and cabbage, as well as the farmer, in just an enum Element. I didn't think something more complex was needed.

Then I have a Bank class which encapsulates one bank and it contains a list of elements. You can move an element from one bank to the other, see if the bank has an element and check if two banks contain the same elements.

The last class is the State class which has two banks, you can also compare two states and check if this state is permitted or if it is final.

The game class has the implemented `play(

Sets as significant states

You should think about the problem solving process in the whole. Currently the algorithm is ruling the structure. Some examples...

Here you explicitly encode the final state as an expression:

boolean isFinal = bank.isDestination() && bank.has(Element.FARMER) && bank.has(Element.WOLF) && bank.has(Element.GOAT) && bank.has(Element.CABBAGE)

You should consider to encode this by comparing sets:

private static final Set FINAL_STATE = new HashSet<>();

FINAL_STATE.add(Element.WOLF);
FINAL_STATE.add(Element.CABBAGE);
FINAL_STATE.add(Element.GOAT);

boolean isFinal = bank.isDestination() && bank.getElements().equals(FINAL_STATE)

Other significant states are not permitted states:

private static final Set> NOT_PERMITTED_STATES = new HashSet<>();

So you can ask for permission after simulating a state:

public boolean isPermittedState(Set state) {
    return !NOT_PERMITTED_STATES.contains(state);
}

Represent a simulation

You should mention "What happens if" in your code explicitly as a simulation.

...
if (isPermittedState(bank.simulateStateIf(elementsRemoved, elementsAdded))) {
    ...
}
...

Currently you are copying Bank objects several times at different places for your simulation and to avoid side effects (e.g. State, solve()-method). Instantiate Bank-objects once and never copy them. Use Sets to represent state instead. Always make defensive copies of the Sets.

Omit Element.FARMER

You also see that I omitted Element.FARMER in FINAL_STATE as this element is not an element like the others.

You see the special nature from the Element.FARMER in the take()-method and the drop()-method which is leading to special cases.

Introduce a boat

A good way modelling the problem is to represent real involved objects. In this case you are at least missing a boat.

public class Boat {
    private Set elements;
    ...
    public void deleteCargo(Element element) ...
    public void loadCargo(Element element) ...
}

The more actors you identify that are involved in the problem the clearer your code will be.

Notice: After all the boat can also be the Farmer to make clear that someone is looking after the cargo elements. But The Farmer itself should not be part of the other elements and be modelled another way.

Separate concerns

You should have a separate generic path finding algorithm:

• permutate

• eleminate not permitted steps

• eliminate already tried steps

• choose one step if available

• register step as tried

• check if final state is reached, yes -> done, no -> 1.

• return to previous step if no further step is available

• if no previous step is available problem is not solvable

The steps are not necessarily in order. It relates to your recursive call of the solve()-method the stateExists()-method and the addState()-method. I'd expect following structure of the State-Class to use in the generic path finding algorithm:

public class State {

    private Bank currentBank;

    private Set elementsToTransport;

    public int hashCode() {
        return currentBank.hashCode() * elementsToTransport.hashCode();
    }

    public boolean equals(Object object) {

        boolean equals = false;

        if (object instanceof State) {
            State that = (State) object;
            equals = this.currentBank.equals(that.currentBank) && this.elementsToTransport.equals(that.elementsToTransport);
        }

        return equals;
    }

    public Bank getCurrentBank() {
        return currentBank;
    }

    public Set getElementsToRemove() {
        return elementsToRemove;
    }

}

It's a value object with hashCode and equals overriden. With this object you are able to simulate situation of a Bank as mentioned previously (isPermitted()-method).

You also print out intermediate information while processing the solve()-method. Try to separate this concern.

What I really mean here is not that the representation you chose, it's more separating algorithms. You mixed a general path finding algorithm with a concrete problem solving algorithm and displaying information. Break the whole problem in smaller pieces and separate concerns.

I suggest to make the path finding algorithm generic and introduce the listener pattern to separate the display of information during path finding.

Miscellaneous

Try to avoid multiple return statement in a method. Multiple return statements (continue and break as well) will hinder you to apply refactorings like "extract method".

Do not compare Banks to each other and do not provide a copy constructor. This is not natural. Try to preserve object identity for "business" objects. The North Sea is not the Baltic Sea even if you cannot see the difference. And you will never try to make a copy of one of them. Try to develop in an OO way.

You have to introduce a variable "currentBank" and an algorithm that switches between the two Banks as a transport simulation.

Finally you are transporting the el

StackExchange Code Review Q#118516, answer score: 4