def comprehend_problem(problem_spec: str) -> ProblemModel:
    """Use LLM to parse and understand the ICFP problem specification."""

    # Step 1: Summarize the problem
    summary = call_llm(
        model="claude-3-opus",
        prompt=f"""Read the following ICFP contest problem specification
carefully. Provide:
1. A concise summary of the problem
2. The input/output format
3. The scoring function
4. Key constraints
5. Suggested algorithmic approaches (ranked by likely effectiveness)
6. Identification of sub-problems that can be solved independently

Problem specification:
{problem_spec}""",
        temperature=0.2  # Low temp for accurate comprehension
    )

    # Step 2: Decompose into sub-tasks
    subtasks = call_llm(
        model="claude-3-5-sonnet",
        prompt=f"""Based on this problem analysis:
{summary}

Identify independent sub-problems. For each, specify:
- What it takes as input
- What it produces as output
- How it connects to other sub-problems
- Suggested approach""",
        temperature=0.3
    )

    return ProblemModel(summary=summary, subtasks=subtasks)

async def ensemble_strategy_decision(problem_model, current_best):
    """Query multiple models for strategic direction."""
    prompt = f"""Given this problem: {problem_model.summary}
Current best approach scores {current_best.fitness}.
What is the most promising direction for improvement?"""

    responses = await asyncio.gather(
        call_llm_async("claude-3-5-sonnet", prompt),
        call_llm_async("gpt-4o", prompt),
        call_llm_async("gemini-1.5-pro", prompt),
    )

    # Synthesize recommendations
    synthesis = call_llm(
        "claude-3-5-sonnet",
        f"Three AI experts suggested:\n{responses}\nSynthesize the best strategy."
    )
    return synthesis

Score
  ^
  |                                              ......***
  |                                     .........
  |                            .........
  |                    ........
  |            ........
  |        ....
  |    ....
  |  ..
  | .
  |.
  +---------------------------------------------------------> Time (hours)
  0    12     24     36     48     60     72

  Phase 1       Phase 2         Phase 3        Phase 4
  (Comprehend)  (Explore)       (Exploit)      (Polish)
  0-6h          6-24h           24-54h         54-72h

    allocation = {comprehension: 0.05, exploration: 0.40, exploitation: 0.40, polishing: 0.15}
    Budget is front-loaded toward exploration; comprehension is cheap relative to evolution

+============================================================================+
|                SAKANA AI ICFP 2025 EVOLUTIONARY SYSTEM                     |
+============================================================================+
|                                                                            |
|  +---------------------+                                                   |
|  | PROBLEM SPEC INPUT  |                                                   |
|  | (Contest website)    |                                                   |
|  +---------+-----------+                                                   |
|            |                                                               |
|            v                                                               |
|  +---------+-----------+     +---------------------------+                 |
|  | COMPREHENSION MODULE|     |    STRATEGY PLANNER       |                 |
|  | - Parse problem     |---->|    - Decompose problem    |                 |
|  | - Extract scoring   |     |    - Rank approaches      |                 |
|  | - Identify I/O fmt  |     |    - Plan sub-tasks       |                 |
|  | - Model: Opus/GPT4  |     |    - Allocate resources   |                 |
|  +---------------------+     +------------+--------------+                 |
|                                           |                                |
|            +------------------------------+                                |
|            |                                                               |
|            v                                                               |
|  +---------+-------------------------------------------------+             |
|  |              EVOLUTIONARY ENGINE (per sub-problem)        |             |
|  |                                                           |             |
|  |  +----------------+    +------------------+               |             |
|  |  | POPULATION     |    | PARENT SELECTION |               |             |
|  |  | (QD Archive)   |--->| - Tournament     |               |             |
|  |  | - By strategy  |    | - Fitness-prop   |               |             |
|  |  | - By subtask   |    | - Diversity-aware|               |             |
|  |  +-------+--------+    +--------+---------+               |             |
|  |          ^                       |                        |             |
|  |          |                       v                        |             |
|  |  +-------+--------+    +--------+---------+               |             |
|  |  | SURVIVAL       |    | MUTATION ENGINE  |               |             |
|  |  | SELECTION      |    | (Multi-Model LLM)|               |             |
|  |  | - Elitism      |    | - Prompt build   |               |             |
|  |  | - Niche-aware  |    | - API dispatch   |               |             |
|  |  | - Age-based    |    | - Code extract   |               |             |
|  |  +-------+--------+    +--------+---------+               |             |
|  |          ^                       |                        |             |
|  |          |                       v                        |             |
|  |  +-------+--------+    +--------+---------+               |             |
|  |  | SCORER         |    | BUILD & TEST     |               |             |
|  |  | - Local eval   |<---| - Compile        |               |             |
|  |  | - Server submit|    | - Sandbox run    |               |             |
|  |  | - Score parse  |    | - Error capture  |               |             |
|  |  +----------------+    +------------------+               |             |
|  +-----------------------------------------------------------+             |
|                                                                            |
|  +------------------------------------------------------------------+      |
|  | ORCHESTRATION & MONITORING                                        |      |
|  | - Multi-subtask coordination    - Budget tracking                |      |
|  | - Parallel API management       - Convergence detection          |      |
|  | - Error recovery & retry        - Live leaderboard monitoring    |      |
|  | - Phase transitions             - Logging & visualization        |      |
|  +------------------------------------------------------------------+      |
|                                                                            |
|  +------------------------------------------------------------------+      |
|  | CONTEST SERVER INTERFACE                                          |      |
|  | - Solution submission API       - Score retrieval                |      |
|  | - Problem update polling        - Leaderboard scraping           |      |
|  +------------------------------------------------------------------+      |
+============================================================================+

[Problem Spec] --> [Comprehension] --> [Strategy Plan] --> [Sub-task Assignment]
                                                                |
                   +--------------------------------------------+
                   |                    |                        |
                   v                    v                        v
            [Sub-task 1 Evo]    [Sub-task 2 Evo]         [Sub-task N Evo]
                   |                    |                        |
                   v                    v                        v
            [Best Solution 1]   [Best Solution 2]        [Best Solution N]
                   |                    |                        |
                   +--------------------+------------------------+
                                        |
                                        v
                              [Solution Assembler]
                                        |
                                        v
                              [Submit to Contest Server]
                                        |
                                        v
                              [Parse Score & Feedback]
                                        |
                                        v
                              [Feed Back to Population]

class SolutionAssembler:
    def assemble(self, subtask_solutions: dict) -> str:
        """Combine sub-task solutions into final submission."""
        # Use LLM to integrate if sub-tasks interact
        if self.subtasks_interact():
            return self.llm_integrate(subtask_solutions)
        else:
            # Simple concatenation/composition
            return self.compose(subtask_solutions)

"""You are an expert programmer competing in the ICFP contest.

PROBLEM SUMMARY:
{problem_summary}

CURRENT SOLUTION (Score: {score}):
```python
{parent_code}

#### Error-Guided Mutation

if eval_result.status == "WRONG_ANSWER":
    error_context = f"""

return build_mutation_prompt(parent, "error_fix", error_context)

### 10.2 Parent Selection and Sampling

The ICFP system uses the same core selection mechanisms as AHC058 (fitness-proportionate, tournament, diversity-aware) with one addition -- **sub-task-aware selection**:

# Step 1: Choose which sub-task to focus on
# Weight by potential improvement (gap between current and theoretical max)
improvement_potential = {}
for st, pop in populations.items():
    best = max(ind.fitness for ind in pop)
    ceiling = subtask_weights[st]['theoretical_max']
    improvement_potential[st] = (ceiling - best) * subtask_weights[st]['importance']

# Softmax to select sub-task
probs = softmax(list(improvement_potential.values()))
chosen_subtask = np.random.choice(list(populations.keys()), p=probs)

# Step 2: Select parent within chosen sub-task population
return tournament_selection(populations[chosen_subtask])

### 10.3 Population Management

The ICFP system extends the QD archive with **hierarchical structure**:

#### Age-Based Culling

To prevent stale individuals from consuming population slots:

### 10.4 Solution Diversity and Novelty

#### Multi-Dimensional Diversity

The ICFP system tracks diversity across multiple axes:

- **Algorithmic strategy:** What approach (greedy, DP, SA, etc.)
- **Programming language:** Python vs C++ vs others
- **Code structure:** Number of functions, nesting depth, LOC
- **Behavioral profile:** Score distribution across test cases
- **Lineage distance:** How many mutations separate two individuals

#### Diversity Distance Function


$$
d(a, b) = w1 * dstrategy(a,b) + w2 * dbehavioral(a,b) + w3 * dstructural(a,b)
        Weighted combination of strategy (categorical), behavioral (score vector cosine distance), and structural (code diff ratio) distances
$$

# Behavioral distance (cosine distance of score vectors)
a_scores = np.array(a.per_test_scores)
b_scores = np.array(b.per_test_scores)
cosine_sim = np.dot(a_scores, b_scores) / (np.linalg.norm(a_scores) * np.linalg.norm(b_scores) + 1e-8)
d_behav = 1.0 - cosine_sim

# Structural distance (normalized edit distance of code)
d_struct = normalized_levenshtein(a.code, b.code)

return w[0] * d_strat + w[1] * d_behav + w[2] * d_struct

### 10.5 LLM Orchestration and Model Selection

#### Phase-Aware Model Selection

    elif phase == "exploration":
        # Diversify models for diverse solutions
        return random.choice(["claude-3-5-sonnet", "gpt-4o", "gemini-1.5-pro"])

    elif phase == "exploitation":
        # Use best code model for refinement
        if mutation_type in ["parameter_tune", "local_fix"]:
            return "claude-3-haiku"  # cheap
        return "claude-3-5-sonnet"

    elif phase == "polishing":
        # Budget-conscious but quality-focused
        if budget_remaining > 0.1:
            return "claude-3-5-sonnet"
        return "claude-3-haiku"

#### Concurrent API Management

def __init__(self):
    self.semaphores = {
        "claude": asyncio.Semaphore(10),    # max 10 concurrent
        "openai": asyncio.Semaphore(10),
        "google": asyncio.Semaphore(5),
    }
    self.retry_delays = {"claude": 1, "openai": 1, "google": 2}

async def call(self, provider, model, prompt, **kwargs):
    sem = self.semaphores[provider]
    async with sem:
        for attempt in range(3):
            try:
                return await self._raw_call(provider, model, prompt, **kwargs)
            except RateLimitError:
                await asyncio.sleep(self.retry_delays[provider] * (2 ** attempt))
        raise MaxRetriesExceeded()

### 10.6 Search Strategies and Tree Exploration

#### Phase-Based Search Strategy

#### Stagnation Detection and Recovery

def check(self, current_best_fitness):
    self.best_history.append(current_best_fitness)

    if len(self.best_history) < self.patience:
        return False

    recent = self.best_history[-self.patience:]
    improvement = (recent[-1] - recent[0]) / (abs(recent[0]) + 1e-8)
    return improvement < self.min_improvement

def recovery_action(self):
    """Suggest action when stagnation is detected."""
    return random.choice([
        "increase_exploration",      # More strategy-change mutations
        "inject_random_solutions",   # Generate from scratch
        "switch_subtask_focus",      # Work on different sub-task
        "ensemble_strategy_review",  # Ask multiple LLMs for new ideas
    ])

### 10.7 Evaluation and Fitness Assessment

#### Dual Evaluation Modes

def local_eval(self, code):
    """Fast local evaluation on sample test cases."""
    # Compile/interpret
    binary = self.build(code)
    if not binary.success:
        return EvalResult(fitness=0, status="BUILD_FAIL", error=binary.stderr)

    # Run on local test cases
    scores = []
    for tc in self.local_test_cases:
        result = self.run_sandboxed(binary, tc, time_limit=10.0)
        if result.ok:
            scores.append(self.score(result.output, tc))
        else:
            scores.append(0)

    return EvalResult(fitness=np.mean(scores), scores=scores, status="OK")

def server_eval(self, code):
    """Submit to contest server for official scoring."""
    # Only used for promising solutions (expensive/rate-limited)
    response = self.contest_api.submit(code)
    return EvalResult(
        fitness=response.score,
        status="OK",
        server_response=response
    )

#### Tiered Evaluation Strategy


$$
Eval(candidate) =

          Stage 1: Quick local eval on 3 test cases (fast filter)

          Stage 2: Full local eval on all test cases (if Stage 1 promising)

          Stage 3: Server submission (if Stage 2 beats current best)
        Each stage filters out poor candidates, saving evaluation budget for promising ones
$$

### 10.8 Prompt Engineering and Co-Evolution

#### Context-Rich Prompts

ICFP prompts are richer than AHC058 prompts because they must convey the novel problem:

    # Problem understanding (from comprehension phase)
    sections.append(f"## Problem Summary\n{context['problem_summary']}")

    # Scoring function explanation
    sections.append(f"## Scoring\n{context['scoring_explanation']}")

    # Sub-task context
    if context.get('subtask'):
        sections.append(f"## Current Sub-task\n{context['subtask']}")

    # Parent code and performance
    sections.append(f"## Current Solution (Score: {parent.fitness})\n"
        f"```python\n{parent.code}\n```")

    # Population context -- what strategies are working
    sections.append(f"## Population Insights\n"
        f"- Best score overall: {context['best_score']}\n"
        f"- Best strategy: {context['best_strategy']}\n"
        f"- Strategies tried: {context['strategies_tried']}\n"
        f"- Recent improvements came from: {context['recent_improvements']}")

    # Leaderboard context (competitive intelligence)
    if context.get('leaderboard_info'):
        sections.append(f"## Leaderboard\n{context['leaderboard_info']}")

    # Mutation instructions
    sections.append(self.mutation_instructions(mutation_type))

    return "\n\n".join(sections)

#### Leaderboard-Driven Motivation

An innovative technique: the system includes leaderboard position in prompts to "motivate" the LLM:

### 10.9 Cost Control and Budget Management

def __init__(self, total_budget, contest_duration_hours=72):
    self.total = total_budget
    self.spent = 0.0
    self.duration = contest_duration_hours
    self.start_time = time.time()

    # Phase budgets
    self.phase_budgets = {
        "comprehension": total_budget * 0.05,
        "exploration": total_budget * 0.40,
        "exploitation": total_budget * 0.40,
        "polishing": total_budget * 0.15,
    }
    self.phase_spent = {k: 0.0 for k in self.phase_budgets}

def get_current_phase(self):
    elapsed = (time.time() - self.start_time) / 3600
    if elapsed < 6:
        return "comprehension"
    elif elapsed < 24:
        return "exploration"
    elif elapsed < 54:
        return "exploitation"
    else:
        return "polishing"

def can_spend(self, estimated_cost):
    phase = self.get_current_phase()
    phase_remaining = self.phase_budgets[phase] - self.phase_spent[phase]
    total_remaining = self.total - self.spent
    return estimated_cost <= min(phase_remaining, total_remaining)

def get_cost_per_call(self, model):
    # Estimated cost per API call (input + output tokens)
    costs = {
        "claude-3-opus": 0.15,
        "claude-3-5-sonnet": 0.05,
        "gpt-4o": 0.06,
        "gemini-1.5-pro": 0.04,
        "claude-3-haiku": 0.005,
        "gpt-4o-mini": 0.003,
    }
    return costs.get(model, 0.05)

### 10.10 Meta-Level and Self-Improvement

#### Adaptive Phase Transitions

Instead of fixed time-based phase transitions, the system can adaptively shift phases based on evolutionary dynamics:

    elif current_phase == "exploitation":
        # Transition to polishing when improvement rate drops
        improvement_rate = metrics['improvement_rate_per_hour']
        return improvement_rate < 0.001 or metrics['time_elapsed'] > 54

#### Strategy Transfer Across Sub-tasks

    for target_task, target_pop in populations.items():
        if target_task == source_task:
            continue

        # Check if this strategy hasn't been tried in target
        target_strategies = {ind.strategy for ind in target_pop}
        if best.strategy not in target_strategies:
            # Adapt the strategy to the target sub-task
            adapted = llm_adapt_solution(
                source_code=best.code,
                source_task=source_task,
                target_task=target_task
            )
            target_pop.append(adapted)

#### Self-Reflective Evolution

Periodically, the system asks the LLM to analyze the evolutionary run itself:

## 11. Programming Language

### System Implementation

The orchestration framework is implemented in **Python** with:

- `asyncio` for concurrent API and evaluation management
- `aiohttp`/`httpx` for async HTTP calls to LLM APIs and contest server
- `subprocess` for compilation and sandboxed execution
- `numpy` for fitness computation and statistical analysis
- Custom logging and monitoring infrastructure

### Generated Solution Languages

Unlike AHC058 (C++ only), the ICFP system can generate solutions in multiple languages:

| Language | When Preferred | Build Command |
| --- | --- | --- |
| Python 3 | Rapid prototyping, complex logic, string manipulation | `python3 solution.py` |
| C++17 | Performance-critical optimization, heavy computation | `g++ -O2 -std=c++17` |
| Rust | Memory safety + performance (when LLM supports it) | `rustc -O` |
| Haskell/OCaml | Functional programming tasks (ICFP tradition) | `ghc -O2` / `ocamlopt` |

## 12. Memory Management

### Extended Context Requirements

ICFP problems are much larger and more complex than AHC problems, requiring careful context management:

| Context Component | Tokens (est.) | Strategy |
| --- | --- | --- |
| Problem specification (full) | 2,000-10,000 | Compressed summary used after comprehension phase |
| Problem summary | 500-1,500 | Always included in mutations |
| Scoring explanation | 200-500 | Always included |
| Parent code | 500-5,000 | Full code; truncated if >5K tokens |
| Performance data | 200-500 | Summarized scores |
| Population insights | 200-400 | Aggregate statistics only |
| Mutation instructions | 200-500 | Mutation-type specific |
| **Total per mutation** | **2,000-8,500** |  |

### Long-Context for Full-Program Analysis

For complex refactoring, Gemini 1.5 Pro's 1M+ token context is leveraged:

context += "\nAnalyze all solutions, identify what makes the best ones work, and create an improved solution."

return call_llm("gemini-1.5-pro", context, temperature=0.5)