Skip to content
Snippets Groups Projects
rtree.py 3.4 KiB
Newer Older
  • Learn to ignore specific revisions
  • from dataclasses import dataclass
    
    
    
    chrg's avatar
    chrg committed
    class Probe:
        def __init__(self, rtree, path, guess_depth=0):
            """Test an rtree with a path, and optional number of guesses"""
            self.path = path + [True] * guess_depth
            self.depth = guess_depth
            self.reasons = []
    
    chrg's avatar
    chrg committed
    
    
    chrg's avatar
    chrg committed
            def check(reason: str):
                """Check the path or default to false"""
                self.reasons.append(reason)
                return self.undecided() <= 0 and self.path[len(self.reasons) - 1]
    
    chrg's avatar
    chrg committed
            self.input = rtree(check)
    
    chrg's avatar
    chrg committed
        def undecided(self):
            """The number of choices left on the path"""
    
    chrg's avatar
    chrg committed
            return len(self.reasons) - len(self.path)
    
    chrg's avatar
    chrg committed
    
    def reduce(predicate, rtree):
        # Extract the initial reduction probe, from the rightmost branch.
        rp = Probe(rtree, [])
        # Run exponential search after the depest sequence of trues
        # that can be appended to the path without failing the predicate
        depth = 1
        # Invariant: predicate(rp) == True
        while rp.undecided() > 0:
            # Try to probe the with current path extended by trues trues.
            if predicate(rp_ := Probe(rtree, rp.path, depth)):
                rp, depth = rp_, depth * 2
                continue
            # Adjust the depth so that none of them are wasted.
            depth += min(0, rp_.undecided())
            # Perform a binary search, accepting the nessarary trues, and
            # reducing the unknown trues to 1:
            while depth > 1:
                # Prope the rtree with the current path extended by half the depth.
                if predicate(rp_ := Probe(rtree, rp.path, depth // 2)):
                    rp = rp_  # Accept the current path.
                    depth -= depth // 2  # And try the remaining half
                else:
                    depth //= 2  # Half the current trues
            # Store that the next element in the path has to be false
            rp.path.append(False)
        # return the input.
        return rp
    
    
    
    def debug(predicate):
    
    chrg's avatar
    chrg committed
        counter = 0
    
        def newpred(rp):
            nonlocal counter
            counter += 1
            t = predicate(rp.input)
            print(
                f"{counter:02})",
                ", ".join(rp.reasons[len(rp.path) - rp.depth : len(rp.path)]),
            )
            print(f"... P({rp.input!r}) = {t}")
    
            return t
    
        return newpred
    
    
    
    chrg's avatar
    chrg committed
    def latex(
        predicate,
        query_format="Remove {}?".format,
        input_format="\\verb|{}|".format,
        start_count=0,
    ):
        counter = start_count - 1
    
        def newpred(rp):
            nonlocal counter
            counter += 1
            t = predicate(rp.input)
            query = ", ".join(rp.reasons[len(rp.path) - rp.depth : len(rp.path)])
            theck = "true" if t else "false"
    
            print(
                f"{counter:02} & \\verb|{pretty(rp)}| & {query_format(query)} & {input_format(rp.input)} & {theck} \\\\"
            )
            return t
    
        return newpred
    
    
    def pretty(rp):
        from itertools import zip_longest
    
        def binary(a):
            return "1" if a else "0"
    
        return "".join(
            a for a, _ in zip_longest(map(binary, rp.path), rp.reasons, fillvalue="*")
        )
    
    
    def reduce_abc(check) -> str:
        result = ""
        for x in "abcdefghijklmnopqrstuvxyz":
            if not check(f"{x}"):
                result += x
            else:
                result += " "
    
    chrg's avatar
    chrg committed
        return result
    
    
    
    if __name__ == "__main__":
    
    chrg's avatar
    chrg committed
        p = latex(
            lambda e: "a" in e or "p" in e,
            start_count=0,
        )
        input_format = "\\verb|{}|".format
        p(Probe(reduce_abc, []))
        rp = reduce(p, reduce_abc)
        print(f"&& {input_format(rp.input)} & true \\\\")