Newer
Older
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 = []
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]
def undecided(self):
"""The number of choices left on the path"""
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
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}")
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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 += " "