📋 Problem Description

A helicopter drops two trains, each on a parachute, onto a straight infinite railway line. The distance between the trains is unknown, and both trains face the same direction. When they land, each parachute detaches and stays on the track next to the train.

Each train is controlled by an identical microchip running the same program. The trains:

• Do not know their position on the line
• Do not know the distance between them
• Cannot communicate with each other
• Can only: move forward/backward one unit per time step, or wait
• Can detect when they are at a parachute location (but cannot distinguish which parachute)

Goal: Design an algorithm that guarantees the two trains will eventually collide, no matter how far apart they start.

💡 Algorithm Solution

The Expanding Spiral Search

Each train executes an expanding spiral search pattern from its parachute marker:

• Round 1: Move forward 1 unit → return to parachute → move backward 1 unit → return to parachute
• Round 2: Move forward 2 units → return to parachute → move backward 2 units → return to parachute
• Round 3: Move forward 4 units → return to parachute → move backward 4 units → return to parachute
• Round n: Move forward 2^n-1 units → return → move backward 2^n-1 units → return

Why It Works

The exponential growth (doubling the search distance each round) ensures that eventually, the search radius will exceed the initial distance between the trains. When this happens, one train will be exploring forward while the other is exploring backward (or returning), causing them to collide.

🚀 Getting Started

Prerequisites

• Node.js (v18 or higher)
• npm, yarn, pnpm, or bun

Installation

npm install

Running the Development Server

npm run dev

Open http://localhost:3000 with your browser to see the simulation.

Building for Production

npm run build
npm start

🎮 How to Use

1. Set Initial Distance: Choose how far apart the trains start (1-100 units)
2. Press Play: Watch the trains execute their algorithm step by step
3. Adjust Speed: Control how fast the simulation runs
4. Observe: See the trains explore, return to their parachutes, and eventually collide
5. Reset: Try different starting distances to verify the algorithm always works

🏗️ Project Structure

src/
├── app/
│   ├── page.tsx          # Main application page
│   ├── documentation/    # Documentation page
│   ├── layout.tsx        # Root layout
│   └── globals.css       # Global styles
├── components/
│   ├── Header.tsx              # Navigation header
│   ├── TrainVisualization.tsx  # Visual representation of trains and railway
│   └── ControlPanel.tsx        # UI controls for the simulation
└── lib/
    ├── trainAlgorithm.ts       # Core algorithm logic
    └── simulation.ts           # Simulation state management

🤖 Development with Cursor AI

This project was developed with significant assistance from Cursor AI as the main development assistant. Here's how Cursor AI was utilized:

Algorithm Design

• Brainstorming: Cursor helped explore different algorithmic approaches
• Verification: Discussed the correctness proof and edge cases
• Optimization: Refined the implementation for clarity and efficiency

Code Generation

• Component scaffolding: Generated initial structure for React components
• TypeScript types: Created type-safe interfaces
• Utility functions: Implemented helper functions for calculations

UI/UX Development

• Layout suggestions: Provided recommendations for responsive design
• Styling: Generated Tailwind CSS classes
• Animation: Implemented smooth transitions and effects

🛠️ Technologies Used

• Next.js 16 - React framework with App Router
• React 19 - UI library
• TypeScript - Type safety
• Tailwind CSS 4 - Styling
• Biome - Linting and formatting
• Cloudflare Pages - Deployment platform

🔍 Algorithm Complexity

For trains starting at distance D apart:

• Time complexity: O(D) steps - the trains collide when the search radius reaches D
• Space complexity: O(1) - each train only needs to track its current state
• Rounds to collision: O(log D) - exponential growth means logarithmic number of rounds

📝 Notes on Implementation

Original Work

This implementation was developed from first principles using reasoning and AI assistance. The algorithm was derived by analyzing the problem constraints:

1. Both trains must execute identical programs
2. Trains can only use local information (their parachute position)
3. The solution must work for any initial distance
4. The approach must guarantee eventual collision

The exponential spiral search naturally emerges as a solution that satisfies all these constraints.

🙏 Acknowledgments

• Challenge inspired by classic distributed systems and robotics problems
• Built with Cursor AI as the primary development assistant
• Deployed on Cloudflare Pages