Solving Farmer-Wolf-Goat-Cabbage riddle with Groovy/Java

The Riddle - Farmer Wolf Goat Cabbage

A farmer is on the west bank of a river with a wolf, a goat and a cabbage in his care. Without his presence the wolf would eat the goat or the goat would eat the cabbage. The wolf is not interested in the cabbage. The farmer wishes to bring his three charges across the river. However the boat available to him can only carry one of the wolf, goat and cabbage besides himself. The puzzle is: is there a sequence of river crossings so that the farmer can transfer himself and the other three all intact to the east bank?

The Solution

It is a task that given an initial state, a final state, and a set of rules, one will start from the initial state and try to reach to the final state by passing through some intermediate states. Each move will transform from one state to the other, and there might be multiple valid moves from a given state. Such a collection of interconnected states can be represented by State Space Graph.
Let's use 'f', 'c', 'g', 'w' to denote the farmer, the cabbage, the goat, and the wolf, and use '|' to separate the river where left of the '|' denotes west bank and right of the '|' denotes east bank. Initially, they are all at the west bank of the river, which is represented as 'fcgw |' as shown below. We can solve the riddle by figuring out what the possible and valid moves are, using either Breadth-First Search or Depth-First Search, on a state space graph shown below

 

Depth First Search

I use DFS to find the first possible solution to the riddle, where it looks like this

or with a possibility of backtracking like this

Breadth First Search

I can build a complete state space graph using BFS, excluding the red states as shown below

Sample Source Code

Implemented in a mix of Groovy and Java, where Java is mainly used for the POJOs, the sample source code, including the unit test, demonstrates how to build a complete state space graph (which is also a directed graph) and how to find all possible solutions based on the state space graph.
DirectedGraph.java

import java.util.*;

public class DirectedGraph<T> implements Iterable<T> {

    // key is a Node, value is a set of Nodes connected by outgoing edges from the key
    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

    public boolean addNode(T node) {
        if (graph.containsKey(node)) {
            return false;
        }

        graph.put(node, new HashSet<T>());
        return true;
    }

    public void addNodes(Collection<T> nodes) {
        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        // Add the edge by adding the dest node into the outgoing edges
        graph.get(src).add(dest);
    }

    public void removeEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        graph.get(src).remove(dest);
    }

    public boolean edgeExists(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        return graph.get(src).contains(dest);
    }

    public Set<T> edgesFrom(T node) {
        // Check that the node exists.
        Set<T> edges = graph.get(node);
        if (edges == null)
            throw new NoSuchElementException("Source node does not exist.");

        return Collections.unmodifiableSet(edges);
    }

    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }

    public int size() {
        return graph.size();
    }

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

    private void validateSourceAndDestinationNodes(T src, T dest) {
        // Confirm both endpoints exist
        if (!graph.containsKey(src) || !graph.containsKey(dest))
            throw new NoSuchElementException("Both nodes must be in the graph.");
    }

}

BoatLocation.java

public enum BoatLocation {
    WestBank, EastBank
}

RiverRole.java, implemented Comparable interface in order to be used in a SortedSet

public class RiverRole implements Comparable<RiverRole> {

    public final String name;
    public final boolean canSailTheBoat;

    public RiverRole(String name, boolean canSailTheBoat) {
        this.name = name;
        this.canSailTheBoat = canSailTheBoat;
    }

    @Override
    public int compareTo(RiverRole o) {
        return this.name.compareTo(o.name);
    }

    @Override
    public String toString() {
        return name;
    }
}

RiverState.java

import java.util.Collection;
import java.util.SortedSet;
import java.util.TreeSet;

public class RiverState {

    private SortedSet<RiverRole> westBank;
    private SortedSet<RiverRole> eastBank;
    private BoatLocation boatLocation;

    public RiverState(Collection<RiverRole> westBank, Collection<RiverRole> eastBank, BoatLocation boatLocation) {
        this.westBank = new TreeSet<RiverRole>(westBank);
        this.eastBank = new TreeSet<RiverRole>(eastBank);
        this.boatLocation = boatLocation;
    }

    public SortedSet<RiverRole> getWestBank() {
        return new TreeSet<RiverRole>(westBank);
    }

    public SortedSet<RiverRole> getEastBank() {
        return new TreeSet<RiverRole>(eastBank);
    }

    public BoatLocation getBoatLocation() {
        return boatLocation;
    }

    @Override
    public String toString() {
        return "State{westBank=" + westBank + ", eastBank=" + eastBank + ", boatLocation=" + boatLocation + "}";
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof RiverState)) return false;

        RiverState riverState = (RiverState) o;

        return eastBank.equals(riverState.eastBank) &&
               westBank.equals(riverState.westBank) &&
               boatLocation.equals(riverState.boatLocation);
    }

    public int hashCode() {
        int result;
        result = westBank.hashCode();
        result = 31 * result + eastBank.hashCode();
        result = 31 * result + boatLocation.hashCode();
        return result;
    }
}

FarmerWolfGoatRiddle.groovy

import graph.DirectedGraph
import org.codehaus.groovy.runtime.MethodClosure

import static fun.rivercrossing.BoatLocation.EastBank
import static fun.rivercrossing.BoatLocation.WestBank

public class FarmerWolfGoatRiddle {

    /*  Farmer Wolf Goat Puzzle
        A farmer is on the east bank of a river with a wolf, goat and cabbage in his care. Without his presence the wolf would eat
        the goat or the goat would eat the cabbage. The wolf is not interested in the cabbage. The farmer wishes to bring his three
        charges across the river. However the boat available to him can only carry one of the wolf, goat and cabbage besides
        himself. The puzzle is: is there a sequence of river crossings so that the farmer can transfer himself and the other three all
        intact to the west bank?
    */

    RiverRole farmer = new RiverRole("farmer", true);
    RiverRole wolf = new RiverRole("wolf", false);
    RiverRole goat = new RiverRole("goat", false);
    RiverRole cabbage = new RiverRole("cabbage", false);

    RiverState initialState = new RiverState([farmer, wolf, goat, cabbage], [], BoatLocation.WestBank)
    RiverState finalState = new RiverState([], [farmer, wolf, goat, cabbage], EastBank)

    Closure<Boolean> areRolesHarmonisedOnRiverBank = { Collection<RiverRole> roles ->
        // describe clearly what the rules are
        if (!roles.contains(farmer)) {
            if (roles.contains(wolf) && roles.contains(goat)) return false
            if (roles.contains(goat) && roles.contains(cabbage)) return false
        }
        return true
    }


    public Collection<Deque<RiverState>> findAllPossibleSolutions() {
        DirectedGraph<RiverState> graph = buildCompleteGraph()

        Collection<Deque<RiverState>> solutions = []
        Deque<RiverState> currentSolution = new ArrayDeque<RiverState>()

        explore(graph, initialState, currentSolution, solutions)

        return solutions
    }

    // using Depth First Search (Stack Implementation) to identify a solution
    private void explore(DirectedGraph<RiverState> graph, RiverState currentNode, Deque<RiverState> currentSolution, Collection<Deque<RiverState>> solutions) {
        currentSolution.push(currentNode)
        graph.edgesFrom(currentNode).each { RiverState node ->
            if (node == finalState) {
                // add the current solution, including the final node, to the solutions
                currentSolution.push(node)
                solutions.add(new ArrayDeque<RiverState>(currentSolution))
                currentSolution.pop()
            } else {
                // recursively explore
                explore(graph, node, currentSolution, solutions)
            }
        }
        currentSolution.pop()
    }

    // using Breath First Search to build the complete graph
    private DirectedGraph<RiverState> buildCompleteGraph() {
        DirectedGraph<RiverState> graph = new DirectedGraph<RiverState>()
        graph.addNode(initialState)

        Set<RiverState> visitedNodes = new HashSet<RiverState>()

        // use a queue to keep the states to be visited in sequence
        Deque<RiverState> currentStates = new ArrayDeque<RiverState>()
        currentStates.add(initialState)

        while (!currentStates.isEmpty()) {
            if (currentStates.peek() != finalState) {
                def currentState = currentStates.removeFirst()
                if (!visitedNodes.contains(currentState)) {
                    visitedNodes.add(currentState)
                    def possibleStates = findNextPossibleStates(currentState)
                    def validStates = possibleStates.findAll { RiverState possibleState ->
                        // matched state should not be one of the visited states, and it should pass the validations
                        return !visitedNodes.contains(possibleState) && passRuleValidations(possibleState)
                    }
                    // add successors and edges
                    graph.addNodes(validStates)
                    validStates.each { graph.addEdge(currentState, it) }

                    // add to current states so that we can visit them next
                    currentStates.addAll(validStates)
                }
            } else {
                currentStates.removeFirst() // remove the final state from the currentStates queue
            }
        }

        return graph
    }

    private boolean passRuleValidations(RiverState state) {
        return areRolesHarmonisedOnRiverBank(state.eastBank) && areRolesHarmonisedOnRiverBank(state.westBank)
    }

    private List<RiverState> findNextPossibleStates(RiverState currentState) {
        // from the last visited state, find out who can sail the boat, and where is the sailor
        List<RiverState> possibleStates = []

        transitFrom(currentState, possibleStates)

        return possibleStates
    }

    private void transitFrom(RiverState currentState, List<RiverState> possibleStates) {
        // check where the boat is
        BoatLocation boatOrigin = currentState.boatLocation
        BoatLocation boatDestination

        // we use method closure to get a copy of west bank or east bank roles
        MethodClosure origin, destination

        // multiple assignments
        (origin, destination, boatDestination) = boatOrigin == WestBank ?
            [currentState.&getWestBank, currentState.&getEastBank, EastBank] :
            [currentState.&getEastBank, currentState.&getWestBank, WestBank]

        def possibleSailors = origin().findAll { RiverRole role -> role.canSailTheBoat }

        possibleSailors?.each { RiverRole sailor ->
            // pick 0 passengers onto the boat
            Collection<RiverRole> onBoat = [sailor]
            possibleStates.add(createNextPossibleState(origin, destination, onBoat, boatDestination))

            Collection<RiverRole> possiblePassengers = origin() as Collection<RiverRole>
            possiblePassengers.remove(sailor)

            // pick 1 passenger onto the boat
            possiblePassengers.each { RiverRole passenger ->
                onBoat = [passenger, sailor]
                possibleStates.add(createNextPossibleState(origin, destination, onBoat, boatDestination))
            }
        }
    }

    private RiverState createNextPossibleState(MethodClosure origin, MethodClosure destination, Collection<RiverRole> onBoat, BoatLocation boatDestination) {
        Collection<RiverRole> newDestination = destination() as Collection<RiverRole>
        Collection<RiverRole> newOrigin = origin() as Collection<RiverRole>

        // boat transits from origin to destination
        newOrigin.removeAll(onBoat)
        newDestination.addAll(onBoat)

        return boatDestination == WestBank ? new RiverState(newDestination, newOrigin, boatDestination) : new RiverState(newOrigin, newDestination, boatDestination)
    }


}

FarmerWolfGoatRiddleTest.groovy

import org.junit.Test

import static fun.rivercrossing.BoatLocation.EastBank
import static fun.rivercrossing.BoatLocation.WestBank


class FarmerWolfGoatRiddleTest {

    FarmerWolfGoatRiddle riddle = new FarmerWolfGoatRiddle()

    @Test
    public void findAllPossibleSolutions() {
        def solutions = riddle.findAllPossibleSolutions()
        // the ordering of solutions will be random
        assert solutions.size() == 2
        assert solutions[0].size() == 8
        assert solutions[1].size() == 8

        def assertAllSolutions = { Deque<RiverState> solution1, Deque<RiverState> solution2 ->
            assertFirstSolution(solution1)
            assertSecondSolution(solution2)
        }

        // assert with the correct expectations regardless of which is the first solution
        if (solutions[0].contains(new RiverState([riddle.wolf], [riddle.farmer, riddle.goat, riddle.cabbage], EastBank))) {
            assertAllSolutions(solutions[0], solutions[1])
        } else {
            assertAllSolutions(solutions[1], solutions[0])
        }
    }

    private void assertFirstSolution(Deque<RiverState> solution) {
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], [], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf, riddle.cabbage], [riddle.farmer, riddle.goat], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.cabbage], [riddle.goat], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf], [riddle.farmer, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat], [riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([riddle.goat], [riddle.farmer, riddle.wolf, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.goat], [riddle.wolf, riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([], [riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == null
    }

    private void assertSecondSolution(Deque<RiverState> solution) {
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], [], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf, riddle.cabbage], [riddle.farmer, riddle.goat], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.cabbage], [riddle.goat], WestBank)
        assert solution.poll() == new RiverState([riddle.cabbage], [riddle.farmer, riddle.goat, riddle.wolf], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.cabbage, riddle.goat], [riddle.wolf], WestBank)
        assert solution.poll() == new RiverState([riddle.goat], [riddle.farmer, riddle.wolf, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.goat], [riddle.wolf, riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([], [riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == null
    }
}

Sorting objects with one-way dependency using Topological Sort with Directed Graphs

Suppose there are a bunch of objects to be evaluated, each of which might depend on a number of other objects being evaluated first before it can be evaluated. The objects being depended on might depend on other objects. There is no cyclic dependency that object A depends on object B, and object B depends on object C, and object C depends on object A.

To solve this problem, we want to sort these objects such that when traversing through these objects, they should be ready for evaluation and their dependencies, if applicable, should have been evaluated. The sorting algorithm and data structure that are applicable for this problem is Topological Sort with Directed Graphs.

If the edges in a graph have a direction, the graph is called a directed graph, as shown above. The arrows in the figure show the direction of the edges. We also include two vertices here to represent isolated objects that don't depend on other objects.

The arrows in the figure represent evaluation direction. For example, to evaluate E, we must first evaluate A and B. To evaluate H, we might want a sorted collection like this:

ADBECFDGH or ADGBECFH

There are many other possible ordering, depending on the approach you take to implement the topological sort.

DirectedGraph.java

import java.util.*;

public class DirectedGraph<T> implements Iterable<T> {

    // key is a Node, value is a set of Nodes connected by outgoing edges from the key
    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

    public boolean addNode(T node) {
        if (graph.containsKey(node)) {
            return false;
        }

        graph.put(node, new HashSet<T>());
        return true;
    }

    public void addNodes(Collection<T> nodes) {
        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        // Add the edge by adding the dest node into the outgoing edges
        graph.get(src).add(dest);
    }

    public void removeEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        graph.get(src).remove(dest);
    }

    public boolean edgeExists(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        return graph.get(src).contains(dest);
    }

    public Set<T> edgesFrom(T node) {
        // Check that the node exists.
        Set<T> edges = graph.get(node);
        if (edges == null)
            throw new NoSuchElementException("Source node does not exist.");

        return Collections.unmodifiableSet(edges);
    }

    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }

    public int size() {
        return graph.size();
    }

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

    private void validateSourceAndDestinationNodes(T src, T dest) {
        // Confirm both endpoints exist
        if (!graph.containsKey(src) || !graph.containsKey(dest))
            throw new NoSuchElementException("Both nodes must be in the graph.");
    }

}

TolopogicalSort.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class TopologicalSort {

    public static <T> List<T> sort(DirectedGraph<T> graph) {
        DirectedGraph<T> reversedGraph = reverseGraph(graph);

        List<T> result = new ArrayList<T>();
        Set<T> visited = new HashSet<T>();

        /* We'll also maintain a third set consisting of all nodes that have
         * been fully expanded.  If the graph contains a cycle, then we can
         * detect this by noting that a node has been explored but not fully
         * expanded.
         */
        Set<T> expanded = new HashSet<T>();

        // Fire off a Depth-First Search from each node in the graph
        for (T node : reversedGraph)
            explore(node, reversedGraph, result, visited, expanded);

        return result;
    }


    /**
     * Recursively performs a Depth-First Search from the specified node, marking all nodes
     * encountered by the search.
     *
     * @param node     The node to begin the search from.
     * @param graph    The graph in which to perform the search.
     * @param result   A list holding the topological sort of the graph.
     * @param visited  A set of nodes that have already been visited.
     * @param expanded A set of nodes that have been fully expanded.
     */
    private static <T> void explore(T node, DirectedGraph<T> graph, List<T> result, Set<T> visited, Set<T> expanded) {
        if (visited.contains(node)) {
            // if this node has already been expanded, then it's already been assigned a
            // position in the final topological sort and we don't need to explore it again.
            if (expanded.contains(node)) return;

            // if it hasn't been expanded, it means that we've just found a node that is currently being explored,
            // and therefore is part of a cycle.  In that case, we should report an error.
            throw new IllegalArgumentException("A cycle was detected within the Graph when exploring node " + node.toString());
        }

        visited.add(node);

        // recursively explore all predecessors of this node
        for (T predecessor : graph.edgesFrom(node))
            explore(predecessor, graph, result, visited, expanded);

        result.add(node);
        expanded.add(node);
    }

    private static <T> DirectedGraph<T> reverseGraph(DirectedGraph<T> graph) {
        DirectedGraph<T> result = new DirectedGraph<T>();

        // Add all the nodes from the original graph
        for (T node : graph) {
            result.addNode(node);
        }

        // Scan over all the edges in the graph, adding their reverse to the reverse graph.
        for (T node : graph) {
            for (T endpoint : graph.edgesFrom(node)) {
                result.addEdge(endpoint, node);
            }
        }

        return result;
    }

}

Below demonstrate the setup of the directed graph and will print out the sorted result.

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph()
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");
        graph.addNode("G");
        graph.addNode("H");
        graph.addNode("I");
        graph.addNode("J");

        graph.addEdge("A", "D");
        graph.addEdge("A", "E");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "G");
        graph.addEdge("E", "H");
        graph.addEdge("F", "H");
        graph.addEdge("G", "H");

        List sorted = TopologicalSort.sort(graph)

        System.out.println(sorted)
    }