Order a report agent's sections to keep context small
Your task
A research agent writes a long report as a tree of sections. Before it writes a section, it writes each of that section's subsections in full, one after another, in an order it picks. A finished subsection's summary stays in the context until its parent is written, so the order changes how full the context gets.
Write smallest_peak(sections) that returns the smallest peak context the agent can write the whole report with.
Input and output:
sections: up to 100,000 sections, each[name, parent, notes, summary], in any order. Names are unique non-empty strings. The report itself is the one section whoseparentis"". Every otherparentnames another section, and parents never form a loop.notesis the tokens of the section's own notes, andsummarythe tokens of the summary it leaves behind. Both are whole numbers from 0 to 1,000,000,000.- Return a whole number of tokens.
Rules:
- A section is in progress from the moment the agent starts its first subsection until the section itself is written. For every section in progress, the context holds the summaries of its subsections finished so far.
- Writing a section adds its
notesto what the context already holds. A section with subsections is written after all of them, so all their summaries are there too. - When a section is written, its notes and its subsections' summaries leave the context. Its own summary enters the context only then, as a finished subsection of its parent. The report has no parent, so its summary never counts.
- The peak is the largest number of tokens in the context at any moment. Each section may order its subsections differently. Return the smallest peak over all choices.
Examples
smallest_peak(sections: list[list]) -> intExample 1
Input
smallest_peak([["report", "", 100, 0], ["methods", "report", 300, 400], ["intro", "report", 500, 50]])Output
550Example 2
Input
smallest_peak([["report", "", 1200, 300]])Output
1200Example 3
Input
smallest_peak([["report", "", 200, 0], ["market", "report", 150, 120], ["sizing", "market", 900, 80], ["rivals", "market", 400, 200], ["risks", "report", 700, 60]])Output
900