SilverSight/scripts/braid_word_solver.py

#!/usr/bin/env python3
"""
Braid Word Solver: maps DAG iteration paths to braid words.

8 strands → 16 moduli in 8 chiral pairs (L_{2i-1}, L_{2i}).
Each pair: identity modulus > reflection modulus = σ_i⁺ (over-crossing).
DAG path = braid word: sequence of crossings that transforms A₀ to Sidon.
"""
import sys, math, json
from typing import List, Tuple
from collections import defaultdict
sys.path.insert(0, '/home/allaun/SilverSight/scripts')
from verify_wrapping import f_k, is_sidon
from iteration_dag import IterationDAG, AdaptiveRule, DAGNode

# ---------- Braid Word Representation ----------

def moduli_to_braid_word(moduli_sequence: List[List[int]]) -> str:
    """Convert a sequence of modulus choices to a braid word.
    
    Each modulus vector has 2k entries (k strands, 2 axes each).
    A modulus pair [L_id, L_ref] for strand i encodes:
      - L_id > L_ref  → σ_i⁺  (over-crossing, identity dominates)
      - L_id < L_ref  → σ_i⁻  (under-crossing, reflection dominates)
      - Large M       → active crossing (big change in configuration)
      - Small M       → gentle crossing (small change)
    """
    strands = len(moduli_sequence[0]) // 2 if moduli_sequence else 0
    if strands == 0:
        return "1"  # identity braid
    
    word = []
    for moduli in moduli_sequence:
        for i in range(strands):
            L_id = moduli[2*i]     # identity axis
            L_ref = moduli[2*i+1]  # reflection axis
            if L_id > L_ref:
                word.append(f"σ_{i+1}⁺")
            elif L_ref > L_id:
                word.append(f"σ_{i+1}⁻")
            # if equal, no crossing
    return " · ".join(word) if word else "1"

# ---------- 16D Braid Configuration ----------

class BraidConfig:
    """Represent a braid configuration as 8 chiral modulus pairs."""
    
    def __init__(self, base_moduli: List[Tuple[int,int]] = None):
        """Initialize with 8 strand pairs. Default: all (5,3)."""
        if base_moduli:
            self.pairs = list(base_moduli)
        else:
            # Default: each strand has id=5, ref=3 (L_id > L_ref = over)
            self.pairs = [(5, 3)] * 8
        assert len(self.pairs) == 8, "Need exactly 8 strand pairs"
    
    def to_moduli_list(self) -> List[int]:
        """Flatten to [L1, L2, ..., L15, L16] for CRT use."""
        result = []
        for L_id, L_ref in self.pairs:
            result.append(L_id)
            result.append(L_ref)
        return result
    
    def apply_crossing(self, strand: int, over: bool = True):
        """Apply σ_strand (over or under) by adjusting the pair."""
        i = strand - 1  # 0-indexed
        L_id, L_ref = self.pairs[i]
        if over:
            # Over-crossing: identity dominates → increase identity modulus
            self.pairs[i] = (L_id + 2, max(L_ref - 1, 2))
        else:
            # Under-crossing: reflection dominates → increase reflection modulus
            self.pairs[i] = (max(L_id - 1, 2), L_ref + 2)
    
    @staticmethod
    def from_moduli_list(moduli: List[int]):
        """Convert flat moduli list back to strand pairs."""
        pairs = []
        for i in range(0, len(moduli), 2):
            pairs.append((moduli[i], moduli[i+1]))
        return BraidConfig(pairs)

# ---------- DAG → Braid Word Mapping ----------

def dag_path_to_braid(A0: List[int], S: int, path: List[DAGNode]) -> Tuple[str, List[BraidConfig]]:
    """Convert a DAG path to a braid word.
    
    Root (A₀) → node1 (A₁) → node2 (A₂) → ...
    Each non-root node's moduli encode the crossing applied to reach it:
      moduli = [L_id, L_ref, ...]
      L_id > L_ref → σ⁺ (over-crossing)
      L_id < L_ref → σ⁻ (under-crossing)
      Unused strands (beyond the first pair) default to idle.
    """
    crossings = []
    
    for i in range(1, len(path)):
        mods = path[i].moduli
        pair = (mods[0], mods[1]) if len(mods) >= 2 else (2, 2)
        L_id, L_ref = pair
        if L_id > L_ref:
            crossings.append("σ₁⁺")
        elif L_ref > L_id:
            crossings.append("σ₁⁻")
        else:
            crossings.append("σ₁·")
    
    braid_word = " · ".join(crossings) if crossings else "1"
    return braid_word

def solve_braid_word(A0: List[int], S: int, max_steps: int = 4) -> dict:
    """Find the shortest braid word that transforms A0 to Sidon."""
    rule = AdaptiveRule(max_val=16)
    dag = IterationDAG(A0, S, rule, max_steps=max_steps)
    dag.build()
    
    results = {
        'A0': A0, 'S': S,
        'paths': [],
        'summary': {}
    }
    
    for path in dag.sidon_paths:
        braid_word = dag_path_to_braid(A0, S, path)
        results['paths'].append({
            'steps': len(path) - 1,
            'braid_word': braid_word,
            'As': [n.A for n in path],
            'Ms': [n.M for n in path]
        })
    
    if results['paths']:
        shortest = min(results['paths'], key=lambda p: p['steps'])
        results['summary'] = {
            'total_paths': len(results['paths']),
            'shortest_word': shortest['braid_word'],
            'shortest_steps': shortest['steps'],
            'final_set': shortest['As'][-1],
            'moduli_path': shortest['Ms']
        }
    
    return results

# ---------- Test & Demonstration ----------

def demo_sidon_example():
    """Map the known Sidon example to a braid word."""
    A0, S = [1, 2, 5, 6], 7
    print("=" * 60)
    print("BRAID WORD SOLVER — Sidon Example")
    print("=" * 60)
    
    result = solve_braid_word(A0, S)
    
    if result['paths']:
        p = result['paths'][0]  # First path found
        print(f"\nA₀ = {result['A0']}")
        print(f"S  = {result['S']}")
        print(f"\nBraid word: {p['braid_word']}")
        print(f"\nStep-by-step:")
        for i in range(len(p['As'])):
            sidon = " ★SIDON" if is_sidon(p['As'][i]) else ""
            print(f"  Step {i}: A = {p['As'][i]}  M = {p['Ms'][i]}{sidon}")
    
    print(f"\nSummary: {result['summary']}")

def demo_complex_set():
    """Map the complex set to a braid word — shows multi-step paths."""
    A0, S = [0, 1, 3, 8, 13], 27
    print("\n" + "=" * 60)
    print("BRAID WORD SOLVER — Complex Set (multi-step)")
    print("=" * 60)
    
    result = solve_braid_word(A0, S)
    
    if result['paths']:
        p = min(result['paths'], key=lambda x: x['steps'])
        print(f"\nA₀ = {result['A0']}")
        print(f"S  = {result['S']}")
        print(f"\nShortest braid word ({p['steps']} steps): {p['braid_word']}")
        print(f"\nPath:")
        for i in range(len(p['As'])):
            sidon = " ★" if is_sidon(p['As'][i]) else ""
            print(f"  {i}: A={p['As'][i]} M={p['Ms'][i]}{sidon}")
    
    print(f"\nTotal paths found: {result['summary'].get('total_paths', 0)}")

def demo_braid_vs_moduli():
    """Show how DAG path = braid word with modulus ordering."""
    print("\n" + "=" * 60)
    print("BRAID WORD = DAG PATH")
    print("=" * 60)
    print()
    print("Each DAG step chooses moduli (L_id, L_ref) for a strand.")
    print("L_id > L_ref → σ⁺ (over-crossing)")
    print("L_id < L_ref → σ⁻ (under-crossing)")
    print()
    print("Example path:")
    print("  Step 1: (7, 3) → σ₁⁺  (strand 1 over-crosses, gap=7)")
    print("  Step 2: (11, 2) → σ₁⁺ (strand 1 over-crosses again, gap=11)")
    print("  Step 3: Sidon reached → braid word = σ₁⁺·σ₁⁺")
    print()
    print("The braid word IS the iteration path.")

if __name__ == "__main__":
    demo_sidon_example()
    demo_complex_set()
    demo_braid_vs_moduli()