River Bank

Problem

The wolf, goat, cabbage riddle is pretty well known. A farmer has a wolf, goat, and cabbage on one side of the river. He needs to transport everything across the river in a small boat that can hold only himself and one other thing. He can’t leave the wolf and goat by themselves, he also cannot leave the goat with the cabbage. How does he get everything across?

Representation

We have to keep track of which side of the river things are on. There are 4 items lets use a binary array with the elements representing the person, cabbage, goat, wolf. Since each thing can be on one side of the river or the other we only need to know one side to know the other. The state can be represented as a 4 bit array or a number between 0 and 16.

The starting state is (1,1,1,1) everything on the first side of the river.

⎕←s0←4⍴1

┌→──────┐ │1 1 1 1│ └~──────┘

How do we get the next states we can transion too? We can build an adjacency matrix or anything that is isomorphically the same. For any individul state we know the person has to move and one or zero other items can move. And those get added or removed based on which direction the farmer travels. If we xor the current state with the four possible trips we get the states it can transition too.

⍝ possible s1s
(⊂s0)≠(1 0 0 0) (1 0 0 1) (1 0 1 0) (1 1 0 0)

┌→────────────────────────────────────────┐ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 1 1 1│ │0 1 1 0│ │0 1 0 1│ │0 0 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ └∊────────────────────────────────────────┘

⎕←transitions←(1 0 0 0) (1 0 0 1) (1 0 1 0) (1 1 0 0)

┌→────────────────────────────────────────┐ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 0 0 0│ │1 0 0 1│ │1 0 1 0│ │1 1 0 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ └∊────────────────────────────────────────┘

Lets build the full table.

⎕←states←↓⍉2 2 2 2⊤⍳16

┌→────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 0 0 0│ │0 0 0 1│ │0 0 1 0│ │0 0 1 1│ │0 1 0 0│ │0 1 0 1│ │0 1 1 0│ │0 1 1 1│ │1 0 0 0│ │1 0 0 1│ │1 0 1 0│ │1 0 1 1│ │1 1 0 0│ │1 1 0 1│ │1 1 1 0│ │1 1 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ └∊────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

⍉transitions ∘.≠ states

┌→────────────────────────────────────────┐ ↓ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 0 0 0│ │1 0 0 1│ │1 0 1 0│ │1 1 0 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 0 0 1│ │1 0 0 0│ │1 0 1 1│ │1 1 0 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 0 1 0│ │1 0 1 1│ │1 0 0 0│ │1 1 1 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 0 1 1│ │1 0 1 0│ │1 0 0 1│ │1 1 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 1 0 0│ │1 1 0 1│ │1 1 1 0│ │1 0 0 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 1 0 1│ │1 1 0 0│ │1 1 1 1│ │1 0 0 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 1 1 0│ │1 1 1 1│ │1 1 0 0│ │1 0 1 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │1 1 1 1│ │1 1 1 0│ │1 1 0 1│ │1 0 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 0 0 0│ │0 0 0 1│ │0 0 1 0│ │0 1 0 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 0 0 1│ │0 0 0 0│ │0 0 1 1│ │0 1 0 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 0 1 0│ │0 0 1 1│ │0 0 0 0│ │0 1 1 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 0 1 1│ │0 0 1 0│ │0 0 0 1│ │0 1 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 1 0 0│ │0 1 0 1│ │0 1 1 0│ │0 0 0 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 1 0 1│ │0 1 0 0│ │0 1 1 1│ │0 0 0 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 1 1 0│ │0 1 1 1│ │0 1 0 0│ │0 0 1 0│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │0 1 1 1│ │0 1 1 0│ │0 1 0 1│ │0 0 1 1│ │ │ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ └∊────────────────────────────────────────┘

The starting state is the index of each subarray. The numbers are the states it is possible to transition to from the index state.

⎕←st←↓⍉2⊥¨transitions ∘.≠ states

┌→────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→────────┐ ┌→────────┐ ┌→─────────┐ ┌→─────────┐ ┌→─────────┐ ┌→─────────┐ ┌→──────────┐ ┌→──────────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │8 9 10 12│ │9 8 11 13│ │10 11 8 14│ │11 10 9 15│ │12 13 14 8│ │13 12 15 9│ │14 15 12 10│ │15 14 13 11│ │0 1 2 4│ │1 0 3 5│ │2 3 0 6│ │3 2 1 7│ │4 5 6 0│ │5 4 7 1│ │6 7 4 2│ │7 6 5 3│ │ │ └~────────┘ └~────────┘ └~─────────┘ └~─────────┘ └~─────────┘ └~─────────┘ └~──────────┘ └~──────────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │ └∊────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

State 0 can transition to 8, 9, 10 or 12. State 1 can transition to 9, 8, 11, 13. Etc

Unfortunatly some states are forbidden. Specifically those without the farmer with wolf-goat or goat-cabbage, or wolf-goat-cabbage. We also have to consider an illegal state cant be on the other side of the river as well. These are

(0 1 1 0) (0 0 1 1) (0 1 1 1) (1 0 0 1) (1 1 0 0) (1 0 0 0) lets remove these so we cant transition to them.

2⊥¨(0 1 1 0) (0 0 1 1) (0 1 1 1) (1 0 0 1) (1 1 0 0) (1 0 0 0) 

┌→───────────┐ │6 3 7 9 12 8│ └~───────────┘

⎕←st←st ~¨ ⊂2⊥¨(0 1 1 0) (0 0 1 1) (0 1 1 1) (1 0 0 1) (1 1 0 0) (1 0 0 0)

┌→────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→─┐ ┌→────┐ ┌→───────┐ ┌→───────┐ ┌→────┐ ┌→────┐ ┌→───────┐ ┌→──────────┐ ┌→──────┐ ┌→────┐ ┌→──┐ ┌→──┐ ┌→────┐ ┌→────┐ ┌→──┐ ┌→┐ │ │ │10│ │11 13│ │10 11 14│ │11 10 15│ │13 14│ │13 15│ │14 15 10│ │15 14 13 11│ │0 1 2 4│ │1 0 5│ │2 0│ │2 1│ │4 5 0│ │5 4 1│ │4 2│ │5│ │ │ └~─┘ └~────┘ └~───────┘ └~───────┘ └~────┘ └~────┘ └~───────┘ └~──────────┘ └~──────┘ └~────┘ └~──┘ └~──┘ └~────┘ └~────┘ └~──┘ └~┘ │ └∊────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

 ⍝ if we want to view the actual adjancency matrix we can
 {⍉(⍳⍴⍵)∘.∊⍵} st

┌→──────────────────────────────┐ ↓0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0│ │0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0│ │0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1│ │0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0│ │0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1│ │0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1│ │0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1│ │1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0│ │1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0│ │1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0│ │0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0│ │1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0│ │0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0│ │0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0│ └~──────────────────────────────┘

State Transition Graph

The dfns workspace has a path function to find the shortest path in a graph given the graph s tarting node and an end node. With the state table built this is just a function call.

st path 15 0

┌→──────────────────┐ │15 5 13 1 11 2 10 0│ └~──────────────────┘

⎕←bank0←⍉2 2 2 2⊤st path 15 0

┌→──────┐ ↓1 1 1 1│ │0 1 0 1│ │1 1 0 1│ │0 0 0 1│ │1 0 1 1│ │0 0 1 0│ │1 0 1 0│ │0 0 0 0│ └~──────┘

Solution

Lets try and make this solution more understandable. First lets show both sides of the river

bank1←~bank0

bank0 bank1

┌→────────────────────┐ │ ┌→──────┐ ┌→──────┐ │ │ ↓1 1 1 1│ ↓0 0 0 0│ │ │ │0 1 0 1│ │1 0 1 0│ │ │ │1 1 0 1│ │0 0 1 0│ │ │ │0 0 0 1│ │1 1 1 0│ │ │ │1 0 1 1│ │0 1 0 0│ │ │ │0 0 1 0│ │1 1 0 1│ │ │ │1 0 1 0│ │0 1 0 1│ │ │ │0 0 0 0│ │1 1 1 1│ │ │ └~──────┘ └~──────┘ │ └∊────────────────────┘

Lets translate these back into names

⎕←items←'farmer' 'cabbage' 'goat' 'wolf'

┌→─────────────────────────────────┐ │ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→───┐ │ │ │farmer│ │cabbage│ │goat│ │wolf│ │ │ └──────┘ └───────┘ └────┘ └────┘ │ └∊─────────────────────────────────┘

(/∘items⍤1⊢bank0) (/∘items⍤1⊢bank1)

┌→────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→────────────────────────────────────────┐ ┌→────────────────────────────────────────┐ │ │ ↓ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→───┐ │ ↓ ┌→─────┐ ┌→─────┐ ┌→─────┐ ┌→─────┐ │ │ │ │ │farmer│ │cabbage│ │goat│ │wolf│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └──────┘ └───────┘ └────┘ └────┘ │ │ └──────┘ └──────┘ └──────┘ └──────┘ │ │ │ │ ┌→──────┐ ┌→───┐ ┌→──────┐ ┌→──────┐ │ │ ┌→─────┐ ┌→───┐ ┌→─────┐ ┌→─────┐ │ │ │ │ │cabbage│ │wolf│ │ │ │ │ │ │ │farmer│ │goat│ │ │ │ │ │ │ │ │ └───────┘ └────┘ └───────┘ └───────┘ │ │ └──────┘ └────┘ └──────┘ └──────┘ │ │ │ │ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→─────┐ │ │ ┌→───┐ ┌→───┐ ┌→───┐ ┌→───┐ │ │ │ │ │farmer│ │cabbage│ │wolf│ │ │ │ │ │goat│ │ │ │ │ │ │ │ │ │ │ └──────┘ └───────┘ └────┘ └──────┘ │ │ └────┘ └────┘ └────┘ └────┘ │ │ │ │ ┌→───┐ ┌→───┐ ┌→───┐ ┌→───┐ │ │ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→─────┐ │ │ │ │ │wolf│ │ │ │ │ │ │ │ │ │farmer│ │cabbage│ │goat│ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ │ │ └──────┘ └───────┘ └────┘ └──────┘ │ │ │ │ ┌→─────┐ ┌→───┐ ┌→───┐ ┌→─────┐ │ │ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │ │ │ │ │farmer│ │goat│ │wolf│ │ │ │ │ │cabbage│ │ │ │ │ │ │ │ │ │ │ └──────┘ └────┘ └────┘ └──────┘ │ │ └───────┘ └───────┘ └───────┘ └───────┘ │ │ │ │ ┌→───┐ ┌→───┐ ┌→───┐ ┌→───┐ │ │ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→─────┐ │ │ │ │ │goat│ │ │ │ │ │ │ │ │ │farmer│ │cabbage│ │wolf│ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ │ │ └──────┘ └───────┘ └────┘ └──────┘ │ │ │ │ ┌→─────┐ ┌→───┐ ┌→─────┐ ┌→─────┐ │ │ ┌→──────┐ ┌→───┐ ┌→──────┐ ┌→──────┐ │ │ │ │ │farmer│ │goat│ │ │ │ │ │ │ │cabbage│ │wolf│ │ │ │ │ │ │ │ │ └──────┘ └────┘ └──────┘ └──────┘ │ │ └───────┘ └────┘ └───────┘ └───────┘ │ │ │ │ ┌→─────┐ ┌→─────┐ ┌→─────┐ ┌→─────┐ │ │ ┌→─────┐ ┌→──────┐ ┌→───┐ ┌→───┐ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │farmer│ │cabbage│ │goat│ │wolf│ │ │ │ │ └──────┘ └──────┘ └──────┘ └──────┘ │ │ └──────┘ └───────┘ └────┘ └────┘ │ │ │ └∊────────────────────────────────────────┘ └∊────────────────────────────────────────┘ │ └∊────────────────────────────────────────────────────────────────────────────────────────┘

What the farmer takes on every river crossing.

1. goat
2. nothing
3. cabbage
4. goat
5. wolf
6. nothing
7. goat