Clicking Dials

An old synthesiser has dim = 6 dials. Each dial clicks through the whole-number positions 0 to top = 20; there is nothing between two clicks. Somewhere there is a setting that reproduces a target sound exactly. You can only try a setting and hear how far off it is.

Write dial(f, dim, top, budget) that returns the best setting you can find, as a list of dim whole numbers.

• f(x) takes a list of dim integers from 0 to top and returns the mismatch (lower is better, 0 is the target sound). Anything else raises ValueError. Every call counts, repeats included.
• You may call f at most budget times. One more call raises BudgetExceeded.
• The dials interact: the best position of one dial depends on the others. The mismatch has shallow dips, so there are settings where turning any single dial by one click makes things worse, although they are far from the target.

The tests run dial_in(dial, budget, seed), which hides a synthesiser and reports the mismatch at the setting you return. Try it with Run: print(dial_in(dial, 300, 1)).

How this problem is scored

A setting passes if its mismatch is no higher than the best of budget random settings (the judge draws them itself). Its quality (0 to 100) is logarithmic in mismatch + 1: random search scores 0, the exact target scores 100, and every factor of ten in mismatch + 1 counts the same.

Examples

Input:  dial_in(dial, 300, 1)
Output: {"value": ..., "evaluations": ..., "random_search": ...}
        passes when value <= random_search
Input:  dial_in(lambda f, dim, top, budget: [10] * dim, 300, 1)
Output: fails: the middle of every dial is worse than random search

Constraints

• dim = 6, top = 20, 300 <= budget <= 800
• Use random for any randomness (the tests seed it) and bound loops by evaluations, never by the clock.

Goals

• Search a space of whole-number settings with neighbour moves
• Never pay twice for the same evaluation
• Escape settings where every single click makes things worse