Fox, Sheep, Cabbage problem - revisited

BobG

The fox, sheep, cabbage problem is too complicated of a task for a person to figure out. Someone should design a simple battery operated computer for this guy so he doesn't have to think.

Let the high from the battery equal the left side of the river and the low from the battery equal equal the right side of the river. The computer will have 4 switches (one each for the person, fox, sheep, and cabbage). The person can flip the switches to try out different combinations. A light will light up if the decision would be a bad one. In essence, you have a truth table

P S F C L
0 0 0 0 0 Every one is on the right side, person can control chaos
0 0 0 1 0 Cabbage is alone, person can keep fox from eating sheep
0 0 1 0 0 Fox is alone, person can keep sheep from eating cabbage
0 0 1 1 0 Fox doesn't eat cabbage, no problem
0 1 0 0 0 Sheep is alone, no problem
0 1 0 1 1 Now we have a problem - sheep can't be left alone with cabbage
0 1 1 0 1 Problem, fox will eat sheep on left side of river
0 1 1 1 1 Big problems, major chaos - who knows what will happen
1 0 0 0 1 Still big problems, just on right side of river instead of left
1 0 0 1 1 Fox will eat sheep on right side of river
1 0 1 0 1 Sheep will contentedly eat cabbage on right side of river
1 0 1 1 0 No problem, as long as sheep doesn't get lonely
1 1 0 0 0 Now nobody's lonely
1 1 0 1 0 Foxes don't get lonely
1 1 1 0 0 Neither does cabbage
1 1 1 1 0 Mission accomplished, everyone's on other side of river

The six possible problems can be reduced to four logical combinations via Boolean logic. Letting '!' represent 'not', the circuitry of the computer can be reduced to:

(P!)SC + (P!)SF + P(S!)(F!) + P(S!)F(C!)

Now the person can tell if a certain combination will cause him a problem. Unfortunately, this doesn't give the person a combination that will carry him from 0000 to 1111. A binary counter won't work - it will have some people swimming and sometimes will have no one bringing the boat back (plus it will count right through the problem). A Gray Code counter also has some problems - it only moves one person at a time, sometimes having the boat move the same direction two times in succession (plus it will count right through the problem).

How do you design a counter that will count the proper combinations in succession, avoiding situations which will light the light?

Gokul43201

Foxes don't like cabbage ? That's just weird !!

TenaliRaman

Put in white, just in case .... but maybe irrelevant

hmm what are we exactly looking for?
0000->1100->0100->1110->0010->1011->0011->1111
is one possible sequence
one can simply draw a state diagram, assume to be working with JKFF, use kmaps and finish the problem ?


-- AI

NateTG

Foxes (though nominally carnivores) would probably eat cabage in a pinch.

BobG:
Do you care if the solution is optimal? Otherwise a tree-traversal would work.

BobG

It would probably be more optimal than mine, since I might have spent about 10 minutes on it. Mine was basically the same as TenaliRaman's, except I did the Boolean equations for the control gates driving the flip-flops (and I used D's instead of JK's).

Gokul43201

Did you know that the JK stood for John Kerry ?