Selecting Code by Behaviour (AlphaCode)

The problem

A model wrote many candidate programs for the same task, and you have few tests. Which to submit? AlphaCode's idea: run all the candidates on extra inputs and group the programs that produce the same outputs. There are many ways to be wrong, but correct programs tend to agree, so they end up in large clusters. You will implement that selection.

programs is a list of Python functions, inputs a list of argument tuples.

The signature

The signature of a program is the tuple of its outputs on every input. If a call raises an exception, the output for that input is the string "error:" + exception class name. Outputs must be hashable: convert lists to tuples.

Example. Five programs meant to compute the absolute value, on the inputs $-2$, $0$ and $3$:

• abs — signature: $(2, 0, 3)$
• x if x >= 0 else -x — signature: $(2, 0, 3)$
• lambda x: x — signature: $(-2, 0, 3)$
• $\sqrt{x^2}$ — signature: $(2.0, 0.0, 3.0)$, equal to $(2, 0, 3)$ in Python
• $1 // x$ (fails at 0) — signature: $(-1, \text{"error:ZeroDivisionError"}, 0)$

Clusters and selection

• cluster(programs, inputs): group program indices with identical signatures. Return the list of clusters (each a list of indices in increasing order), sorted by size, largest first; ties by the smallest index in the cluster.
• select(programs, inputs, budget): one representative per cluster (its smallest index), in cluster order, at most budget of them.

Example. The clusters are [[0, 1, 3], [2], [4]]: three programs that agree, then two loners. With a budget of 2, select returns [0, 2]: the first program of the biggest cluster, and the first of the next one.

What to implement

• signature(program, inputs), cluster(programs, inputs) and select(programs, inputs, budget).

Requirements

• Every program is called on every input exactly once.

Hint

A dict from signature to list of indices, filled while scanning the programs in order, gives the clusters; sort its values by (-len(group), group[0]).