过河算法

面试的时候，被问到过河算法，所以写了一下，
此算法的特点：将类型安装二进制存储，如狼 1，人 2，羊 4，草 8.
            比较的时候按位操作，在算法2中可以扩展一辆船容量N个人
算法1：
import java.util.ArrayList;

public class PassRiver {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");

private long typeid;

public long getTypeid() {
return typeid;
}

public void setTypeid(long typeid) {
this.typeid = typeid;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

private String name;

Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}

public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}

private enum Side {
left, right;
}

private class State {
private long rightSideState;

public long getRightSideState() {
return rightSideState;
}

public long getLeftSideState() {
return leftSideState;
}

public Side getSide() {
return side;
}

private long leftSideState;

private Side side;

public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}

public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}

private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;

private long successState;
private static final Type[] types = Type.values();;

ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;

public StringBuilder getSteps() {
return steps;
}

private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_LEFT = "Remove all boat animals to left side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT = "Remove all boat animals to right side: ";

private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";

PassRiver(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };

this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}

public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {

if (rightSideState == successState)
return true;

addHappenedState(new State(leftSideState, rightSideState, side));

long leftState = leftSideState;
long rightState = rightSideState;
String step;

// have no animal in the boat
if (sizeOfBoatAnimals == 0) {
return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);
} else if (sizeOfBoatAnimals == 1) {

if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}

return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);

} else if (sizeOfBoatAnimals == 2) {

if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}

// remove all animals
if (side == Side.left) {
leftState = leftSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT;
}

if (passWithCheck(leftState, 0, rightState, side, 0)) {
logSteps(step + "\n");
return true;
}

// remove not driver
long animalNotDriver = boatSideState;
for (int i = 0; i < driver.length; i++) {
animalNotDriver = animalNotDriver & (~driver[i].getTypeid());
}
boatSideState = removeAnimal(boatSideState, animalNotDriver);

if (side == Side.left) {
leftState = leftSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_RIGHT;
}

if (passWithCheck(leftState, boatSideState, rightState, side, 1)) {
logSteps(step + Type.getNameById(animalNotDriver) + "\n");
return true;
}

}
return false;
}

private boolean driveBoatToAnotherSide(long leftSideState,
long boatSideState, long rightSideState, Side side,
int sizeOfBoatAnimals) {
if (haveDriver(boatSideState)) {
if (passWithCheck(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),
sizeOfBoatAnimals)) {
logSteps(DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}
return false;
}

private boolean moveToBoat(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {
long leftState = leftSideState;
long rightState = rightSideState;
String step;

for (int i = 0; i < types.length; i++) {
if (side == Side.left) {
if ((types[i].getTypeid() & leftSideState) != 0) {
leftState = removeAnimal(leftSideState, types[i]
.getTypeid());
step = MOVE_FROM_LEFT_TO_BOAT;

} else {
continue;
}
} else {
if ((types[i].getTypeid() & rightSideState) != 0) {
rightState = removeAnimal(rightSideState, types[i]
.getTypeid());
step = MOVE_FROM_RIGHT_TO_BOAT;
} else {
continue;
}
}

if (passWithCheck(leftState, boatSideState | types[i].getTypeid(),
rightState, side, sizeOfBoatAnimals + 1)) {
logSteps(step + Type.getNameById(types[i].getTypeid()) + "\n");
return true;
}
}
return false;
}

private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}

private boolean passWithCheck(long leftState, long boatState,
long rightState, Side side, int sizeOfBoatAnimals) {

if (checkCanExist(leftState) == false
|| checkCanExist(rightState) == false
|| checkCanExist(boatState) == false)
return false;
if (isHappenedState(new State(leftState, rightState, side)) == true)
return false;
if (pass(leftState, boatState, rightState, side, sizeOfBoatAnimals)) {

StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
logSteps(sbTemp.toString());
return true;
}

return false;
}

private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;

return false;

}

private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}

private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
s.append(types[i].getName()).append(",");
}
}
s.append("\n");
return s;
}

private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;

while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);

if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}

return right;
}

private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}

for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}

private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}

private void logSteps(String s) {
this.steps.insert(0, s);
}

public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver pr = new PassRiver(startState);
pr.pass(startState, 0, 0, Side.left, 0);

System.out.print(pr.getSteps());
}
}

算法2：
import java.util.ArrayList;
import java.util.List;



public class PassRiver2 {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");

private long typeid;

public long getTypeid() {
return typeid;
}

public void setTypeid(long typeid) {
this.typeid = typeid;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

private String name;

Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}

public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}

private enum Side {
left, right;
}

private class State {
private long rightSideState;

public long getRightSideState() {
return rightSideState;
}

public long getLeftSideState() {
return leftSideState;
}

public Side getSide() {
return side;
}

private long leftSideState;

private Side side;

public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}

public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}

private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;

private long successState;
private long maxSizeOfBoatAnimal = 2;
private static final Type[] types = Type.values();;

ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;

public StringBuilder getSteps() {
return steps;
}

private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";

private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";

PassRiver2(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };

this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}


public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side) {

if (rightSideState == successState)
return true;

if (checkCanExist(leftSideState) == false
|| checkCanExist(boatSideState) == false
|| checkCanExist(rightSideState) == false)
return false;

if (isHappenedState(new State(leftSideState, rightSideState, side)) == true)
return false;

addHappenedState(new State(leftSideState, rightSideState, side));

List<Type> boatAnimals = getAnimalList(boatSideState);
//boat is on the left side
if(side == Side.left){
//move animal from left side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(leftSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side)) {
logSteps(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side, MOVE_FROM_LEFT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");
return true;
}
}
}

//move animal from boat to left side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side)) {
logSteps(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side, REMOVE_ANIMALS_TO_LEFT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
//boat is on the right side
}else{
//move animal from right side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(rightSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side)) {

logSteps(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side, MOVE_FROM_RIGHT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");


return true;
}
}
}

//move animal from boat to right side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side)) {
logSteps(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side, REMOVE_ANIMALS_TO_RIGHT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
}

//drive to another side
if (haveDriver(boatSideState)) {
if (pass(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left) )) {

logSteps(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}

return false;
}



private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}


private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;

return false;

}

private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}

private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
List<Type>  list = getAnimalList(state);
for (int i = 0; i < list.size(); i++) {
s.append(list.get(i).getName()).append(",");
}
s.append("\n");
return s;
}

    public List<Type> getAnimalList(long state){
    ArrayList<Type> list = new ArrayList<Type>();
    for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
list.add(types[i]);

}
}
    return list;
}

private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;

while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);

if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}

return right;
}

private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}

for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}

private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}

private void logSteps(long leftState , long boatState,long rightState,Side side, String msg) {
StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp.append(msg)
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
this.steps.insert(0, sbTemp);
}

public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver2 pr = new PassRiver2(startState);
pr.pass(startState, 0, 0, Side.left );

System.out.print(pr.getSteps());
}
}