Hire-assistant in Python
Interview each candidate and hire whenever one beats the current best; expected hires are H_n.
- File
hire_assistant.py, 39 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hire-assistant/. The authors are listed in prov/9RHJGA.jsonl.
import random
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def hire_assistant(candidates: list[T]) -> list[int]:
"""Return the 0-based positions of the hires, in order.
A candidate is hired when it is strictly better than every earlier
candidate. The last position in the result is the position of the best
candidate (the first one, if several are equal and best).
"""
hires: list[int] = []
best = -1 # @line L1
for i in range(len(candidates)): # @line L2
c = candidates[i] # @line L3
if best < 0 or candidates[best] < c: # @line L4
best = i # @line L5
hires.append(i) # @line L6
return hires
def randomized_hire_assistant(
candidates: list[T], rng: random.Random | None = None
) -> list[T]:
"""Shuffle the candidates, run hire_assistant, and return the hired candidates in order."""
rng = rng if rng is not None else random.Random()
order = list(candidates)
rng.shuffle(order)
return [order[i] for i in hire_assistant(order)]
test_hire_assistant.py 46 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hire-assistant/. The authors are listed in prov/9RHJGA.jsonl.
import itertools
import random
from fractions import Fraction
from hire_assistant import hire_assistant, randomized_hire_assistant
def test_example() -> None:
assert hire_assistant([5, 2, 8, 6, 9, 1, 10, 3, 7, 4]) == [0, 2, 4, 6]
def test_edges() -> None:
assert hire_assistant([]) == []
assert hire_assistant([7]) == [0]
assert hire_assistant([1, 2, 3, 4]) == [0, 1, 2, 3]
assert hire_assistant([4, 3, 2, 1]) == [0]
assert hire_assistant([2, 2, 2]) == [0]
assert hire_assistant([1, 3, 3, 2]) == [0, 1]
def test_against_brute_force() -> None:
rng = random.Random(1)
for _ in range(300):
a = [rng.randrange(20) for _ in range(rng.randrange(15))]
want = [i for i in range(len(a)) if all(a[j] < a[i] for j in range(i))]
assert hire_assistant(a) == want
if a:
assert a[hire_assistant(a)[-1]] == max(a)
def test_mean_is_harmonic() -> None:
for n in range(1, 7):
total = sum(len(hire_assistant(list(p))) for p in itertools.permutations(range(n)))
count = sum(1 for _ in itertools.permutations(range(n)))
assert Fraction(total, count) == sum(Fraction(1, i) for i in range(1, n + 1))
def test_randomized() -> None:
rng = random.Random(2)
hired = randomized_hire_assistant(list(range(50)), rng)
assert hired[-1] == 49
assert hired == sorted(hired)
assert len(set(hired)) == len(hired)
What the next level needs
- the tests did not run in this build