River Crossing
Statement
Goal
There is a farmer, a wolf, a goat and a cabbage.They need to cross a river with the following restrictions:
* The farmer can move from one side to the other freely, and can optionally carry one other entity
* The wolf can’t be on the same side with the goat without the farmer
* The goat can’t stay at the same side with the cabbage without the farmer
The river has two sides L for Left and R for Right.
You are given the initial positions and the target positions, in the following order Farmer, Wolf, Goat, Cabbage. For example you may be given the positions like so
L L L R which would mean that the farmer, wolf, and goat are on the left side and the cabbage is on the right side.
Without breaking the restrictions, print out the minimum legal states starting at the initial state to get to the target state and including the target state.
FOR MULTIPLE SOLUTIONS
If there are multiple solutions with the same length, return the one that is alphabetically first.
Example Input
L L L R
L L L L
Desired Output
L L L R
R L R R
L L R L
R L R L
L L L L
Explanation
L L L R // Starting State
R L R R // Farmer takes goat to right
L L R L // Farmer takes cabbage left
R L R L // Farmer returns to goat
L L L L // Farmer takes goat to left
Input
Line 1: 4 letters representing the initial state
Line 2: 4 letters representing the target state
Line 2: 4 letters representing the target state
Output
Lines: Solution states, starting with the initial state and ending in the target state
Constraints
All problems have a solution, and each solution has fewer than 20 transition states
Example
Input
L L L L R L R L
Output
L L L L R L R L
Tags
BFS, Constraint Propagation
Difficulty
Medium
Test cases
The question is the solution Test
Input
L L L L
R L R L
Output
L L L L
R L R L
The question is the solution Validator
Input
R R R R
L R L R
Output
R R R R
L R L R
The start is the solution Test
Input
L L L R
L L L R
Output
L L L R
The start is the solution Validator
Input
R L R L
R L R L
Output
R L R L
From one side to the other Test
Input
L L L L
R R R R
Output
L L L L
R L R L
L L R L
R L R R
L L L R
R R L R
L R L R
R R R R
From one side to the other Validator
Input
R R R R
L L L L
Output
R R R R
L R L R
R R L R
L L L R
R L R R
L L R L
R L R L
L L L L
Mix it Up Test
Input
R L R L
L R L R
Output
R L R L
L L R L
R L R R
L L L R
R R L R
L R L R
Mix it Up Validator
Input
R L R L
R R L R
Output
R L R L
L L R L
R L R R
L L L R
R R L R
Rescue One Test
Input
L L L R
L L L L
Output
L L L R
R L R R
L L R L
R L R L
L L L L
Rescue One Validator
Input
L R L L
L L L L
Output
L R L L
R R R L
L L R L
R L R L
L L L L
Solution language
Solution
Stub generator input