Problem 627914 · medium · Level 06 Heuristics & Optimization

The Best of Several Sweet Spots

black-box optimization · random restarts · local minima

A coffee roaster has dim settings, each between -5 and 5. Its bitterness landscape has 2 * dim separate sweet spots: around each one, the bitterness grows like a bowl, stretched differently along different settings. The sweet spots differ in quality, and only one of them reaches the best possible cup. You cannot see the landscape; you can only roast and taste.

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

  • f(x) returns how much more bitter the cup at x is than the best possible cup (lower is better, 0 is the best). Every call counts.
  • bounds is [(-5.0, 5.0)] * dim; values outside are pulled back to the edge.
  • You may call f at most budget times. One more call raises BudgetExceeded.
  • The lesser sweet spots bottom out between 0.3 and 2.0.

The tests run taste_test(roast, dim, budget, seed), which hides a landscape and reports the value at the setting you return and whether it lies in the best sweet spot. Try it with Run: print(taste_test(roast, 4, 800, 1)).

How this problem is scored

A setting passes if it is at least as good as the best of budget random settings (the judge draws them itself). Its quality (0 to 100) measures, on a logarithmic scale, how much closer to 0 you get than that random search: every factor of ten counts the same, and 1e-8 or less scores 100. Settling in a lesser sweet spot leaves you at 0.3 or more, which scores very little.

Examples

Input:  taste_test(roast, 4, 800, 1)
Output: {"value": ..., "best_spot": True, "evaluations": 800, "random_search": ...}
        passes when value <= random_search

Constraints

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

Goals

  • Recognise when one local search is not enough
  • Split an evaluation budget between exploring and refining
  • Refine a promising point with an adaptive step size
Starting Python…