Datacenter Imprisonment

You can now see the teams’ solutions for some tests.

Everyone is using AI, even magicians! But it is too expensive... Merlin, being one of the strongest magicians, hired company Dabius.ai to build a datacenter. The datacenter itself is a square grid of cells, and it is built in the most energy-efficient way possible: the entrance is in the top-left, the exit is in the bottom-right, and empty cells form a tree. So, it is kind a standard old-stylish spooky maze.

Merlin entered that maze, and the doors at the back shut! He found himself trapped and wanted to get out. Unfortunately, he lost the map... Luckily, the maze is also a datacenter which has a cool feature: it can spawn maze-helper agents provided with a code that can communicate with each other and can ask the security system about the maze.

Merlin called you and demanded to write a code for these helper agents while threatening you to tell your boss that all your work is done by AI and you do not even check it!

Formal Statement

You submit a single C++ agent. Merlin (the referee) hides a N×N maze and spawns NUM_AGENTS copies of your agent as separate, isolated processes. The copies must cooperate to discover the unique path from the top-left corner (1,1) to the bottom-right corner (N,N), and have exactly one of them claim it. Claiming the path after fewer turns is better for the score.

You may resubmit at any time — the arena always picks up your latest submission. The contest runs in many rounds; each round runs every team's current agent on the same fresh maze and scores it.

The maze

• Cells are 1-indexed: rows and columns run 1..N.
• Each cell is either empty or a wall.
• Cells are adjacent orthogonally: (r,c) borders (r−1,c) (Up), (r+1,c) (Down), (r,c−1) (Left), and (r,c+1) (Right). A path steps between such neighbours.
• The empty cells form a tree: there is exactly one simple path between any two empty cells. Hence, the path (1,1) → (N,N) is guaranteed to exist and to be unique; (1,1) and (N,N) are always empty.
• The generator's source is provided, but its seed for each round is secret.

Interaction

An agent is a plain process. Merlin writes to the agent's stdin and reads its stdout, one line at a time. Flush after every line you write.

Startup

Once, at the very start, Merlin writes a single line to the agent's stdin:

N NUM_AGENTS AGENT_ID MAX_MSG_LEN

• N — maze size (the maze is N×N),
• NUM_AGENTS — total number of agents participating in the run,
• AGENT_ID — your own 0-based agent id (0 .. NUM_AGENTS-1),
• MAX_MSG_LEN — the maximum message body length in bytes (see > P M below).

Turns

The game runs in lockstep turns. In each turn, every still-alive agent emits exactly one command and then reads exactly one reply line before the next turn begins. No agent can run ahead; everyone advances together.

Commands

• M (message body) is a possibly empty string, ≤ MAX_MSG_LEN bytes. Every byte of M must be printable ASCII, 0x20..0x7E inclusive (space, digits, letters, punctuation, symbols). Tabs, newlines, carriage returns, other control characters, and non-ASCII bytes are forbidden. M is everything after the separator space following P, so it may contain spaces. A message that is too long or contains a byte outside 0x20..0x7E ends the run immediately as a failure.
• - - is the skip reply: no matching message is waiting right now. The turn is a no-op for you; try again next turn.
• . consumes the single command of the agent for the turn and changes nothing. Use it to stay in lockstep while you wait.
• halt permanently removes the agent from the turn rotation: Merlin sends no reply and never prompts again, while the remaining agents play on.
• <ULDR> is the path: a string over U, L, D, R (Up = row−1, Down = row+1, Left = col−1, Right = col+1), walking from (1,1). Every visited cell must be in bounds and empty, no cell may be revisited, and the walk must end at (N,N). When N == 1 the claim is the empty string.

Messages

Each agent has its own incoming message queue. A successful > P M command creates one message (sender = your AGENT_ID, body = M) for agent P. Messages stay queued until the recipient reads them. When Merlin returns a message as <sender> <body>, the body starts after the first space and is returned verbatim, including any spaces inside the original body.

A message sent during turn X becomes readable only in turn X + 1 or later. A < Q or < ? issued in the same turn X will not see it. Messages sent during a turn are delivered in the ascending order of sender AGENT_IDs, after all messages already in the recipient's queue.

A receive command returns at most one message:

• < Q returns and removes the first message in the queue whose sender is Q; messages from other senders stay queued.
• < ? returns and removes the first message in the queue from any sender (the one that has waited longest in the recipient's queue).
• If no matching message is queued, Merlin replies - - and removes nothing.

Time limit

A run has a single wall-clock deadline that starts when the startup line is sent and covers the whole run up to the first claim. If it expires before any agent claims a valid path, the run fails and you score 0 points for that round.

Failure and tolerance

The run ends and you score 0 points if:

• An agent claims a path that isn't the valid (1,1) → (N,N) walk.
• An agent sends a > body longer than MAX_MSG_LEN, or one containing a byte outside 0x20..0x7E.
• No agent produces a valid claim before the time limit.

A single agent dropping out is tolerated — whether it dies (its process exits / EOF on stdout) or bows out voluntarily with halt, the surviving agents keep playing. The run fails only if all agents leave before any valid claim.

Isolation

Each agent runs in its own isolated environment. The only sanctioned channel between agents is > / < through Merlin — do not rely on side channels.

Scoring

Each round, every team's latest agent is run on the same freshly generated maze. Your raw metric for the round is the maximum number of turns any agent took before the claim; fewer is better. If no agent claims a valid path before the time limit, you score 0 points for that round.

Round score is relative to the best (smallest) points among all participants during that round, scaled by that round's maximum score $M_\text{round}$:

$$\text{round score} = M_\text{round} \cdot \frac{\text{best points}}{\text{your points}}$$

$M_\text{round}$ grows exponentially across the contest (see Finals testing): the last round is worth $10\times$ the first, with $M_\text{round}$ rising smoothly in between, and the per-round maxima sum to a problem total of 2400. Your total score for this problem is the sum of your round scores. Resubmitting a stronger agent improves all future rounds; past rounds keep the score of whatever agent was live at the time.

Example

An illustrative 7×7, 3-agent run (the replies do not correspond to any specific seed). Each turn has two rows: agent is what each agent writes to Merlin, merlin is Merlin's reply back.

Constraints

The finals rounds use the configuration below. Exact values may still change, so do not hard-code them.

Finals testing

The finals run for a fixed window with one test row every 10 minutes, each labelled by its run time (14:10, 14:20, …); every 10 minutes Merlin advances to the next row. Shortly after the cutoff for that row, it takes each team's latest accepted submission created by the cutoff and runs all of them on one shared maze. Each test draws N, NUM_AGENTS, and MAX_MSG_LEN as described in Constraints.

Rounds are weighted by their maximum score $M_\text{round}$, which grows exponentially across the window: early rounds carry small weight and each later round is worth a little more, with the final round worth roughly $10\times$ the first. The per-round maxima are small integers and sum to a problem total of 2400, so a team that wins every round scores 2400.

The merlin and maze generator source code is available in merlin-source.zip.

Submission format

A single .cpp file, compiled with g++ -std=c++23 -O2 -pipe -static -s. Compilation must finish within a 30-second compile time limit. On submit, your file is then run on a small maze (a 7×7 maze, 3 agents, a 5-second time limit). It is rejected if it fails to build, exceeds the compile time limit, or doesn't claim a valid path in time. Concretely, the referee runs

timeout 30 g++ -std=c++23 -O2 -pipe -static -s solution.cpp -o agent   # rejected if this exceeds 30 s
merlin --N 7 --NUM_AGENTS 3 --seed 1 --timeout 5.0 --agent-binary agent