248 lines
9.2 KiB
Python
248 lines
9.2 KiB
Python
"""Numeral system induction: recover morpheme values + combination structure
|
||
from attested (numeral phrase, integer) pairs, then convert both directions.
|
||
|
||
Model (covers the large majority of IOL numeral systems):
|
||
value(phrase) = fold over tokens, where adjacent (multiplier, base-power)
|
||
groups combine multiplicatively and groups combine additively — i.e. the
|
||
standard "mixed-radix polynomial" reading: [2] [20] [3] -> 2*20 + 3.
|
||
Some systems are subtractive or overcounting; a signed-additive variant is
|
||
also searched. Token values are solved by constraint search: each distinct
|
||
token gets an unknown integer value; attested equations constrain them.
|
||
|
||
Search is tiny: numeral puzzles use ~5-15 morpheme types with values drawn
|
||
from {1..9, base, base^2, ...}. We enumerate candidate value sets per token
|
||
from divisors/residues of the attested numbers, then DFS with propagation.
|
||
"""
|
||
|
||
from __future__ import annotations
|
||
|
||
import re
|
||
from collections import Counter
|
||
from typing import Dict, List, Optional, Sequence, Tuple
|
||
|
||
from .preprocess import strip_punct, tokenize
|
||
|
||
BASES = (10, 20, 5, 12, 60, 4, 6, 8, 15)
|
||
MAX_TOKEN_VALUE = 10_000
|
||
|
||
|
||
def _norm_tokens(phrase: str) -> List[str]:
|
||
toks = []
|
||
for t in tokenize(phrase.casefold()):
|
||
t = strip_punct(t)
|
||
# split on hyphens: numeral compounds are often hyphenated
|
||
toks.extend([p for p in re.split(r"[-‑]", t) if p])
|
||
return toks
|
||
|
||
|
||
def _eval(vals: Sequence[int]) -> int:
|
||
"""Evaluate token values with the multiplicative-additive convention: a
|
||
smaller value directly before a larger one multiplies it; otherwise
|
||
values add. E.g. [2,20,3] -> 2*20+3 = 43; [3,100,20,7] -> 327."""
|
||
total = 0
|
||
cur = vals[0]
|
||
for prev, v in zip(vals, vals[1:]):
|
||
if v > prev:
|
||
cur = cur * v # e.g. 2 then 20 -> 40
|
||
else:
|
||
total += cur
|
||
cur = v
|
||
return total + cur
|
||
|
||
|
||
class NumeralSystem:
|
||
def __init__(self, values: Dict[str, int]):
|
||
self.values = dict(values)
|
||
|
||
def text_to_num(self, phrase: str) -> Optional[int]:
|
||
toks = _norm_tokens(phrase)
|
||
if not toks or any(t not in self.values for t in toks):
|
||
return None
|
||
return _eval([self.values[t] for t in toks])
|
||
|
||
def num_to_text(self, n: int, attested_phrases: Sequence[str]) -> Optional[str]:
|
||
"""Generate the phrase for n: enumerate token sequences (up to length
|
||
6) whose evaluation equals n, then pick the one most consistent with
|
||
the attested phrasing style (e.g. do multi-token phrases always give
|
||
a base its explicit multiplier, even 'one'?)."""
|
||
toks = sorted(self.values, key=lambda t: -self.values[t])
|
||
found: List[List[str]] = []
|
||
self._search(n, toks, [], 6, found, limit=16, budget=[100_000])
|
||
if not found:
|
||
return None
|
||
style = _StyleModel(self.values, attested_phrases)
|
||
found.sort(key=lambda seq: (-style.score(seq), len(seq)))
|
||
return " ".join(found[0])
|
||
|
||
def _search(self, target: int, toks: List[str], acc: List[str], depth: int,
|
||
found: List[List[str]], limit: int, budget: List[int]) -> None:
|
||
if len(found) >= limit or budget[0] <= 0:
|
||
return
|
||
budget[0] -= 1
|
||
if target == 0 and acc:
|
||
found.append(list(acc))
|
||
return
|
||
if depth == 0 or target <= 0:
|
||
return
|
||
for t in toks:
|
||
v = self.values[t]
|
||
if v > target:
|
||
continue
|
||
# multiplicative: k * v <= target with k attested as token
|
||
for m in toks:
|
||
mv = self.values[m]
|
||
if 1 <= mv < v and mv * v <= target:
|
||
self._search(target - mv * v, toks, acc + [m, t], depth - 2,
|
||
found, limit, budget)
|
||
self._search(target - v, toks, acc + [t], depth - 1, found, limit, budget)
|
||
|
||
|
||
class _StyleModel:
|
||
"""Scores a candidate numeral phrase by consistency with attested style:
|
||
(a) are base tokens (value >= 10) given an explicit smaller multiplier in
|
||
attested multi-token phrases? (b) reuse of attested token bigrams."""
|
||
|
||
def __init__(self, values: Dict[str, int], phrases: Sequence[str]):
|
||
self.values = values
|
||
self.bigrams = set()
|
||
obs: List[bool] = []
|
||
for ph in phrases:
|
||
toks = _norm_tokens(ph)
|
||
if not toks or any(t not in values for t in toks):
|
||
continue
|
||
self.bigrams.update(zip(toks, toks[1:]))
|
||
if len(toks) < 2:
|
||
continue
|
||
for i, t in enumerate(toks):
|
||
if values[t] >= 10:
|
||
obs.append(i > 0 and values[toks[i - 1]] < values[t])
|
||
self.prefer_explicit = sum(obs) > len(obs) / 2 if obs else False
|
||
|
||
def score(self, seq: Sequence[str]) -> float:
|
||
s = 0.0
|
||
s += 0.5 * sum(1 for bg in zip(seq, seq[1:]) if bg in self.bigrams)
|
||
base_seen: Counter = Counter()
|
||
if len(seq) >= 2:
|
||
for i, t in enumerate(seq):
|
||
if self.values[t] >= 10:
|
||
base_seen[t] += 1
|
||
explicit = i > 0 and self.values[seq[i - 1]] < self.values[t]
|
||
s += 1.0 if explicit == self.prefer_explicit else -1.0
|
||
# positional systems use each base power once; repeats are degenerate
|
||
s -= 2.0 * sum(c - 1 for c in base_seen.values())
|
||
return s
|
||
|
||
|
||
def induce(attested: List[Tuple[str, int]], max_candidates: int = 8) -> Optional[NumeralSystem]:
|
||
"""Induce token values from attested (phrase, value) pairs by DFS with
|
||
forward checking. Candidate values per token come from structural
|
||
positions: divisors of attested values, small digits, and base powers."""
|
||
eqs: List[Tuple[List[str], int]] = []
|
||
vocab: List[str] = []
|
||
for phrase, val in attested:
|
||
toks = _norm_tokens(phrase)
|
||
if not toks:
|
||
continue
|
||
eqs.append((toks, val))
|
||
for t in toks:
|
||
if t not in vocab:
|
||
vocab.append(t)
|
||
if not eqs:
|
||
return None
|
||
|
||
# Candidate values per token.
|
||
digits = set(range(1, 10))
|
||
base_powers = {b ** k for b in BASES for k in (1, 2, 3) if b ** k <= MAX_TOKEN_VALUE}
|
||
cands: Dict[str, List[int]] = {}
|
||
for t in vocab:
|
||
cs = set(digits) | base_powers
|
||
# a token appearing alone in an equation must equal that value
|
||
for toks, val in eqs:
|
||
if toks == [t]:
|
||
cs = {val}
|
||
break
|
||
if t in toks:
|
||
cs |= {val} | {d for d in _divisors(val) if d <= MAX_TOKEN_VALUE}
|
||
cands[t] = sorted(cs)
|
||
|
||
# Constraint propagation on short equations before search: a 1-token
|
||
# equation pins its token; a 2-token equation with one token pinned
|
||
# constrains the other to {V-a, V/a}.
|
||
changed = True
|
||
while changed:
|
||
changed = False
|
||
for toks, val in eqs:
|
||
unknown = [t for t in set(toks) if len(cands[t]) > 1]
|
||
if len(set(toks)) == 1:
|
||
t = toks[0]
|
||
if len(toks) == 1 and cands[t] != [val]:
|
||
cands[t] = [val]
|
||
changed = True
|
||
elif len(toks) == 2 and len(unknown) == 1:
|
||
t = unknown[0]
|
||
other = toks[0] if toks[1] == t else toks[1]
|
||
if len(cands[other]) == 1:
|
||
a = cands[other][0]
|
||
allowed = {val - a}
|
||
if a and val % a == 0:
|
||
allowed.add(val // a)
|
||
new = [v for v in cands[t] if v in allowed]
|
||
if new and new != cands[t]:
|
||
cands[t] = new
|
||
changed = True
|
||
|
||
# Order: most-constrained tokens first.
|
||
order = sorted(vocab, key=lambda t: len(cands[t]))
|
||
|
||
assignment: Dict[str, int] = {}
|
||
budget = {"nodes": 200_000}
|
||
|
||
def consistent() -> bool:
|
||
for toks, val in eqs:
|
||
if all(t in assignment for t in toks):
|
||
if _eval([assignment[t] for t in toks]) != val:
|
||
return False
|
||
return True
|
||
|
||
def dfs(i: int) -> bool:
|
||
if budget["nodes"] <= 0:
|
||
return False # search space too big — abstain, don't hang
|
||
if i == len(order):
|
||
return True
|
||
t = order[i]
|
||
for v in cands[t]:
|
||
budget["nodes"] -= 1
|
||
assignment[t] = v
|
||
if consistent() and dfs(i + 1):
|
||
return True
|
||
assignment.pop(t, None)
|
||
return False
|
||
|
||
if dfs(0) and budget["nodes"] > 0:
|
||
sys_ = NumeralSystem(assignment)
|
||
# verify every attested equation round-trips
|
||
if all(sys_.text_to_num(p) == v for p, v in attested):
|
||
return sys_
|
||
return None
|
||
|
||
|
||
def _divisors(n: int) -> List[int]:
|
||
n = abs(n)
|
||
out = []
|
||
for d in range(1, int(n ** 0.5) + 1):
|
||
if n % d == 0:
|
||
out += [d, n // d]
|
||
return sorted(set(out))
|
||
|
||
|
||
def extract_attested(pairs) -> List[Tuple[str, int]]:
|
||
"""From preprocess Pairs, pull (phrase, int) where one side is a number."""
|
||
out = []
|
||
for p in pairs:
|
||
for a, b in ((p.src, p.tgt), (p.tgt, p.src)):
|
||
bs = b.strip().replace(",", "").replace(" ", "")
|
||
if re.fullmatch(r"\d+", bs):
|
||
out.append((a, int(bs)))
|
||
break
|
||
return out
|