Question

 Process Synchronization

 A farmer wants to cross a river with a chicken, some grain, and a fox. His boat can only carry two items at a time.

 The fox will eat the chicken if left alone.

 The chicken will eat the grain if left without the farmer.

 Build the application to synchronize the crossing so all three items arrive across the river.

Answer 1

Take chicken to side 2
Take grain to side 2, but bring the chicken to side 1.
Take the fox to side 2
Take the chicken to side 2
FIN

File Name State.JAVA

package com.atlasrider.ffcg;
	/**
	* Created by billdwyer on 4/2/15.
	*/
	public class State {
	public int Farmer;
	public int Fox;
	public int Chicken;
	public int Grain;
	public State(int farmer, int fox, int chicken, int grain) {
	Farmer = farmer;
	Fox = fox;
	Chicken = chicken;
	Grain = grain;
	}
	public State(String state) {
	Farmer = Character.getNumericValue(state.toCharArray()[0]);
	Fox = Character.getNumericValue(state.toCharArray()[1]);
	Chicken = Character.getNumericValue(state.toCharArray()[2]);
	Grain = Character.getNumericValue(state.toCharArray()[3]);
	}
	public boolean isValid() {
	// Only 2 Objects can be in the boat at once
	int boatCount = 0;
	boatCount = ((Farmer == 1) ? 1 : 0)
	+ ((Fox == 1) ? 1 : 0)
	+ ((Chicken == 1) ? 1 : 0)
	+ ((Grain == 1) ? 1 : 0);
	if(boatCount > 2) return false;
	// Chicken and fox can't be left alone
	if(Chicken == Fox && Chicken != Farmer) return false;
	// Chicken and grain can't be left alone
	if(Chicken == Grain && Chicken != Farmer) return false;
	// If anything is in the boat, the farmer must be there
	if((Grain == 1 || Fox == 1 || Chicken == 1) && Farmer != 1) return false;
	// Default to true
	return true;
	}
	public boolean isValidNextStep(State nextState) {
	// Objects can only move one spot at a time
	if(Math.abs(Farmer - nextState.Farmer) > 1
	|| Math.abs(Fox - nextState.Fox) > 1
	|| Math.abs(Chicken - nextState.Chicken) > 1
	|| Math.abs(Grain - nextState.Grain) > 1)
	return false;
	// Only the farmer can move the objects.
	if(Fox != nextState.Fox && (Farmer != Fox || nextState.Farmer != nextState.Fox)) return false;
	if(Chicken != nextState.Chicken && (Farmer != Chicken || nextState.Farmer != nextState.Chicken)) return false;
	if(Grain != nextState.Grain && (Farmer != Grain || nextState.Farmer != nextState.Grain)) return false;
	return true;
	}
	public String beingMoved(State nextState) {
	if(Fox != nextState.Fox) return "Fox";
	if(Chicken != nextState.Chicken) return "Chicken";
	if(Grain != nextState.Grain) return "Grain";
	return "";
	}
	public String toString() {
	return Integer.toString(Farmer)
	+ Integer.toString(Fox)
	+ Integer.toString(Chicken)
	+ Integer.toString(Grain);
	}
	public void print() {
	String line = " %s | %s | %s \n";
	String blank = " ";
	System.out.printf(line, blank, blank, blank);
	printLine(line, "Farmer", Farmer);
	printLine(line, "Fox", Fox);
	printLine(line, "Chicken", Chicken);
	printLine(line, "Grain", Grain);
	System.out.printf(line, blank, blank, blank);
	System.out.printf("--------------------------------------\n");
	}
	private void printLine(String line, String value, int location) {
	String blank = " ";
	switch(location) {
	case 0:
	System.out.printf(line, String.format("%-8s", value), blank, blank);
	break;
	case 1:
	System.out.printf(line, blank, String.format("%8s", value), blank);
	break;
	case 2:
	System.out.printf(line, blank, blank, String.format("%8s", value));
	break;
	}
	}
	} AI.java package com.atlasrider.ffcg; import org.graphstream.algorithm.APSP; import org.graphstream.graph.Edge; import org.graphstream.graph.Graph; import org.graphstream.graph.Node; import org.graphstream.graph.Path; import org.graphstream.graph.implementations.SingleGraph; import java.util.HashMap; import java.util.Map; import java.util.Scanner; /* ! ! ! ! ! ! ! ! LEFT SIDE ! RIVER ! RIGHT SIDE ! ! ! ! ! ! ! ! 0 1 2 */ // FARMER, FOX, CHICKEN, GRAIN public class AI { private State _startState; private State _endState; private int _numberOfStates = 3; private int _numberOfObjects = 4; private int _numberOfPossibilities = (int)Math.pow(_numberOfStates, _numberOfObjects); public AI() { init(); } public void run() { Graph graph = generateDecisionTree(); Path solution = getSolution(graph); System.out.println("Solution: " + solution.toString()); for(Node node : solution.getNodeSet()) { new State(node.getId()).print(); //new Scanner(System.in).next(); } displayGraph(graph); } private Graph generateDecisionTree() { Graph graph = new SingleGraph("Farmer, Fo, Chicken and the Grain"); State state; int validStates = 0; // Iterate through all posibilities for(int i=0;i<_numberOfPossibilities;i++) { state = new State(addLeadingZeros(Integer.toString(i, _numberOfStates))); //System.out.println(state.toString()); // Only deal with valid states if(state.isValid()) { validStates++; // Add node Node node = graph.getNode(state.toString()); if(node == null) node = graph.addNode(state.toString()); State nextStep; Node nextNode; // Iterate through possible next steps for(int j=0;j<_numberOfPossibilities;j++) { nextStep = new State(addLeadingZeros(Integer.toString(j, _numberOfStates))); // Only deal with valid next steps if(nextStep.isValid() && state.isValidNextStep(nextStep)) { // Add node nextNode = graph.getNode(nextStep.toString()); if(nextNode == null) nextNode = graph.addNode(nextStep.toString()); // Add Edge if(!node.hasEdgeBetween(nextNode)) { Edge edge = graph.addEdge(state.toString() + "->" + nextStep.toString(), node, nextNode); edge.addAttribute("ui.label", state.beingMoved(nextStep)); } } } } } System.out.println("Number of possible states: " + _numberOfPossibilities); System.out.println("Number of valid states: " + validStates); return graph; } private Path getSolution(Graph graph) { APSP apsp = new APSP(); apsp.init(graph); // registering apsp as a sink for the graph apsp.setDirected(false); // undirected graph //apsp.setWeightAttributeName("weight"); // ensure that the attribute name used is "weight" apsp.compute(); // the method that actually computes shortest paths APSP.APSPInfo info = graph.getNode(_startState.toString()).getAttribute(APSP.APSPInfo.ATTRIBUTE_NAME); return info.getShortestPathTo(_endState.toString()); } private void displayGraph(Graph graph) { for (Node node : graph) { node.addAttribute("ui.label", node.getId()); } graph.setStrict(false); graph.setAutoCreate(true); graph.display(); } private String addLeadingZeros(String number) { while(number.length() < 4) number = "0" + number; return number; } private void init() { _startState = new State(0, 0, 0, 0); _endState = new State(2, 2, 2, 2); } }