pydsa.search

viz_binary_search

viz_binary_search(
    func: Optional[Callable] = None,
    width: Optional[int] = None,
)

Trace a binary search: one bar per step, mid marked ✓/✗ by ok(mid).

Source code in pydsa/search.py

def viz_binary_search(func: Optional[Callable] = None, width: Optional[int] = None):
    """Trace a binary search: one bar per step, mid marked ✓/✗ by ok(mid)."""
    if width is None:
        width = min(100, shutil.get_terminal_size().columns)
    if callable(func):
        return viz_binary_search(width=width)(func)

    def decorator(f: Callable) -> Callable:
        def wrapper(*args: Any, **kwargs: Any) -> Any:
            viz = _Viz(width)
            bound = inspect.signature(f).bind(*args, **kwargs)
            for name, v in bound.arguments.items():
                if callable(v):
                    bound.arguments[name] = _record(viz.calls, v, name)
            args, kwargs = bound.args, bound.kwargs

            def trace(frame: Any, event: str, arg: Any) -> Any:
                if frame.f_code == f.__code__:
                    if event == "line":
                        viz.observe(frame.f_locals)
                    return trace
                back = frame.f_back
                if back is None or back.f_code != f.__code__:
                    return None
                if event == "return" and viz.pending is not None:
                    mid = viz.pending[2]
                    if any(v is mid for v in frame.f_locals.values()):
                        viz.calls.append((mid, arg, frame.f_code.co_name))
                return trace

            old = sys.gettrace()
            sys.settrace(trace)
            try:
                result = f(*args, **kwargs)
            finally:
                sys.settrace(old)
            viz.finish(result)
            return result

        return wrapper

    return decorator

first_true

first_true(
    lo: int, hi: int, ok: Callable[[int], bool]
) -> int

Smallest x in [lo, hi] with ok(x) True; ok is False then True.

Returns hi + 1 when ok is False on the whole range.

Source code in pydsa/search.py

def first_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Smallest x in [lo, hi] with ok(x) True; ok is False then True.

    Returns hi + 1 when ok is False on the whole range."""
    return lo + bisect_left(range(lo, hi + 1), True, key=ok)

last_true

last_true(
    lo: int, hi: int, ok: Callable[[int], bool]
) -> int

Largest x in [lo, hi] with ok(x) True; ok is True then False.

Returns lo - 1 when ok is False on the whole range.

Source code in pydsa/search.py

def last_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Largest x in [lo, hi] with ok(x) True; ok is True then False.

    Returns lo - 1 when ok is False on the whole range."""
    return first_true(lo, hi, lambda x: not ok(x)) - 1

first_false

first_false(
    lo: int, hi: int, ok: Callable[[int], bool]
) -> int

Smallest x in [lo, hi] with ok(x) False; ok is True then False.

Returns hi + 1 when ok is True on the whole range.

Source code in pydsa/search.py

def first_false(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Smallest x in [lo, hi] with ok(x) False; ok is True then False.

    Returns hi + 1 when ok is True on the whole range."""
    return first_true(lo, hi, lambda x: not ok(x))

last_false

last_false(
    lo: int, hi: int, ok: Callable[[int], bool]
) -> int

Largest x in [lo, hi] with ok(x) False; ok is False then True.

Returns lo - 1 when ok is True on the whole range.

Source code in pydsa/search.py

def last_false(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Largest x in [lo, hi] with ok(x) False; ok is False then True.

    Returns lo - 1 when ok is True on the whole range."""
    return first_true(lo, hi, ok) - 1

min_chunks

min_chunks(nums: list[int], cap: int) -> float

Fewest contiguous chunks of nums with every chunk summing to at most cap.

Greedy: extend the current chunk while it fits, cut when the next number would push it past cap. Returns inf when a single number exceeds cap.

Source code in pydsa/search.py

def min_chunks(nums: list[int], cap: int) -> float:
    """Fewest contiguous chunks of nums with every chunk summing to at most cap.

    Greedy: extend the current chunk while it fits, cut when the next number
    would push it past cap. Returns inf when a single number exceeds cap."""
    total = 0
    chunks = 1
    for n in nums:
        if n > cap:
            return inf
        if total + n > cap:
            chunks += 1
            total = n
        else:
            total += n
    return chunks