instructions.md

instructions.md

Problem Statement

Multiverse wants to enhance their Mars Rover system with the following capabilities:

Part 1: Obstacle Detection

The Mars surface has obstacles that rovers must navigate around. Extend the system to detect collisions with obstacles: when a rover tries to move into an obstacle, it should stop at its current position (not move forward) but continue processing remaining commands.

Note the updated input format: obstacles may be specified in the grid object.

New Input Format:

{
  "grid": {
    "width": 4,
    "height": 8,
    "obstacles": [
      { "x": 1, "y": 2 },
      { "x": 3, "y": 4 }
    ]
  },
  "robots": [
    {
      "initialPosition": { "x": 2, "y": 3, "orientation": "E" },
      "commands": ["L", "F", "R", "F", "F"]
    }
  ]
}

Expected Behavior:

• Rover hits obstacle → stays in place for that F command
• Rover can still rotate (L/R commands work normally)
• Continue processing remaining commands after hitting obstacle

Output Format (JSON):

[{ "x": 2, "y": 4, "orientation": "E", "lost": false }]

• Returns array of robot final states
• Each state includes x, y, orientation, and lost status

Part 2: Multi-Rover Collision Avoidance

Rovers should avoid colliding with each other:

1. Track active rovers: Maintain positions of all non-lost rovers
2. Collision prevention: If a rover tries to move to a position occupied by another rover, it should behave like hitting an obstacle
3. Update movement logic: Check both obstacles and other rover positions

Expected Behavior:

• Process rovers in input order
• Each rover's final position affects subsequent rovers
• Lost rovers don't block positions (they're off the grid)

Part 3: Path Recording

Add functionality to track and return each rover's complete path:

1. Path tracking: Record every position the rover visits (including initial position)
2. Output enhancement: Return both final position and complete path
3. Format: Include path in output format

Output Format (JSON)

[
  {
    "x": 4,
    "y": 4,
    "orientation": "E",
    "lost": false,
    "path": [
      { "x": 2, "y": 3 },
      { "x": 2, "y": 4 },
      { "x": 1, "y": 4 },
      { "x": 2, "y": 4 },
      { "x": 3, "y": 4 },
      { "x": 4, "y": 4 }
    ]
  },
  {
    "x": 0,
    "y": 4,
    "orientation": "W",
    "lost": true,
    "path": [
      { "x": 0, "y": 2 },
      { "x": 0, "y": 3 },
      { "x": 0, "y": 4 }
    ]
  }
]

Part 4: Performance & Edge Cases

Discuss and potentially implement:

1. Large grid optimization: How would you handle a 1000x1000 grid with 100+ rovers?
2. Invalid input handling: What should happen with malformed input?
3. Memory efficiency: How could you optimize memory usage for path tracking?

Technical Requirements

• Maintain existing test compatibility
• Follow TypeScript best practices
• Keep functions pure where possible
• Add appropriate type definitions
• Write at least 2-3 tests for new functionality