Salad, Sheep, Fox

Martin Ueding

2020-12-06

Code & Zahlen

Recently I have moved and since I've basically exchanged flats with somebody else and her friend, I have been driving around three locations for a whole weekend. I would try to figure out which stuff to load into the car, where to drive next, which person to bring along on the free seat. One would of course need to drive the car where the stuff should go to, but also have a sufficient number of people to carry stuff and put up furniture.

This has reminded me of the classical salad-sheep-fox riddle, which goes like this: You have a salad, a sheep and a fox. They are all on one bank of a river and you want to cross it. You have a raft which can only hold one thing at a time. But you cannot leave the sheep unattended with the fox, otherwise the fox will kill the sheep. Yet you cannot leave the salad unattended with the sheep, as the sheep will eat it. You need to figure out a way to transfer the stuff without leaving something unattended.

So you cannot start ferrying the salad, the fox will kill the sheep. You cannot start ferrying the fox, the sheep will eat the salad. You will need to ferry the sheep first. Then you ferry back. We can take either the salad or the fox. Let us try the salad. We end up with the salad and the sheep on the other bank, the fox at the start. We cannot just leave them there together unattended. But ferrying back the salad makes no sense, so we ferry back the sheep. On the starting bank we exchange the sheep for the fox, ferry over the fox. We then got the salad and the fox together on the other bank, the sheep left behind. We sail back, load in the sheep, and ferry it to the other bank. Done.

This should be solvable systematically. We have three objects, and three places where they can be. This makes for 27 states, but we can already rule out the states where more than one element is on the raft. This gives us the following states, with the original river bank on the right and the other bank on the left. The raft is in the middle.

I start with a bit of starting code to define a state and the items.

import collections
import itertools
import pprint
import subprocess

State = collections.namedtuple('State', ['left', 'raft', 'right'])
State.__repr__ = lambda self: '({} | {} | {})'.format(', '.join(self.left), ', '.join(self.raft), ', '.join(self.right))

items = ['Salad', 'Sheep', 'Fox', 'Person']

Then I build up all the states that are possible, but not necessarily legal.

states = []
for positions in itertools.product(range(3), range(3), range(3), range(3)):
    state = State(set(), set(), set())
    for position, item in zip(positions, items):
        state[position].add(item)
    states.append(state)

We end up with these states in the system. The states are to be read like as (left bank, raft, right bank).

[(Person, Salad, Sheep, Fox |  | ),
 (Salad, Sheep, Fox | Person | ),
 (Salad, Sheep, Fox |  | Person),
 (Person, Salad, Sheep | Fox | ),
 (Salad, Sheep | Person, Fox | ),
 (Salad, Sheep | Fox | Person),
 (Person, Salad, Sheep |  | Fox),
 (Salad, Sheep | Person | Fox),
 (Salad, Sheep |  | Person, Fox),
 (Person, Salad, Fox | Sheep | ),
 (Salad, Fox | Person, Sheep | ),
 (Salad, Fox | Sheep | Person),
 (Person, Salad | Sheep, Fox | ),
 (Salad | Person, Sheep, Fox | ),
 (Salad | Sheep, Fox | Person),
 (Person, Salad | Sheep | Fox),
 (Salad | Person, Sheep | Fox),
 (Salad | Sheep | Person, Fox),
 (Person, Salad, Fox |  | Sheep),
 (Salad, Fox | Person | Sheep),
 (Salad, Fox |  | Person, Sheep),
 (Person, Salad | Fox | Sheep),
 (Salad | Person, Fox | Sheep),
 (Salad | Fox | Person, Sheep),
 (Person, Salad |  | Sheep, Fox),
 (Salad | Person | Sheep, Fox),
 (Salad |  | Person, Sheep, Fox),
 (Person, Sheep, Fox | Salad | ),
 (Sheep, Fox | Person, Salad | ),
 (Sheep, Fox | Salad | Person),
 (Person, Sheep | Salad, Fox | ),
 (Sheep | Person, Salad, Fox | ),
 (Sheep | Salad, Fox | Person),
 (Person, Sheep | Salad | Fox),
 (Sheep | Person, Salad | Fox),
 (Sheep | Salad | Person, Fox),
 (Person, Fox | Salad, Sheep | ),
 (Fox | Person, Salad, Sheep | ),
 (Fox | Salad, Sheep | Person),
 (Person | Salad, Sheep, Fox | ),
 ( | Person, Salad, Sheep, Fox | ),
 ( | Salad, Sheep, Fox | Person),
 (Person | Salad, Sheep | Fox),
 ( | Person, Salad, Sheep | Fox),
 ( | Salad, Sheep | Person, Fox),
 (Person, Fox | Salad | Sheep),
 (Fox | Person, Salad | Sheep),
 (Fox | Salad | Person, Sheep),
 (Person | Salad, Fox | Sheep),
 ( | Person, Salad, Fox | Sheep),
 ( | Salad, Fox | Person, Sheep),
 (Person | Salad | Sheep, Fox),
 ( | Person, Salad | Sheep, Fox),
 ( | Salad | Person, Sheep, Fox),
 (Person, Sheep, Fox |  | Salad),
 (Sheep, Fox | Person | Salad),
 (Sheep, Fox |  | Person, Salad),
 (Person, Sheep | Fox | Salad),
 (Sheep | Person, Fox | Salad),
 (Sheep | Fox | Person, Salad),
 (Person, Sheep |  | Salad, Fox),
 (Sheep | Person | Salad, Fox),
 (Sheep |  | Person, Salad, Fox),
 (Person, Fox | Sheep | Salad),
 (Fox | Person, Sheep | Salad),
 (Fox | Sheep | Person, Salad),
 (Person | Sheep, Fox | Salad),
 ( | Person, Sheep, Fox | Salad),
 ( | Sheep, Fox | Person, Salad),
 (Person | Sheep | Salad, Fox),
 ( | Person, Sheep | Salad, Fox),
 ( | Sheep | Person, Salad, Fox),
 (Person, Fox |  | Salad, Sheep),
 (Fox | Person | Salad, Sheep),
 (Fox |  | Person, Salad, Sheep),
 (Person | Fox | Salad, Sheep),
 ( | Person, Fox | Salad, Sheep),
 ( | Fox | Person, Salad, Sheep),
 (Person |  | Salad, Sheep, Fox),
 ( | Person | Salad, Sheep, Fox),
 ( |  | Person, Salad, Sheep, Fox)]

Now we need to filter out the states which are not allowed.

def is_allowed(state):
    for bank in [state.left, state.right]:
        # If the person is not there to watch but salad and sheep are on the same bank, that is a problem.
        if 'Person' not in bank and {'Salad', 'Sheep'} <= bank:
            return False
        # Same with sheep and fox.
        if 'Person' not in bank and {'Sheep', 'Fox'} <= bank:
            return False

    # The raft must always be attended by the person and can carry only one element.
    if len(state.raft) > 0:
        if 'Person' not in state.raft:
            return False
        if len(state.raft) > 2:
            return False

    return True

states2 = [state for state in states if is_allowed(state)]

From the 81 states there are only 20 left now:

[(Person, Salad, Sheep, Fox |  | ),
 (Person, Salad, Sheep |  | Fox),
 (Salad, Fox | Person, Sheep | ),
 (Salad | Person, Sheep | Fox),
 (Person, Salad, Fox |  | Sheep),
 (Salad, Fox | Person | Sheep),
 (Salad, Fox |  | Person, Sheep),
 (Salad | Person, Fox | Sheep),
 (Salad |  | Person, Sheep, Fox),
 (Sheep | Person, Salad | Fox),
 (Fox | Person, Salad | Sheep),
 (Person, Sheep, Fox |  | Salad),
 (Sheep | Person, Fox | Salad),
 (Person, Sheep |  | Salad, Fox),
 (Sheep | Person | Salad, Fox),
 (Sheep |  | Person, Salad, Fox),
 (Fox | Person, Sheep | Salad),
 ( | Person, Sheep | Salad, Fox),
 (Fox |  | Person, Salad, Sheep),
 ( |  | Person, Salad, Sheep, Fox)]

We have connections between the states where the stuff on the raft goes to either side of the river.

connections = []

for state1 in states2:
    for state2 in states2:
        # We don't need connections from a state to itself.
        if state1 == state2:
            continue
        # We only want connections between states where the raft is full and where it is empty.
        # Without loss of generality, I choose the `state2` to have an empty raft.
        if len(state2.raft) > 0:
            continue

        # If the raft gets unloaded to the left, that is a connection.
        if state1.left | state1.raft == state2.left and state1.right == state2.right:
            connections.append((state1, state2))

        # If the raft gets unloaded to the right, that is a connection.
        if state1.left == state2.left and state1.right | state1.raft == state2.right:
            connections.append((state1, state2))

Now we just need to make a graph from this.

with open('graph.dot', 'w') as f:
    f.write('graph {\nnode [shape=box]\noverlap=false\nsplines=true\n')
    for state in states2:
        f.write('"{}"\n'.format(repr(state)))
    for left, right in connections:
        f.write('"{}" -- "{}"\n'.format(repr(left), repr(right)))
    f.write('}')

subprocess.run(['neato', '-Tpdf', 'graph.dot', '-o', 'graph.pdf'])
subprocess.run(['neato', '-Tpng', 'graph.dot', '-o', 'graph.png'])

And we can nicely see the structure of this problem. The start state is at the top, the final state at the bottom. And there are not so many alternatives. The only choice we have is whether we ferry the salad or the fox after the sheep, but that is about it.

It turns out that due to the small number of choices, it is not so hard to solve without any tools, as I have done at the beginning of this post. Still seeing the state structure was fun!