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.