Farmer's River Crossing Puzzle

You are given the classic river crossing puzzle. A farmer wishes to transport a wolf, a goat, and a cabbage across a river. However, the boat can only carry the farmer along with one item at a time. The puzzle's catch is that if left alone together, the wolf will eat the goat, or the goat will eat the cabbage.

Your task is to output the precise sequence of moves that will safely transport all characters from the left bank to the right bank. Each move is represented as a tuple detailing the item that is moved, the remaining items on the left bank, and the items on the right bank after that move.

The correct sequence of moves is given below:

\[ \begin{array}{l} (\text{goat}, \ [\text{farmer},\text{wolf},\text{cabbage}], \ [\text{goat}]),\\ (\text{farmer}, \ [\text{wolf},\text{cabbage}], \ [\text{farmer},\text{goat}]),\\ (\text{wolf}, \ [\text{farmer},\text{cabbage}], \ [\text{wolf},\text{goat}]),\\ (\text{goat}, \ [\text{cabbage}], \ [\text{farmer},\text{wolf}], \ [\text{goat}]),\\ (\text{cabbage}, \ [\text{farmer},\text{goat}], \ [\text{cabbage},\text{wolf}]),\\ (\text{farmer}, \ [\text{goat}], \ [\text{farmer},\text{wolf},\text{cabbage}]),\\ (\text{goat}, \ [], \ [\text{farmer},\text{wolf},\text{cabbage},\text{goat}]) \end{array} \]

inputFormat

The program does not require any input. However, to adhere to the standard input/output format, a dummy string will be provided via stdin. The program should ignore any input and simply output the correct sequence of moves.

Format: A single line string from stdin (which is ignored).

outputFormat

The output should print the precise sequence of moves as a single string exactly matching the expected format.

Format: The printed output from stdout must be in the following format:

[('goat', ['farmer', 'wolf', 'cabbage'], ['goat']), ('farmer', ['wolf', 'cabbage'], ['farmer', 'goat']), ('wolf', ['farmer', 'cabbage'], ['wolf', 'goat']), ('goat', ['cabbage'], ['farmer', 'wolf'], ['goat']), ('cabbage', ['farmer', 'goat'], ['cabbage', 'wolf']), ('farmer', ['goat'], ['farmer', 'wolf', 'cabbage']), ('goat', [], ['farmer', 'wolf', 'cabbage', 'goat'])]

run

[('goat', ['farmer', 'wolf', 'cabbage'], ['goat']), ('farmer', ['wolf', 'cabbage'], ['farmer', 'goat']), ('wolf', ['farmer', 'cabbage'], ['wolf', 'goat']), ('goat', ['cabbage'], ['farmer', 'wolf'], ['goat']), ('cabbage', ['farmer', 'goat'], ['cabbage', 'wolf']), ('farmer', ['goat'], ['farmer', 'wolf', 'cabbage']), ('goat', [], ['farmer', 'wolf', 'cabbage', 'goat'])]