volt
10ec491129
Two test cells opened with sys.path.insert(0, /root/.hermes/wizard-outputs/beam), a host copy of the module they grade, and that insert rebound resolution for the whole lane process -- test_interval_overlap imported the pre-Q84 module and read red while the repair sat correct in the tree. Each cell now binds Path(__file__).resolve().parent and asserts the import landed there. New instrument: q133_verify.py behind CHECK-q133 (5 legs) and q133_oracle.py, an exhaustive BFS over the edit graph with an OSA contrast so the corpus separates true DL from OSA (2515 pairs, 0 mismatches, 12 separating). verify.py: 10 legs, 10 pass, 0 fault. beam/CHECK: 595 tests, 0 failures.
139 lines
4.4 KiB
Python
139 lines
4.4 KiB
Python
#!/usr/bin/env python3
|
|
"""Exhaustive oracle for the Damerau-Levenshtein module in wizard-work/beam.
|
|
|
|
The lane's module computes the Lowrance-Wagner DP. This computes the same
|
|
quantity another way -- breadth-first search over the edit graph, where one
|
|
edge is insert / delete / substitute / transpose-two-adjacent. For short
|
|
strings BFS reaches the target at the true minimum number of operations by
|
|
construction, and it shares no recurrence, table or loop with the DP, so
|
|
agreement is a measurement rather than a transcription.
|
|
|
|
An OSA (restricted optimal-string-alignment) DP is carried as the *contrast*:
|
|
a corpus on which BFS and OSA never disagree cannot tell "true DL" from "OSA",
|
|
and the reading would be vacuous. The numbers below are printed every run so
|
|
that claim is checked rather than asserted.
|
|
|
|
usage: q133_oracle.py MODULE_DIR [CAP]
|
|
prints one JSON line: pairs, decided, beyond_cap, mismatches, examples,
|
|
bfs_vs_osa, classic
|
|
exit: 0 reading produced (mismatches are the caller's to grade), 2 could not
|
|
import the module
|
|
"""
|
|
import itertools
|
|
import json
|
|
import os
|
|
import sys
|
|
from collections import deque
|
|
|
|
CAP_DEFAULT = 3
|
|
|
|
|
|
def neighbours(s, alphabet):
|
|
n = len(s)
|
|
for i in range(n):
|
|
yield s[:i] + s[i + 1:]
|
|
for i in range(n):
|
|
for c in alphabet:
|
|
if c != s[i]:
|
|
yield s[:i] + c + s[i + 1:]
|
|
for i in range(n + 1):
|
|
for c in alphabet:
|
|
yield s[:i] + c + s[i:]
|
|
for i in range(n - 1):
|
|
if s[i] != s[i + 1]:
|
|
yield s[:i] + s[i + 1] + s[i] + s[i + 2:]
|
|
|
|
|
|
def bfs(a, b, alphabet, cap):
|
|
if a == b:
|
|
return 0
|
|
seen = {a}
|
|
q = deque([(a, 0)])
|
|
while q:
|
|
s, d = q.popleft()
|
|
if d >= cap:
|
|
continue
|
|
for t in neighbours(s, alphabet):
|
|
if t == b:
|
|
return d + 1
|
|
if t not in seen:
|
|
seen.add(t)
|
|
q.append((t, d + 1))
|
|
return None
|
|
|
|
|
|
def osa(a, b):
|
|
la, lb = len(a), len(b)
|
|
d = [[0] * (lb + 1) for _ in range(la + 1)]
|
|
for i in range(la + 1):
|
|
d[i][0] = i
|
|
for j in range(lb + 1):
|
|
d[0][j] = j
|
|
for i in range(1, la + 1):
|
|
for j in range(1, lb + 1):
|
|
cost = 0 if a[i - 1] == b[j - 1] else 1
|
|
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost)
|
|
if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
|
|
d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)
|
|
return d[la][lb]
|
|
|
|
|
|
def corpus(alphabet, maxlen):
|
|
out = []
|
|
for n in range(maxlen + 1):
|
|
out.extend("".join(p) for p in itertools.product(alphabet, repeat=n))
|
|
return out
|
|
|
|
|
|
def main():
|
|
if len(sys.argv) < 2:
|
|
print("usage: q133_oracle.py MODULE_DIR [CAP]", file=sys.stderr)
|
|
return 2
|
|
moddir = os.path.abspath(sys.argv[1])
|
|
cap = int(sys.argv[2]) if len(sys.argv) > 2 else CAP_DEFAULT
|
|
sys.path.insert(0, moddir)
|
|
try:
|
|
from damerau_levenshtein import damerau_levenshtein as dl
|
|
except Exception as exc: # noqa: BLE001
|
|
print("could not import damerau_levenshtein from %s: %s" % (moddir, exc),
|
|
file=sys.stderr)
|
|
return 2
|
|
|
|
pairs = decided = beyond = mismatches = bfs_vs_osa = 0
|
|
examples = []
|
|
for alphabet, maxlen in (("ab", 4), ("abc", 3)):
|
|
strings = corpus(alphabet, maxlen)
|
|
for a in strings:
|
|
for b in strings:
|
|
pairs += 1
|
|
want = bfs(a, b, alphabet, cap)
|
|
alt = osa(a, b)
|
|
if want is None:
|
|
beyond += 1
|
|
continue
|
|
decided += 1
|
|
if want != alt:
|
|
bfs_vs_osa += 1
|
|
got = dl(a, b)
|
|
if got != want:
|
|
mismatches += 1
|
|
if len(examples) < 8:
|
|
examples.append([a, b, want, got])
|
|
|
|
classic = []
|
|
for a, b in (("ca", "abc"), ("abcd", "abdc"), ("ab", "ba"), ("teh", "the"),
|
|
("book", "back"), ("abc", "acb"), ("", ""), ("a", "")):
|
|
classic.append([a, b, dl(a, b), bfs(a, b, "abcdehko", cap + 1), osa(a, b)])
|
|
|
|
print(json.dumps({
|
|
"module": os.path.join(moddir, "damerau_levenshtein.py"),
|
|
"cap": cap, "pairs": pairs, "decided": decided, "beyond_cap": beyond,
|
|
"mismatches": mismatches, "examples": examples, "bfs_vs_osa": bfs_vs_osa,
|
|
"classic": classic,
|
|
}, sort_keys=True))
|
|
return 0
|
|
|
|
|
|
if __name__ == "__main__":
|
|
sys.exit(main())
|