Evaluate Agents That Generate or Optimize Kernels and Compiler Code

Your team is building an AI system that automatically produces GPU kernel code. The system outputs candidate kernels as arithmetic expressions that compute a single scalar value from one or more input variables. A trusted reference expression, written by an expert, is known to be correct. Before any candidate kernel can be released, it must pass an automated validation step.

You are given a batch of candidate expression strings, the reference expression, and a collection of test cases. For each candidate, you must evaluate the expression on every test case and compare its output to the expected value (which is the result of the reference expression on that test case). A candidate is acceptable only when its result matches the expected value within a relative error of $10^{-5}$ (with an absolute floor of $10^{-12}$ for expected values near zero). In addition, you must count the number of arithmetic operators (+, -, *, /) that appear in the candidate expression. Among all acceptable candidates, the one with the smallest operator count is considered the best. If multiple candidates share the same minimal operator count, choose the one that appears earliest in the input list. If no candidate passes all test cases, return -1.

Each expression string consists of variable names (single lowercase letters a–z), floating-point literals (e.g., 3.14, -0.5, 1e-3), parentheses ( ), and the four binary operators +, -, *, /. Standard precedence and left-associativity apply. Whitespace characters may appear anywhere and should be ignored.

Input Format

• The first line contains an integer M, the number of candidate expressions.
• The next M lines each contain one candidate expression string.
• The following line contains the reference expression string.
• The next line contains an integer T, the number of test cases.
• Each of the next T lines describes one test case. A test case line begins with one or more variable assignments separated by spaces, written as <var>=<value> (e.g., x=2.5). After the assignments, the line ends with the token expected=<value>. All values are standard decimal floating-point numbers.

Output Format

Print a single integer: the 0‑based index of the best acceptable candidate, or -1 if none are acceptable.

Example 1:

Input:
3
x + y
x + y + 0.0
x * y
x + y
1
x=2.0 y=3.0 expected=5.0

Output: 0

Explanation: Candidates 0 and 1 both evaluate to 5.0, matching the expected value. Candidate 0 uses 1 operator, candidate 1 uses 2 operators. Candidate 2 gives 6.0 and is rejected. The best candidate is index 0.

Example 2:

Input:
2
a + b
b + a
a + b
2
a=1.0 b=2.0 expected=3.0
a=-1.0 b=5.0 expected=4.0

Output: 0

Explanation: Both candidates produce the correct outputs on both test cases and each contains exactly 1 operator. The tie is broken by choosing the earlier index, 0.

Example 3:

Input:
2
x + y + 1e-6
x + y
x + y
1
x=1.0 y=2.0 expected=3.0

Output: 1

Explanation: The first candidate yields 3.000001, which is acceptable because the relative error $\frac{|3.000001 - 3.0|}{3.0} \approx 3.33\times 10^{-7}$ is below $10^{-5}$. However, it uses 2 operators, while the second candidate uses only 1 operator and is exactly correct. The best candidate is index 1.

Constraints:

• 1 <= M <= 20
• 1 <= T <= 20
• Each expression string has length at most 200.
• Across all expressions, at most 5 distinct variable names appear.
• All floating-point values fit in a 64-bit double and lie in the range [-1000.0, 1000.0].
• The reference expression is guaranteed to be valid and to avoid division by zero on the provided test cases.