a disfunctional family has to cross the river. on one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. there is a boat only big enough to hold 2 people (counting the dog as 1 person). only the adults are capable of operating the boat. everyone has to get to the other side, without anything bad happening.
difficulties: if the dog is left with anyone and the maid isn’t there to control him, he’ll bite. the dad can’t be left with any of the daughters when the mom isn’t there. likewise, the mom can’t be trusted alone with either of the sons when the dad isn’t there.
remember! only an adult can operate the boat, AND the boat can’t drive itself.
Solution
we start with a mother (m), two daughters (d1, d2), a father (f), two sons (s1, s2), a housemaid (h), and a dog (c – canine) on the west (W) shore, and they all want to get to the east (E) shore.
W = {m, d1, d2, f, s1, s2, h, c} // everyone on the west shore E = {} // no one on the east shore
let’s move everyone, over…
housemaid and canine go east, and the housemaid comes back:
W = {m, d1, d2, f, s1, s2, h} E = {c}
housemaid and s1 go east, h and c come back:
W = {m, d1, d2, f, s2, h, c} E = {s1}
father and s2 go east, father comes back:
W = {m, d1, d2, f, h, c} E = {s1, s2}
mother and father go east, mother comes back:
W = {m, d1, d2, h, c} E = {f, s1, s2}
h and c go east, father comes back:
W = {m, d1, d2, f} E = {s1, s2, h, c}
father and mother go east, mother comes back:
W = {m, d1, d2} E = {f, s1, s2, h, c}
mother and d1 go east, housemaid and c come back:
W = {d2, h, c} E = {m, d1, f, s1, s2}
h and d2 go east, h comes back
W = {h, c} E = {m, d1, d2, f, s1, s2}
h and c go east
W = {} E = {m, d1, d2, f, s1, s2, h, c}
done!
💡Strategies for Solving This Problem
Optimization and State Space Search
Got this at Palantir in 2023. Classic river crossing puzzle that tests graph search, state representation, and constraint satisfaction. Good for showing systematic problem-solving.
The Problem
A farmer needs to cross a river with a fox, chicken, and bag of grain. The boat can only hold the farmer and one other item. Constraints:
If left alone: fox eats chicken
If left alone: chicken eats grain
Farmer must be in boat to row
Find sequence of moves to get everything across safely.
State Representation
Each state = [farmer, fox, chicken, grain] where each is 0 (left) or 1 (right)
Initial: [0, 0, 0, 0] (all on left)
Goal: [1, 1, 1, 1] (all on right)
Approach 1: Trial and Error
Try random moves, backtrack when stuck. Inefficient and may not find optimal solution.
Approach 2: BFS (Breadth-First Search) ✓
Explore all possible moves systematically. Guarantees shortest solution.
Algorithm:
Start with initial state in queue
For each state, generate all valid moves
Check if move violates constraints (fox eats chicken, etc.)
Add valid new states to queue
Track visited states to avoid cycles
Stop when reach goal state
Valid Moves
From each state, farmer can:
Cross alone
Cross with fox
Cross with chicken
Cross with grain
But only if farmer and item are on same side.
Constraint Checking
After each move, check if state is safe:
If fox and chicken on same side without farmer → invalid
If chicken and grain on same side without farmer → invalid
Approach 3: DFS with Backtracking
Try each path deeply before backtracking. Can find solution but not guaranteed to be shortest.
The Solution Sequence
Optimal solution (7 moves):
Take chicken across →
Return alone ←
Take fox across →
Return with chicken ←
Take grain across →
Return alone ←
Take chicken across →
Key insight: Must bring chicken back to prevent it eating grain while bringing fox over.
At Palantir
Interviewer asked me to code the solution. Started with state representation, then implemented BFS with constraint checking. He asked "Why BFS over DFS?" I explained BFS finds shortest path. Then he asked about space complexity and how to optimize.
✅Solution
Solution: BFS with State Space Search
function solveRiverCrossing() {
// State: [farmer, fox, chicken, grain]
// 0 = left bank, 1 = right bank
const initialState = [0, 0, 0, 0];
const goalState = [1, 1, 1, 1];
// Check if state is safe
function isSafe(state) {
const [farmer, fox, chicken, grain] = state;
// Fox and chicken alone on same side
if (fox === chicken && farmer !== fox) return false;
// Chicken and grain alone on same side
if (chicken === grain && farmer !== chicken) return false;
return true;
}
// Generate all possible next states
function getNextStates(state) {
const [farmer, fox, chicken, grain] = state;
const nextStates = [];
// Farmer crosses alone
const alone = [1 - farmer, fox, chicken, grain];
if (isSafe(alone)) nextStates.push(alone);
// Farmer crosses with fox
if (farmer === fox) {
const withFox = [1 - farmer, 1 - fox, chicken, grain];
if (isSafe(withFox)) nextStates.push(withFox);
}
// Farmer crosses with chicken
if (farmer === chicken) {
const withChicken = [1 - farmer, fox, 1 - chicken, grain];
if (isSafe(withChicken)) nextStates.push(withChicken);
}
// Farmer crosses with grain
if (farmer === grain) {
const withGrain = [1 - farmer, fox, chicken, 1 - grain];
if (isSafe(withGrain)) nextStates.push(withGrain);
}
return nextStates;
}
// Convert state to string for Set storage
const stateToString = (state) => state.join(',');
// BFS
const queue = [[initialState, []]]; // [state, path]
const visited = new Set([stateToString(initialState)]);
while (queue.length > 0) {
const [currentState, path] = queue.shift();
// Check if reached goal
if (stateToString(currentState) === stateToString(goalState)) {
return {
success: true,
moves: path.length,
path: path
};
}
// Explore next states
for (const nextState of getNextStates(currentState)) {
const nextKey = stateToString(nextState);
if (!visited.has(nextKey)) {
visited.add(nextKey);
queue.push([nextState, [...path, nextState]]);
}
}
}
return { success: false };
}
// Solve and display
const result = solveRiverCrossing();
if (result.success) {
console.log(`Solution found in ${result.moves} moves!n`);
const items = ['Farmer', 'Fox', 'Chicken', 'Grain'];
console.log('Initial: [0,0,0,0] - All on left bankn');
result.path.forEach((state, i) => {
console.log(`Move ${i + 1}: [${state.join(',')}]`);
// Describe what moved
const prev = i === 0 ? [0,0,0,0] : result.path[i-1];
const moved = [];
moved.push('Farmer');
for (let j = 1; j < 4; j++) {
if (state[j] !== prev[j]) {
moved.push(items[j]);
}
}
const direction = state[0] === 1 ? '→' : '←';
console.log(` ${moved.join(' + ')} crosses ${direction}n`);
});
}
Python Version with Better Output
from collections import deque
def solve_river_crossing():
initial = (0, 0, 0, 0) # farmer, fox, chicken, grain
goal = (1, 1, 1, 1)
def is_safe(state):
farmer, fox, chicken, grain = state
# Fox eats chicken if alone together
if fox == chicken and farmer != fox:
return False
# Chicken eats grain if alone together
if chicken == grain and farmer != chicken:
return False
return True
def get_moves(state):
farmer, fox, chicken, grain = state
moves = []
# Farmer alone
new_state = (1 - farmer, fox, chicken, grain)
if is_safe(new_state):
moves.append((new_state, "Farmer crosses alone"))
# Farmer with fox
if farmer == fox:
new_state = (1 - farmer, 1 - fox, chicken, grain)
if is_safe(new_state):
moves.append((new_state, "Farmer crosses with Fox"))
# Farmer with chicken
if farmer == chicken:
new_state = (1 - farmer, fox, 1 - chicken, grain)
if is_safe(new_state):
moves.append((new_state, "Farmer crosses with Chicken"))
# Farmer with grain
if farmer == grain:
new_state = (1 - farmer, fox, chicken, 1 - grain)
if is_safe(new_state):
moves.append((new_state, "Farmer crosses with Grain"))
return moves
# BFS
queue = deque([(initial, [])])
visited = {initial}
while queue:
state, path = queue.popleft()
if state == goal:
return path
for next_state, move_desc in get_moves(state):
if next_state not in visited:
visited.add(next_state)
queue.append((next_state, path + [(next_state, move_desc)]))
return None
# Solve and display
solution = solve_river_crossing()
if solution:
print("River Crossing Solution:")
print("=" * 50)
print("Initial: All on LEFT bankn")
for i, (state, move) in enumerate(solution, 1):
direction = "→ RIGHT" if state[0] == 1 else "← LEFT"
print(f"Move {i}: {move} {direction}")
print(f" State: {state}")
# Show who's on each side
farmer, fox, chicken, grain = state
left = []
right = []
for j, item in enumerate(['Farmer', 'Fox', 'Chicken', 'Grain']):
if state[j] == 0:
left.append(item)
else:
right.append(item)
print(f" LEFT: {left}")
print(f" RIGHT: {right}n")
print(f"Success! Solved in {len(solution)} moves.")
else:
print("No solution found!")
Expected Output
River Crossing Solution:
==================================================
Initial: All on LEFT bank
Move 1: Farmer crosses with Chicken → RIGHT
State: (1, 0, 1, 0)
LEFT: ['Fox', 'Grain']
RIGHT: ['Farmer', 'Chicken']
Move 2: Farmer crosses alone ← LEFT
State: (0, 0, 1, 0)
LEFT: ['Farmer', 'Fox', 'Grain']
RIGHT: ['Chicken']
Move 3: Farmer crosses with Fox → RIGHT
State: (1, 1, 1, 0)
LEFT: ['Grain']
RIGHT: ['Farmer', 'Fox', 'Chicken']
Move 4: Farmer crosses with Chicken ← LEFT
State: (0, 1, 0, 0)
LEFT: ['Farmer', 'Chicken', 'Grain']
RIGHT: ['Fox']
Move 5: Farmer crosses with Grain → RIGHT
State: (1, 1, 0, 1)
LEFT: ['Chicken']
RIGHT: ['Farmer', 'Fox', 'Grain']
Move 6: Farmer crosses alone ← LEFT
State: (0, 1, 0, 1)
LEFT: ['Farmer', 'Chicken']
RIGHT: ['Fox', 'Grain']
Move 7: Farmer crosses with Chicken → RIGHT
State: (1, 1, 1, 1)
LEFT: []
RIGHT: ['Farmer', 'Fox', 'Chicken', 'Grain']
Success! Solved in 7 moves.
Complexity Analysis
Time Complexity: O(2^N) where N=4 items
Each item can be on left or right: 2^4 = 16 possible states
Many states are invalid (unsafe), so actually fewer
BFS explores each valid state once
Space Complexity: O(2^N)
Queue and visited set can hold all valid states
Path storage is O(solution length)
Optimizations
Bidirectional BFS: Search from both start and goal, meet in middle
A* search: Use heuristic (count of items on wrong side)
State pruning: Detect symmetric states early
Common Mistakes
Forgetting to check safety after EVERY move: Must validate before adding to queue
Not tracking visited states: Will loop forever
Using DFS: May find solution but not shortest
Wrong constraint logic: "Alone" means farmer is NOT there
Follow-up Questions
Add more items (wolf, sheep, cabbage)? Same BFS approach, more states
Boat holds 2 items besides farmer? More possible moves per state
Different constraints? Modify is_safe() function
Minimum number of moves? BFS guarantees this
Count all possible solutions? Remove visited set, count goal states reached
