Replace with the 256 element transition table with a 40 element transition table
ID: 3833686 • Letter: R
Question
Replace with the 256 element transition table with a 40 element transition table. The 40 element transition table's elements are not integers. The elements are triples {source state, destination state, transition type}
The transition type is Bad or Good.
Look at the transition table. B is bad, G is good, and I is impossible. The new transition table will contain no impossible transitions.
below is the fucntions that need modification.
source.cpp
#include <iostream>
#include <string>
#include "cargo.h"
#include "river.h"
using namespace std;
int main()
{
River river;
river.show();
do
{
int cargo = Cargo::read();
river.cross(cargo);
river.show();
}
while(!river.stop());
system("pause");
return 0;
}
River.cpp
#include "River.h"
River::River(void)
{
for (int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
_far_side[pos] = false;
}
void River::show(void)
{
for(int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
if(_far_side[pos])
cout << "- | " << Cargo::cargoToChar(pos) << endl;
else
cout << Cargo::cargoToChar(pos) << " | -" << endl;
cout << endl;
}
void River::cross(int cargo)
{
copy(_far_side, _near_side);
_far_side[Cargo::SHOWMAN] = !_near_side[Cargo::SHOWMAN];
_far_side[cargo] = !_near_side[cargo];
if(!goodCrossing(_near_side, _far_side))
copy(_near_side, _far_side);
}
void River::copy(bool source[], bool sink[])
{
for(int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
sink[pos] = source[pos];
}
int River::state(bool river[])
{
int _state = 0;
for(int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
_state = _state + river[pos] * (int)pow(2, pos);
return _state;
}
bool River::goodCrossing(bool this_side[], bool that_side[])
{
static const int I = 0;
static const int B = 1;
static const int G = 2;
static const int n_states = 16;
static int crossing_table[][n_states] =
{{I,I,I,I,B,B,G,I,I,I,I,I,B,I,I,I},
{I,I,I,I,I,B,I,G,I,I,I,I,I,G,I,I},
{I,I,I,I,I,I,G,G,I,I,I,I,I,I,G,I},
{I,I,I,I,I,I,I,B,I,I,I,I,I,I,I,B},
{B,I,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{B,B,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{G,I,G,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,G,G,B,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,B,G,G,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,G,I,G},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,B,B},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,I,B},
{B,I,I,I,I,I,I,I,B,I,I,I,I,I,I,I},
{I,G,I,I,I,I,I,I,G,G,I,I,I,I,I,I},
{I,I,G,I,I,I,I,I,G,I,B,I,I,I,I,I},
{I,I,I,B,I,I,I,I,I,G,B,B,I,I,I,I}};
int this_side_state = state(this_side);
int that_side_state = state(that_side);
return crossing_table[this_side_state][that_side_state] == G;
}
bool River::stop(void)
{
return state(_far_side) == stop_state;
}
River.h
#pragma once
#include <math.h>
#include "cargo.h"
class River
{
public:
River(void);
void show(void);
void cross(int);
bool stop(void);
private:
static const int stop_state = 15;
bool _far_side[Cargo::CARGO_AND_SHOWMAN];
bool _near_side[Cargo::CARGO_AND_SHOWMAN];
void copy(bool[], bool[]);
int state(bool[]);
bool goodCrossing(bool [], bool []);
};
Cargo.cpp
#include "Cargo.h"
int Cargo::charToCargo(char cargo)
{
switch(cargo)
{
case 'w': case 'W':
return WOLF;
case 's': case 'S':
return SHOWMAN;
case 'g': case 'G':
return GOAT;
case 'c': case 'C':
return CABBAGES;
default:
return NOCARGO;
}
}
char Cargo::cargoToChar(int cargo)
{
switch(cargo)
{
case WOLF:
return 'W';
case SHOWMAN:
return 'S';
case GOAT:
return 'G';
case CABBAGES:
return 'C';
case NOCARGO:
return 'N';
default:
return 'B';
}
}
bool Cargo::isCargo(char candidate)
{
switch(candidate)
{
case 'w': case 'W':
case 's': case 'S':
case 'g': case 'G':
case 'C': case 'c':
case 'N': case 'n':
return true;
default:
return false;
}
}
int Cargo::read(void)
{
char cargo;
do
{
cout << "Enter W for Wolf" << endl;
cout << "Enter N for no cargo" << endl;
cout << "Enter G for Goat" << endl;
cout << "Enter C for cabbages" << endl;
cout << "Enter cargo - ";
cin.get(cargo);
cin.ignore(numeric_limits<int>::max(), ' ');
}
while(!isCargo(cargo));
return charToCargo(cargo);
}
Cargo.h
#pragma once
#include <iostream>
#include <limits.h>
#include <string>
using namespace std;
class Cargo
{
public:
static int read(void);
static int charToCargo(char);
static char cargoToChar(int);
static bool isCargo(char);
static const int BADCARGO = -1;
static const int CABBAGES = 0;
static const int GOAT = 1;
static const int SHOWMAN = 2;
static const int WOLF = 3;
static const int NOCARGO = 4;
static const int CARGO_AND_SHOWMAN = 5;
};
Explanation / Answer
ANSWER::
public class WolfGoatCabbageGame implements RiverCrossingGame
{
private enum Element { FARMER, WOLF, GOAT, CABBAGE };
private Bank westBank;
private Bank eastBank;
private static Vector<State> states;
private List<String> steps;
class Bank
{
private String name;
private Vector<Element> elements;
private boolean isDestination;
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;
}
public Bank(Bank src)
{
name = src.name;
elements = (Vector<Element>) src.elements.clone();
isDestination = src.isDestination;
}
public boolean move(Element element, Bank dst)
{
if (!has(Element.FARMER) || !has(element) || dst.has(element))
return false;
Element object = take(element);
if (object == null)
return false;
dst.drop(object);
return true;
}
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;
}
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);
}
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;
}
private void drop(Element element) {
elements.add(element);
if (element != Element.FARMER)
elements.add(Element.FARMER);
}
}
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);
}
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);
}
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))));
}
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() + " " + eastBank.toString();
}
}
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>();
}
public void play() {
State startingState = new State(westBank, eastBank);
addState(startingState);
Vector<Element> elements = (Vector<Element>) westBank.getElements().clone();
boolean solved = false;
for (Element element : elements) {
Bank thisBank = new Bank(westBank);
Bank otherBank = new Bank(eastBank);
if (!thisBank.move(element, otherBank))
{
System.out.println("ILLEGAL MOVE! ");
}
State state = new State(thisBank, otherBank);
if (state.isPermitted(thisBank) && state.isPermitted(otherBank))
{
if (!solved && solve(state, otherBank, thisBank))
solved = true;
addStep(element, thisBank, otherBank);
printSteps();
}
}
}
private boolean solve(State state, Bank src, Bank dst)
{
addState(state);
if (state.isFinal(src)) {
return true;
}
Vector<Element> elements = (Vector<Element>) src.getElements().clone();
for (Element element : elements) {
Bank thisBank = new Bank(src);
Bank otherBank = new Bank(dst);
if (!thisBank.move(element, otherBank))
{
System.out.println("ILLEGAL MOVE! ");
}
State st = new State(thisBank, otherBank);
if (st.isPermitted(thisBank) && st.isPermitted(otherBank) && !stateExists(st))
{
if (solve(st, otherBank, thisBank))
{
addStep(element, thisBank, otherBank);
return true;
}
}
}
return false;
}
private void addState(State state)
{
states.add(state);
}
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 ";
step += from + " " + to + " ";
steps.add(0, step);
}
public void printSteps()
{
for (String step : steps)
{
System.out.println(step);
}
}
}