Builds are numbered 1..n. Once a build is bad, every later build is bad too. You have
is_bad(build) -> bool, but each call runs a 20-minute test suite. Return the first bad build (or None
if all are good) using at most ⌈log2(n)⌉ + 1 calls. The harness counts your calls.
Implement first_bad. Input: n: int, is_bad: callable. Returns: int | None.
This code runs before yours (fake clients, clocks and the test harness). You can use its names; don't edit them.
import math
def __harness__(fn, n, first_bad):
calls = {"n": 0}
def is_bad(build):
if not 1 <= build <= n:
raise ValueError(f"build {build} does not exist")
calls["n"] += 1
return first_bad is not None and build >= first_bad
answer = fn(n, is_bad)
return {"answer": answer, "within_budget": calls["n"] <= math.ceil(math.log2(max(n, 1))) + 1}
def first_bad(n: int, is_bad):
for build in range(1, n + 1):
if is_bad(build):
return build
return None
Run executes the public tests. Submit grades against public and hidden tests.
Builds are numbered 1..n. Once a build is bad, every later build is bad too. You have
is_bad(build) -> bool, but each call runs a 20-minute test suite. Return the first bad build (or None
if all are good) using at most ⌈log2(n)⌉ + 1 calls. The harness counts your calls.
Implement first_bad. Input: n: int, is_bad: callable. Returns: int | None.
This code runs before yours (fake clients, clocks and the test harness). You can use its names; don't edit them.
import math
def __harness__(fn, n, first_bad):
calls = {"n": 0}
def is_bad(build):
if not 1 <= build <= n:
raise ValueError(f"build {build} does not exist")
calls["n"] += 1
return first_bad is not None and build >= first_bad
answer = fn(n, is_bad)
return {"answer": answer, "within_budget": calls["n"] <= math.ceil(math.log2(max(n, 1))) + 1}
def first_bad(n: int, is_bad):
for build in range(1, n + 1):
if is_bad(build):
return build
return None
Run executes the public tests. Submit grades against public and hidden tests.