The Wolf, Goat and Cabbage Game

Question

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() method which calls solve(). This one calls himself recursively. There are two methods, stateExists() and addState(), to control the visited states. I would have liked to have moved these two into the State class as static methods but since State is a nested class of the game class I couldn't do it.

The steps of the solution are simply stored in a List<String>.

So here it is:

public class WolfGoatCabbageGame implements RiverCrossingGame {
    private enum Element { FARMER, WOLF, GOAT, CABBAGE };
    private Bank westBank;
    private Bank eastBank;
    private static Vector<State> states; // visited states
    private List<String> steps; // steps to solve the puzzle

    class Bank {
        private String name;
        private Vector<Element> elements; // elements in the bank
        private boolean isDestination; // flag: is this the bank where we want to cross?

        public Bank(String name, boolean isDestination) {
            this.name = name;
            elements = new Vector<Element>();
            this.isDestination = isDestination;
        }

        public Bank(String name, Element[] elements, boolean isDestination) {
            this.name = name;
            this.elements = new Vector<Element>(Arrays.asList(elements));
            this.isDestination = isDestination;
        }

        // Copy constructor to avoid copying references to the vector of elements
        @SuppressWarnings("unchecked")
        public Bank(Bank src) {
            name = src.name;
            elements = (Vector<Element>) src.elements.clone();
            isDestination = src.isDestination;
        }

        // moves the element to the bank dst
        public boolean move(Element element, Bank dst) {
            // I did this just for debugging
            if (!has(Element.FARMER) || !has(element) || dst.has(element))
                return false;

            // removes the element from the bank and stores it in object (simulation of taking an element and taking it up the boat)
            Element object = take(element);

            // again debugging. It's never going to be null during the game
            if (object == null)
                return false;

            // adds the object to the bank dst (simulation of taking an element off the boat and dropping it on the bank)
            dst.drop(object);

            return true;
        }

        // checks if two banks have the same set of elements
        public boolean compare(Bank bank) {
            if (bank.elements.size() != elements.size())
                return false;

            for (Element element : elements)
                if (!bank.has(element))
                    return false;

            return true;
        }

        // checks if this bank contains the element
        public boolean has(Element element) {
            for (Element elt : elements)
                if (elt == element)
                    return true;

            return false;
        }

        public String getName() {
            return name;
        }

        public int numberOfElements() {
            return elements.size();
        }

        public Vector<Element> getElements() {
            return elements;
        }

        public boolean isDestination() {
            return isDestination;
        }

        public String toString() {
            String bankString = this.name + " bank: ";
            for (Element element : elements)
                bankString += element + ", ";

            return bankString.substring(0, bankString.length() - 2);
        }

        // takes an element off the bank and returns it. If it's different than the farmer it means the farmer has to leave this bank as well, so he's removed
        private Element take(Element element) {
            if (element == Element.FARMER) {
                for (Element e : elements) {
                    if (e == element) {
                        elements.remove(e);
                        return element;
                    }
                }
            } else {
                Element farmer = null;
                Element eltToRemove = null;
                for (Element e : elements) {
                    if (e == Element.FARMER)
                        farmer = e;
                    else if (e == element)
                        eltToRemove = e;
                }

                if (farmer == null || eltToRemove == null)
                    return null;

                elements.remove(farmer);
                elements.remove(eltToRemove);

                return element;
            }

            return null;
        }

        // drops the element on the shore. If it's different than the farmer drops the farmer as well because he's crossed the river
        private void drop(Element element) {
            elements.add(element);

            if (element != Element.FARMER)
                elements.add(Element.FARMER);
        }
    }

    // encapsulates a state: basically a particular arrangement of the elements in both banks
    class State {
        private Bank thisBank;
        private Bank otherBank;

        public State(Bank thisBank, Bank otherBank) {
            // copy constructor used to avoid assigning references (remember the bank has a vector of elements)
            this.thisBank = new Bank(thisBank);
            this.otherBank = new Bank(otherBank);
        }

        // checks if two states are the same. It is necessary to check the order of the arguments in case the comparison needs to be swapped (this is to avoid comparing WEST with EAST and EAST with WEST when we need to compare WEST with WEST and EAST with EAST
        public boolean compare(State state) {
            if (state.thisBank.getName().equals(thisBank.getName()))
                return thisBank.compare(state.thisBank) && otherBank.compare(state.otherBank);
            else
                return thisBank.compare(state.otherBank) && otherBank.compare(state.thisBank);
        }

        // checks if the state is permitted (rules set by the game)
        public boolean isPermitted(Bank bank) {
            return !(!bank.has(Element.FARMER) && 
                    ((bank.has(Element.WOLF) && bank.has(Element.GOAT)) || (bank.has(Element.GOAT) && bank.has(Element.CABBAGE)))); 
        }

        // checks if the state is final (set by the game: all the elements are in the other bank)
        public boolean isFinal(Bank bank) {
            return bank.isDestination() && bank.has(Element.FARMER) && bank.has(Element.WOLF) && bank.has(Element.GOAT) && bank.has(Element.CABBAGE);
        }

        public String toString() {
            return westBank.toString() + "\n" + eastBank.toString();
        }
    }

    // initialize the starting bank with all 4 elements and the other one is empty
    public WolfGoatCabbageGame() {
        westBank = new Bank("WEST", new Element[]{ Element.FARMER, Element.WOLF, Element.GOAT, Element.CABBAGE }, false);
        eastBank = new Bank("EAST", true);
        states = new Vector<State>();
        steps = new ArrayList<String>();
    }

    // initial call to the game
    @SuppressWarnings("unchecked")
    @Override
    public void play() {
        State startingState = new State(westBank, eastBank);
        addState(startingState); // the initial state is added to the visited states list

        Vector<Element> elements = (Vector<Element>) westBank.getElements().clone();
        boolean solved = false;

        // move each element in the starting bank to the opposite bank
        for (Element element : elements) {
            Bank thisBank = new Bank(westBank);
            Bank otherBank = new Bank(eastBank);

            if (!thisBank.move(element, otherBank)) {
                System.out.println("ILLEGAL MOVE!\n"); // debugging
            }

            // new state after moving the element
            State state = new State(thisBank, otherBank);

            // check if the current state is permitted
            if (state.isPermitted(thisBank) && state.isPermitted(otherBank)) {
                // call the solve method with the current state and swap banks in the arguments so we start exploring solutions from the other bank
                if (!solved && solve(state, otherBank, thisBank))
                    solved = true;
                    addStep(element, thisBank, otherBank); // adds step to the list of steps for the solution
                    printSteps();
            }
        }
    }

    // current state, src is the bank where we're at and dst is the opposite one
    @SuppressWarnings("unchecked")
    private boolean solve(State state, Bank src, Bank dst) {
        // this state is now visited
        addState(state);

        // if the state is final we're done
        if (state.isFinal(src)) {
            return true;
        }

        Vector<Element> elements = (Vector<Element>) src.getElements().clone();
        // same than in the play method: we try taking each element from this bank to the other
        for (Element element : elements) {
            Bank thisBank = new Bank(src);
            Bank otherBank = new Bank(dst);

            if (!thisBank.move(element, otherBank)) {
                System.out.println("ILLEGAL MOVE!\n");
            }

            State st = new State(thisBank, otherBank);

            // if the new state is permitted and it has not already been visited, explore new solutions recursively starting from this state
            if (st.isPermitted(thisBank) && st.isPermitted(otherBank) && !stateExists(st)) {            
                if (solve(st, otherBank, thisBank)) {
                    // as the stack pops back we're adding the correct steps to the solution
                    addStep(element, thisBank, otherBank);
                    return true;
                }
            }
        }

        return false;
    }

    // adds a new state to the visited states list
    private void addState(State state) {
        states.add(state);
    }

    // checks if the state has already been visited
    private boolean stateExists(State state) {
        for (State st : states)
            if (st.compare(state))
                return true;

        return false;
    }

    private void addStep(Element element, Bank from, Bank to) {
        String step = "[" + element + "] moved from " + from.getName() + " bank to " + to.getName() + " bank \n";
        step += from + "\n" + to + "\n";

        steps.add(0, step);
    }

    public void printSteps() {
        for (String step : steps) {
            System.out.println(step);
        }
    }

}

Believe it or not, being my mind sooo rusty this took me awfully more effort than I even expected.

I would like you to point out bad practices, unnecessary logic and ways to improve this.

By the way the reason move() returns a boolean is purely for debugging while I was doing this. I think it should just be void and that inside the method different cases shouldn't be controlled because a) it's never going to get to it and b) if it does it's because the programmer is calling the method with a out-of-the-game-flow state construction. I hope you know what I mean.

I just realized the isPermitted() method can be changed so it checks both banks and I can get rid of the argument. The problem comes from a previous implementation of State where it just had one bank and I realized this was wrong. Then I tried to reuse the code and... side effects!

Another edit: I just realized I should have just probably used Set<Element> instead of Vector.

Answer 1

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<Element> 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<Set<Element>> NOT_PERMITTED_STATES = new HashSet<>();

So you can ask for permission after simulating a state:

public boolean isPermittedState(Set<Element> 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<Element> 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:

1. permutate
2. eleminate not permitted steps
3. eliminate already tried steps
4. choose one step if available
5. register step as tried
6. check if final state is reached, yes -> done, no -> 1.
7. return to previous step if no further step is available
8. 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<Element> 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<Element> 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 elements the selected valid State-Object contains in the field "elementsToTransport".