DRMacIver's Notebook

def single_pass_delete(test_case, condition):
    """Returns a version of `test_case` that satisfies `condition` and
    is "one-minimal" in the sense that you cannot delete any single
    member of it and have it still satisfy the condition."""
    test_case = list(test_case)

    def can_delete(j, k):
        return condition(test_case[:j] + test_case[k:])

    i = 0
    while i < len(test_case):
        try:
            # Scan in parallel for the first location where we can delete
            # a single element of the list. If no more elements are deletable
            # this will run with as much parallelism as we can give it.
            i = find_first(range(i, len(test_case), lambda j: can_delete(j, j + 1)
        except NotFound:
            break

        del test_case[i]
        # Now that we've found an area where there's at least one deletable
        # element, we hope that it's part of a large chunk of deletable elements.
        # This finds an integer k so that we can delete the next k elements
        # and not the next k + 1 elements, running in O(log(k)). This hopefully
        # lets us delete a reasonable large chunk at a time.
        k = find_integer(lambda k: i + k <= len(test_case) and can_delete(i, i + k))
        del test_case[i:i+k]

        # Because we chose k such that k + 1 elements are not deletable, we know
        # that the element left at i (if any, we might have deleted the whole list)
        # is now not deletable, so we increment i to skip past it on the next
        # iteration. This is purely a performance optimisation, but in the worst
        # case might cause us to make twice as many calls to `condition` as we
        # need to if we skip it.
        i += 1

    return test_case

import os
from itertools import islice


class NotFound(Exception):
    pass


def find_first(target, predict):
    """Returns the first element of `target` that satisfies `predicate`,
    or raises `NotFound` if none do."""

    if not target:
        raise NotFound()

    parallelism = os.cpu_count()

    if parallelism <= 1:
        for x in target:
            if f(x):
                return x
        raise NotFound()
    else:
        with ThreadPoolExecutor(max_workers=parallelism) as executor:
            it = iter(target)
            chunk_size = 1
            while True:
                chunk = list(islice(it, chunk_size))
                if not chunk:
                    raise NotFound()
                for x, b in zip(chunk, executor.map(f, chunk)):
                    if b:
                        return x
                chunk_size *= 2