# Farmer crossing river with wolf, duck, bag of corn

Updated 0 Tallied Votes 2K Views

This snippets contains a python program to find a shortest solution to the problem of the farmer who whishes to cross a river. The boat can only contain two things, including the rower. The farmer comes with a wolf, a duck and a bag of corn, and he can't leave the duck alone with one of the other items because the wolf would eat the duck, or the duck would eat the corn.

The program shows how to use a `collections.OrderedDict` to implement a stack without repetitions. This is used to traverse a tree of states. These states, encoded as small integers, represent the situation on the east bank of the river. Four bits are used to indicate if the farmer, the duck, the wolf and the bag of corn are on this side of the river.

``````#!/usr/bin/env python3
# -*-coding: utf8-*-
'''Solves the farmer s crossing river problem
'''
__version__ = '0.2.0'
from collections import OrderedDict

FARMER, DUCK, WOLF, CORN = 8, 4, 2, 1
ALL = FARMER|DUCK|WOLF|CORN

# the following functions work if item and group are
# integers in range(16)

def duck_not_alone(group):
return (group & ~FARMER) >= 5

def has_item(item, group):
return (item & group) == item

def with_item(item, group):
return group | item

def without_item(item, group):
return group & ~item

def other_bank(group):
return 15 - group

def children(group):
if has_item(FARMER, group):
for item in (DUCK, WOLF, CORN):
if has_item(item, group) and not duck_not_alone(without_item(item, group)):
yield without_item(FARMER|item, group)
if not duck_not_alone(group):
yield without_item(FARMER, group)
else:
for c in children(other_bank(group)):
yield other_bank(c)

def walk_tree():
shortest = None
stack = OrderedDict()
stack[ALL] = children(ALL)
while stack:
top = next(reversed(stack))
for child in stack[top]:
if child not in stack:
break
else:
del stack[top]
continue
if child == 0:
shortest = list(stack)
shortest.append(child)
del stack[top]
elif (not shortest) or (len(stack) + 2 < len(shortest)):
stack[child] = children(child)
return shortest

def humanize(group):
L = []
for item, name in [(FARMER, 'farmer'),(DUCK, 'duck'), (WOLF, 'wolf'), (CORN, 'corn')]:
if has_item(item, group):
L.append(name)
return '({})'.format(', '.join(L))

def situation(east):
w, e = humanize(other_bank(east)), humanize(east)
return '{:>30s} ~~~ {:s}'.format(w, e)

def draw_solution(steps):
for group in steps:
print(situation(group))

if __name__ == '__main__':
draw_solution(walk_tree())

"""my output -->
() ~~~ (farmer, duck, wolf, corn)
(farmer, duck) ~~~ (wolf, corn)
(duck) ~~~ (farmer, wolf, corn)
(farmer, duck, wolf) ~~~ (corn)
(wolf) ~~~ (farmer, duck, corn)
(farmer, wolf, corn) ~~~ (duck)
(wolf, corn) ~~~ (farmer, duck)
(farmer, duck, wolf, corn) ~~~ ()
"""``````
Gribouillis 1,391

The snippet has been edited for a better version 0.2.0 ...

rubberman 1,355

Simple. The farmer secures the duck under his hat - now there is only the farmer, the wolf, and the bag of corn which the wolf won't be interested in. BTW, how does the farmer keep the wolf from eating him? :-)

AssertNull 1,094

Here is a C++ implementation.

``````// The goal is to move everyone from the west side of the river to the east side of the river
//
// Restrictions: Farmer must always stay with the boat.  Farmer can take at most one passenger
//               in the boat.  Duck and corn cannot be on the same side of the river without the
//               farmer.  Wolf and duck cannot be on the same side of the river without the
//               farmer.
//
// States      : Each of the four objects (wolf, duck, corn, farmer) has a state of 0 or 1. 0
//             : represents that the object's location is on the west side of the river, 1
//               means that the object's location is on the east side of the river.  The
//               combined state of the four objects is an integer value from 0 to 15, inclusive.
//               Each of the four objects has its own bit.  The bits are as follows, from least
//               to most significant bit: farmer, wolf, duck corn.
//
//               Farmer = 0001 = 1 (1 to the 0 power)
//               Wolf   = 0010 = 2 (1 to the 1 power)
//               Duck   = 0100 = 4 (1 to the 2 power)
//               Corn   = 1000 = 8 (1 to the 3 power)
//
//               Initial state = 0 (all objects are on west side of bank)
//               Success state = 15(all objects are on east side of bank)
//
//               1100 = 12 = Farmer and wolf on west side, duck and corn on east side
//               0011 =  3 = Farmer and wolf on east side, duck and corn on west side
//
//               Note that if you flip the 4 bits, you'll have the same configuration of
//               objects on the same side, just the east and west are flipped.  Notice also
//               that 3 + 12 equals 15, so if you want everyone to switch sides, you simply
//               subtract a state from 15 to get its flipped state (15 - 12 = 3).
//
//               This fact comes in handy when checking the legality of a certain state, since
//               illegal states involve the farmer being on one side, and certain pairs of
//               objects being on the other side.  State 12 is illegal.  Therefore state 3 is
//               also illegal since 15 - 12 is 3. State 8 (1000) is legal, so is state 7 (0111),
//               since state X's legality is always the same as state 15 minus X.
//
// Illegal states : An illegal state is any state where the farmer is on one side of the
//                  river and the duck and the wolf, or the duck and the corn, are on the
//                  other side.  The following are the illegal states, where * represents
//                  a wildcard state (i.e. the state does not matter).
//
//                  0001(1), 1001(9) - (*001 - farmer east, wolf and duck west, corn wildcard)
//                  0001(1), 0011(3) - (00*1 - farmer east, duck and corn west, wolf wildcard)
//
//                  So states 1, 3, and 9 are illegal.  Subtracting each of these states from 15
//                  (14, 12, 6 - see explanation above) results in a state that is also illegal.
//                  So the illegal states are {1,3,6,9,12,14}.
//
// Approach:        Starting state is state 0.  Ending state is state 15.  The goal is to get all
//                  objects across the river.  The farmer can be alone in the boat or take one
//                  object.  When the farmer is going from West to East, he attempts to take an
//                  object with him.  When going East to West, he tries to go alone since the goal
//                  is for all objects to end up on the East side.  All states are checked to make
//                  sure they are legal and that the objects have not been in that state before.
//
//                  I made the code as it is in order to possibly change the game a little bit
//                  in the future by adding or subtracting objects or adding and subtracting illegal
//                  combinations.  I think the code/algorithm can be improved.

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;

enum
{
FARMER = 0, WOLF, DUCK, CORN, NUM_OBJECTS
};

enum
{
WEST = 0, EAST
};

const int NUM_ILLEGAL_PAIRINGS = 2;
const int ILLEGAL_PAIRINGS[NUM_ILLEGAL_PAIRINGS][2] = {{WOLF, DUCK},{DUCK, CORN}};

const string OBJECT_NAMES[NUM_OBJECTS] = {"farmer", "wolf", "duck", "corn"};

const int START_STATE = 0;  // all objects on west side - 0000
const int END_STATE   = 15; // all objects on east side - 1111

bool state_is_legal(int state)
{
int farmer_side = ((state & FARMER_MASK) >> FARMER);

// iterate through all pairs of objects that don't get along.  If any are
// on the same side without the farmer's presence, then the state is illegal.
for (int i = 0; i < NUM_ILLEGAL_PAIRINGS; i++)
{
object1_side = ((state & mask) >> ILLEGAL_PAIRINGS[i][0]);
object2_side = ((state & mask) >> ILLEGAL_PAIRINGS[i][1]);

// a pair of objects have been selected to test.  If both objects
// are on the same side and the farmer is NOT on this side, this
// is an illegal state.
if(object1_side == object2_side && object1_side != farmer_side)
return false; // state is illegal.
}

return true; // all pairings tests have passed.  State is legal.
}

int switch_sides(int state, int object_to_switch)
{
int mask = (1 << object_to_switch);
state -= mask; // object is on east side.  Switch to west side.
else
state += mask; // object is on west side.  Switch to east side.
return state;
}

void Display(int state)
{
string west_group = "(";
string east_group = "(";
for(int i = 0; i < NUM_OBJECTS; i++)
{
east_group += OBJECT_NAMES[i] + ",";
else
west_group += OBJECT_NAMES[i] + ",";
}
west_group += ")";
east_group += ")";
cout << setw(30) << right << west_group << " ~~ " << east_group << endl;
}

bool contains(const vector <int>& states, int value)
{
int size = states.size();
for(int i = 0; i < size; i++)
{
if(states[i] == value)
return true;
}
return false;
}

int main()
{
int farmer_side, farmer_switch_state, new_state;
bool farmer_switch_state_valid, new_state_valid;
vector <int> states;
int state = START_STATE; // all on west bank.
states.push_back(state);

while(state != END_STATE)
{
farmer_side = ((state & (1 << FARMER)) >> FARMER);
farmer_switch_state = switch_sides(state, FARMER);
farmer_switch_state_valid = state_is_legal(farmer_switch_state) && !contains(states, farmer_switch_state);
if(farmer_side == EAST && farmer_switch_state_valid)
{
// farmer is on east side, travels to west side alone
states.push_back(farmer_switch_state);
state = farmer_switch_state;
continue;
}
for(int i = 1; i < NUM_OBJECTS; i++)
{
int object_side = ((state & (1 << i)) >> i);
new_state = switch_sides(farmer_switch_state, i);
new_state_valid = object_side == farmer_side && state_is_legal(new_state) && !contains(states, new_state);

if(new_state_valid)
{
// farmer is taking an object with him in the boat ride.
break;
}
}

if(new_state_valid)
{
state = new_state;
states.push_back(state);
continue;
}

if(farmer_switch_state_valid)
{
// farmer is traveling west to east alone because he cannot take an object
state = farmer_switch_state;
states.push_back(state);
continue;
}

return 1; // No valid state found.  TODO - handle this without aborting.
}

int size = states.size();
for(int i = 0; i < size; i++)
{
Display(states[i]);
}
return 0;
}
``````
Gribouillis commented: good code +14
AssertNull 1,094

Mistake in the comments above. Fairly obvious, but will point it out anyway. Lines 15 to 18 should be:

// Farmer = 0001 = 1 (2 to the 0 power)
// Wolf = 0010 = 2 (2 to the 1 power)
// Duck = 0100 = 4 (2 to the 2 power)
// Corn = 1000 = 8 (2 to the 3 power)

Base 2, not base 1, so raising 2 to a power, not raising 1 to a power, which makes no sense.

Gribouillis 1,391

Nice code. The interesting part is that you are using a heuristic instead of a systematic scanning of the whole graph. This approach may be more flexible for generalized versions of the problem.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.