The River Crossing Problem

The River Crossing Problem, inspired by Allen Downey’s “The Little Book of Semaphores,” demonstrates constrained group formation and safety-critical synchronization. It models scenarios where groups must form under specific rules before proceeding - common in distributed systems and resource allocation.

The Scenario

A river crossing with:

Two types of people: Hackers (H) and Employees (E)
A boat that holds exactly 4 people
Random arrivals on the riverbank

Safety rules for boarding:

Boat must have exactly 4 people to cross
Valid combinations:
- 4 Hackers (HHHH)
- 4 Employees (EEEE)
- 2 Hackers + 2 Employees (HHEE)
Invalid combinations (unsafe):
- 3 Hackers + 1 Employee (HHH+E)
- 1 Hacker + 3 Employees (H+EEE)

The challenge: Coordinate arrivals so everyone crosses safely without deadlock or starvation.

The Puzzle: Safe Group Formation

graph TD W[Waiting on Bank] --> D{Enough for Valid Group?} D -->|4 Hackers| B1[HHHH boards] D -->|4 Employees| B2[EEEE boards] D -->|2H + 2E| B3[HHEE boards] D -->|Not yet| W B1 --> Cross[Boat Crosses] B2 --> Cross B3 --> Cross Cross --> Empty[Boat Returns Empty] Empty --> W style B1 fill:#FF6B6B style B2 fill:#4ECDC4 style B3 fill:#FFD93D style W fill:#95E1D3

Tricky scenarios:

3 Hackers waiting → Need 1 more Hacker OR 2 Employees
1 Hacker + 1 Employee → Need 3 more of either OR 1H+1E
3 Employees waiting → Need 1 more Employee OR 2 Hackers

Real-World Applications

This pattern appears in many systems:

Transaction batching: Group transactions with compatibility rules
Vehicle pooling: Carpooling with passenger type constraints
Packet aggregation: Combine packets with protocol requirements
Resource allocation: Allocate resources to compatible groups
Task scheduling: Batch tasks with dependency constraints
Elevator systems: Group passengers by destination zones

Valid Combinations Diagram

stateDiagram-v2 [*] --> Waiting Waiting --> HHHH: 4 Hackers available Waiting --> EEEE: 4 Employees available Waiting --> HHEE: 2 Hackers + 2 Employees HHHH --> Crossing EEEE --> Crossing HHEE --> Crossing Crossing --> [*]: Cross river note right of HHHH ⚫⚫⚫⚫ All hackers end note note right of EEEE 🔵🔵🔵🔵 All employees end note note right of HHEE ⚫⚫🔵🔵 Mixed (balanced) end note

Implementation in Go

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"sync/atomic"
	"time"
)

type PersonType int

const (
	Hacker PersonType = iota
	Employee
)

func (p PersonType) String() string {
	if p == Hacker {
		return "Hacker"
	}
	return "Employee"
}

func (p PersonType) Emoji() string {
	if p == Hacker {
		return "⚫"
	}
	return "🔵"
}

type RiverCrossing struct {
	hackersWaiting   int
	employeesWaiting int

	mu             sync.Mutex
	boatReady      *sync.Cond
	hackersQueue   chan int
	employeesQueue chan int

	// Statistics
	crossings      atomic.Int64
	hackersCrossed atomic.Int64
	employeesCrossed atomic.Int64
}

func NewRiverCrossing() *RiverCrossing {
	rc := &RiverCrossing{
		hackersQueue:   make(chan int, 10),
		employeesQueue: make(chan int, 10),
	}
	rc.boatReady = sync.NewCond(&rc.mu)
	return rc
}

// Person arrives at river and waits to cross
func (rc *RiverCrossing) Person(personType PersonType, id int) {
	// Random arrival
	time.Sleep(time.Duration(rand.Intn(200)) * time.Millisecond)

	fmt.Printf("%s [%s %d] Arrived at riverbank (waiting: ⚫ %d, 🔵 %d)\n",
		personType.Emoji(), personType, id, rc.hackersWaiting, rc.employeesWaiting)

	rc.mu.Lock()

	// Join waiting queue
	if personType == Hacker {
		rc.hackersWaiting++
	} else {
		rc.employeesWaiting++
	}

	// Check if we can form a valid boat
	for !rc.canFormBoat() {
		rc.boatReady.Wait()
	}

	// We can form a boat! Determine our role
	combination := rc.selectCombination()

	if rc.isPartOfCombination(personType, combination) {
		if personType == Hacker {
			rc.hackersWaiting--
		} else {
			rc.employeesWaiting--
		}

		rc.mu.Unlock()

		// Board the boat
		rc.boardBoat(personType, id, combination)
	} else {
		// Not part of this boat, keep waiting
		rc.mu.Unlock()
	}
}

// canFormBoat checks if valid combination is possible
func (rc *RiverCrossing) canFormBoat() bool {
	h := rc.hackersWaiting
	e := rc.employeesWaiting

	// Valid combinations:
	return (h >= 4) ||          // 4 hackers
		(e >= 4) ||             // 4 employees
		(h >= 2 && e >= 2)      // 2 of each
}

// selectCombination chooses which combination to form
func (rc *RiverCrossing) selectCombination() string {
	h := rc.hackersWaiting
	e := rc.employeesWaiting

	// Priority: balanced > homogeneous
	if h >= 2 && e >= 2 {
		return "HHEE"
	} else if h >= 4 {
		return "HHHH"
	} else if e >= 4 {
		return "EEEE"
	}

	return ""
}

// isPartOfCombination checks if person type is in selected combination
func (rc *RiverCrossing) isPartOfCombination(personType PersonType, combination string) bool {
	// Simple check based on combination string
	if combination == "HHHH" && personType == Hacker {
		return true
	}
	if combination == "EEEE" && personType == Employee {
		return true
	}
	if combination == "HHEE" {
		return true // Both types needed
	}
	return false
}

// boardBoat handles the boarding and crossing logic
func (rc *RiverCrossing) boardBoat(personType PersonType, id int, combination string) {
	// Simplified: just record the crossing
	if personType == Hacker {
		rc.hackersCrossed.Add(1)
	} else {
		rc.employeesCrossed.Add(1)
	}

	fmt.Printf("%s [%s %d] ⛴️  Boarding boat (%s)\n",
		personType.Emoji(), personType, id, combination)

	// Simulate crossing
	time.Sleep(200 * time.Millisecond)

	fmt.Printf("%s [%s %d] ✓ Crossed river\n", personType.Emoji(), personType, id)

	// Wake up waiting people for next boat
	rc.boatReady.Broadcast()
}

// Stats prints statistics
func (rc *RiverCrossing) Stats() {
	fmt.Println("\n📊 River Crossing Statistics:")
	fmt.Printf("   Total crossings:     %d\n", rc.crossings.Load())
	fmt.Printf("   ⚫ Hackers crossed:   %d\n", rc.hackersCrossed.Load())
	fmt.Printf("   🔵 Employees crossed: %d\n", rc.employeesCrossed.Load())
	fmt.Printf("   Total people:        %d\n",
		rc.hackersCrossed.Load()+rc.employeesCrossed.Load())
}

func main() {
	fmt.Println("=== The River Crossing Problem ===")
	fmt.Println("Constrained group formation\n")

	const (
		numHackers   = 8
		numEmployees = 8
	)

	crossing := NewRiverCrossing()

	var wg sync.WaitGroup

	// Hackers arrive
	for i := 0; i < numHackers; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			crossing.Person(Hacker, id)
		}(i)
	}

	// Employees arrive
	for i := 0; i < numEmployees; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			crossing.Person(Employee, id)
		}(i)
	}

	wg.Wait()

	crossing.Stats()
	fmt.Println("\n✓ Simulation complete!")
}

How It Works

1. Waiting Count Tracking

hackersWaiting   int
employeesWaiting int

// Update under mutex
mu.Lock()
if personType == Hacker {
    hackersWaiting++
} else {
    employeesWaiting++
}
mu.Unlock()

Track available people for forming boats.

2. Valid Combination Check

func canFormBoat() bool {
    h := hackersWaiting
    e := employeesWaiting

    return (h >= 4) ||         // HHHH
           (e >= 4) ||         // EEEE
           (h >= 2 && e >= 2)  // HHEE
}

Simple predicate to check if any valid combination exists.

3. Combination Selection Strategy

func selectCombination() string {
    // Prefer balanced (prevents starvation)
    if h >= 2 && e >= 2 {
        return "HHEE"
    } else if h >= 4 {
        return "HHHH"
    } else if e >= 4 {
        return "EEEE"
    }
}

Key insight: Prefer mixed boats to prevent starvation of minority type!

4. Broadcast Wake-Up

for !canFormBoat() {
    boatReady.Wait()
}

// After boarding
boatReady.Broadcast()  // Wake all to recheck

All waiters wake up to see if they can form next boat.

Advanced: Coordinator-Based Approach

More sophisticated implementation with explicit coordinator:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type Boat struct {
	id          int
	hackers     []int
	employees   []int
	ready       chan struct{}
	crossed     chan struct{}
}

func NewBoat(id int) *Boat {
	return &Boat{
		id:        id,
		hackers:   make([]int, 0, 4),
		employees: make([]int, 0, 4),
		ready:     make(chan struct{}),
		crossed:   make(chan struct{}, 4),
	}
}

func (b *Boat) IsFull() bool {
	return len(b.hackers)+len(b.employees) == 4
}

func (b *Boat) IsValid() bool {
	h := len(b.hackers)
	e := len(b.employees)
	return (h == 4 && e == 0) ||
		(h == 0 && e == 4) ||
		(h == 2 && e == 2)
}

func (b *Boat) AddPerson(personType PersonType, id int) bool {
	if b.IsFull() {
		return false
	}

	if personType == Hacker {
		b.hackers = append(b.hackers, id)
	} else {
		b.employees = append(b.employees, id)
	}

	return true
}

func (b *Boat) Cross() {
	fmt.Printf("\n⛴️  [Boat %d] Crossing with: ⚫×%d 🔵×%d\n",
		b.id, len(b.hackers), len(b.employees))

	time.Sleep(300 * time.Millisecond)

	fmt.Printf("⛴️  [Boat %d] ✓ Reached other side\n", b.id)

	// Signal all passengers
	for range b.hackers {
		b.crossed <- struct{}{}
	}
	for range b.employees {
		b.crossed <- struct{}{}
	}
}

type RiverCoordinator struct {
	hackersWaiting  chan int
	employeesWaiting chan int
	boatsLaunched   atomic.Int64

	mu sync.Mutex
}

func NewRiverCoordinator() *RiverCoordinator {
	return &RiverCoordinator{
		hackersWaiting:  make(chan int, 20),
		employeesWaiting: make(chan int, 20),
	}
}

// Coordinator forms valid boats
func (rc *RiverCoordinator) Coordinator() {
	boatID := 0

	for {
		boat := NewBoat(boatID)
		boatID++

		fmt.Println("\n🛥️  [Coordinator] Waiting to form boat...")

		// Try to form valid boat
		rc.formBoat(boat)

		if boat.IsValid() && boat.IsFull() {
			fmt.Printf("🛥️  [Coordinator] Boat %d formed! Launching...\n", boat.id)
			go boat.Cross()
		}
	}
}

func (rc *RiverCoordinator) formBoat(boat *Boat) {
	h := len(rc.hackersWaiting)
	e := len(rc.employeesWaiting)

	fmt.Printf("   [Coordinator] Assessing: ⚫ %d hackers, 🔵 %d employees waiting\n", h, e)

	// Determine strategy
	if h >= 2 && e >= 2 {
		// Form mixed boat (HHEE)
		rc.addToBoat(boat, Hacker, 2)
		rc.addToBoat(boat, Employee, 2)
		fmt.Println("   [Coordinator] Strategy: Mixed boat (HHEE)")

	} else if h >= 4 {
		// Form hacker boat (HHHH)
		rc.addToBoat(boat, Hacker, 4)
		fmt.Println("   [Coordinator] Strategy: All hackers (HHHH)")

	} else if e >= 4 {
		// Form employee boat (EEEE)
		rc.addToBoat(boat, Employee, 4)
		fmt.Println("   [Coordinator] Strategy: All employees (EEEE)")

	} else {
		// Wait for more people
		fmt.Println("   [Coordinator] Not enough for valid boat, waiting...")
		time.Sleep(100 * time.Millisecond)
		rc.formBoat(boat) // Recursive retry
	}
}

func (rc *RiverCoordinator) addToBoat(boat *Boat, personType PersonType, count int) {
	for i := 0; i < count; i++ {
		var id int
		if personType == Hacker {
			id = <-rc.hackersWaiting
			boat.AddPerson(Hacker, id)
			fmt.Printf("   [Coordinator] ⚫ Hacker %d boarded\n", id)
		} else {
			id = <-rc.employeesWaiting
			boat.AddPerson(Employee, id)
			fmt.Printf("   [Coordinator] 🔵 Employee %d boarded\n", id)
		}
	}
}

func (rc *RiverCoordinator) Person(personType PersonType, id int) {
	time.Sleep(time.Duration(id*50) * time.Millisecond)

	fmt.Printf("%s [%s %d] Arrived, joining queue\n",
		personType.Emoji(), personType, id)

	if personType == Hacker {
		rc.hackersWaiting <- id
	} else {
		rc.employeesWaiting <- id
	}
}

func RunCoordinator() {
	fmt.Println("\n=== Coordinator-Based Approach ===\n")

	coordinator := NewRiverCoordinator()

	// Start coordinator
	go coordinator.Coordinator()

	var wg sync.WaitGroup

	// Arrivals
	for i := 0; i < 6; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			coordinator.Person(Hacker, id)
		}(i)

		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			coordinator.Person(Employee, id+100)
		}(i)
	}

	// Let simulation run
	time.Sleep(5 * time.Second)

	fmt.Println("\n✓ Coordinator simulation complete!")
}

func main() {
	RunCoordinator()
}

Deadlock Prevention

Potential deadlock scenario:

3 Hackers waiting
3 Employees waiting
Each group waits for 1 more of their type
Nobody can form valid boat!

Solutions:

1. Prefer Mixed Boats

if h >= 2 && e >= 2 {
    return "HHEE"  // Use both types
}

2. Timeout and Reassess

select {
case <-boatReady:
    // Boat formed
case <-time.After(5 * time.Second):
    // Timeout, try different strategy
    rc.tryAlternativeCombination()
}

3. Global Coordinator

Central authority makes decisions, prevents local deadlocks.

Starvation Prevention

Starvation scenario:

2 Hackers + 10 Employees
Employees keep forming EEEE boats
Hackers wait forever!

Prevention strategies:

1. Fair Scheduling

// Track wait time
waitingSince := time.Now()

// Priority boost for long waits
if time.Since(waitingSince) > threshold {
    increasePriority()
}

2. Mandatory Mixed Boats

// Force mixed boat every N crossings
if crossings % 3 == 0 && canFormMixed() {
    return "HHEE"  // Force fairness
}

Crossing Sequence Diagram

sequenceDiagram participant H1 as Hacker 1 participant H2 as Hacker 2 participant E1 as Employee 1 participant E2 as Employee 2 participant Coord as Coordinator participant Boat H1->>Coord: Arrive H2->>Coord: Arrive E1->>Coord: Arrive Note over Coord: 2H + 1E
Cannot form boat yet E2->>Coord: Arrive Note over Coord: 2H + 2E
Can form HHEE! Coord->>Boat: Form boat (HHEE) Boat->>H1: Board Boat->>H2: Board Boat->>E1: Board Boat->>E2: Board Boat->>Boat: Cross river Boat->>H1: Arrived Boat->>H2: Arrived Boat->>E1: Arrived Boat->>E2: Arrived

Key Go Patterns

1. Condition-Based Group Formation

for !canFormValidGroup() {
    condition.Wait()
}

// Form group
selectMembers()

2. Multi-Type Queuing

hackersQueue := make(chan int, capacity)
employeesQueue := make(chan int, capacity)

// Select based on strategy
select {
case h := <-hackersQueue:
    addToBoat(h)
case e := <-employeesQueue:
    addToBoat(e)
}

3. Broadcast for Group Coordination

// One person triggers boat formation
if canLaunchBoat() {
    boatReady.Broadcast()  // Wake all candidates
}

Performance Considerations

Throughput Optimization

Throughput = Boats_Per_Hour * 4

Maximize throughput:

Minimize waiting time between boats
Prefer combinations that clear queues
Launch multiple boats if possible

Fairness vs Efficiency Trade-off

Pure efficiency (maximize boats):

Always launch homogeneous boats
Minority type may starve

Pure fairness (equal crossings):

Force mixed boats
May waste time waiting

Balanced approach:

Prefer mixed when possible
Use homogeneous to prevent blocking
Track and adjust based on wait times

Variations

1. Three or More Types

// Hackers, Employees, Interns
// Valid: HHHH, EEEE, IIII, HHEE, HHII, EEII
func canFormBoat(h, e, i int) bool {
    return (h==4) || (e==4) || (i==4) ||
           (h==2 && e==2) ||
           (h==2 && i==2) ||
           (e==2 && i==2)
}

2. Variable Capacity Boats

// Boats of size 2, 4, or 6
type Boat struct {
    capacity int  // Varies
}

// Adjust valid combinations per capacity

3. One-Way vs Round-Trip

// Boat must return
func (b *Boat) RoundTrip() {
    b.Cross()        // To other side
    b.ReturnEmpty()  // Back to start
}

Advantages of This Pattern

✓ Safety guaranteed - Invalid combinations prevented ✓ Flexible grouping - Multiple valid combinations ✓ Deadlock-free (with proper design) ✓ Fairness achievable - With priority adjustments

When to Use

✓ Use when:

Groups must form under constraints
Safety rules must be enforced
Multiple valid combinations exist
Fairness required

✗ Avoid when:

No grouping constraints
Single-type resources
Groups can be arbitrary
Strict ordering required

Try It Yourself

Three types - Add “Interns” with new rules
Priority system - VIP passengers board first
Multiple boats - Run 2-3 boats simultaneously
Deadlock scenario - Test with 3H + 3E
Measure fairness - Track wait times per type

This is part 16 of “Golang Experiments: Classic Concurrency Problems”

The River Crossing Problem#

The Scenario#

The Puzzle: Safe Group Formation#

Real-World Applications#

Valid Combinations Diagram#

Implementation in Go#

How It Works#

1. Waiting Count Tracking#

2. Valid Combination Check#

3. Combination Selection Strategy#

4. Broadcast Wake-Up#

Advanced: Coordinator-Based Approach#

Deadlock Prevention#

1. Prefer Mixed Boats#

2. Timeout and Reassess#

3. Global Coordinator#

Starvation Prevention#

1. Fair Scheduling#

2. Mandatory Mixed Boats#

Crossing Sequence Diagram#

Key Go Patterns#

1. Condition-Based Group Formation#

2. Multi-Type Queuing#

3. Broadcast for Group Coordination#

Performance Considerations#

Throughput Optimization#

Fairness vs Efficiency Trade-off#

Variations#

1. Three or More Types#

2. Variable Capacity Boats#

3. One-Way vs Round-Trip#

Advantages of This Pattern#

When to Use#

Try It Yourself#