Deekshitha08/complexity-verifier

Complexity Verifier Environment

An OpenEnv environment designed to test an AI agent's ability to analyze and determine the time complexity of Python algorithms. The agent is provided with the function code, description, and execution timings at different input scales (N=100, N=1000, N=10000). The agent must predict the Big-O time complexity.

Quick Start

The simplest way to use the Complexity Verifier environment is through the ComplexityVerifierEnv class:

from complexity_verifier import ComplexityVerifierAction, ComplexityVerifierEnv

try:
    # Create environment from Docker image
    env = ComplexityVerifierEnv.from_docker_image("complexity_verifier-env:latest")

    # Reset gives a new random algorithm from the problem bank
    result = env.reset()
    obs = result.observation
    
    print(f"Function: {obs.function_name}")
    print(f"Code:\n{obs.function_code}")
    print(f"Timings: N=100: {obs.timing_n100}ms | N=1000: {obs.timing_n1000}ms | N=10000: {obs.timing_n10000}ms")

    # The agent analyzes the code/timings and makes a prediction
    # Valid predictions: "O(1)", "O(logN)", "O(N)", "O(NlogN)", "O(N^2)"
    prediction = "O(N)"
    
    result = env.step(ComplexityVerifierAction(predicted_complexity=prediction))
    
    print(f"Prediction: {prediction}")
    print(f"Is Correct: {result.observation.is_correct}")
    print(f"Actual Complexity: {result.observation.actual_complexity}")
    print(f"Message: {result.observation.message}")
    print(f"Reward: {result.reward}")

finally:
    # Always clean up
    env.close()

Building the Docker Image

Before using the environment, you need to build the Docker image:

# From project root
docker build -t complexity_verifier-env:latest -f server/Dockerfile .

Environment Details

Observation

ComplexityVerifierObservation: Contains the problem details and metadata:

• —function_code (str): The Python code of the algorithm.
• —function_name (str): The name of the function.
• —sample_input_description (str): Brief description of what the function does.
• —timing_n100 (float): Execution time in milliseconds for N=100.
• —timing_n1000 (float): Execution time in milliseconds for N=1000.
• —timing_n10000 (float): Execution time in milliseconds for N=10000.
• —message (str): Status or feedback message.

Action

ComplexityVerifierAction: Contains the agent's prediction:

• —predicted_complexity (str): Must be one of O(1), O(logN), O(N), O(NlogN), O(N^2).

Reward

The reward structure provides partial credit for "close" guesses:

• —Exact Match: 1.0 reward.
• —Off by one complexity class (e.g. guessed O(NlogN) instead of O(N)): 0.3 reward.
• —Completely incorrect: 0.0 reward.
• —Invalid prediction string: -0.2 reward.

Deploying to Hugging Face Spaces

You can deploy the environment to Hugging Face Spaces using the openenv push command:

# From the environment directory
openenv push --repo-id my-org/complexity-verifier

After deployment, your space will include:

• —Web Interface at /web
• —API Documentation at /docs
• —WebSocket at /ws for low-latency interactions

Advanced Usage

The server supports multiple concurrent WebSocket connections using factory mode. To utilize this, ensure your client connects to a server running the updated app.py.

from complexity_verifier import ComplexityVerifierEnv, ComplexityVerifierAction
from concurrent.futures import ThreadPoolExecutor

def run_episode(client_id: int):
    with ComplexityVerifierEnv(base_url="http://localhost:8000") as env:
        result = env.reset()
        # Make a guess
        result = env.step(ComplexityVerifierAction(predicted_complexity="O(N)"))
        return client_id, result.reward

with ThreadPoolExecutor(max_workers=4) as executor:
    results = list(executor.map(run_episode, range(4)))

Development & Testing

Test the core logic directly without the HTTP wrapper:

python server/complexity_verifier_environment.py

Run the server locally:

uvicorn server.app:app --reload