#! /usr/bin/python3
# Last edited on 2026-04-26 14:41:45 by stolfi

import os, sys, re
from sys import stderr as err, stdout as out
from math import sqrt, hypot, log, exp, floor, ceil, inf, nan, isfinite

def match_multi_pattern(text, pats, eval):

  # Takes a text and a list {pats[0..nh-1]} of RE patterns. 
  # 
  # Enumerates all the ways to parse {text} into {ns = 2*nh+1}
  # segments  {segs[0..ns-1]} so that each segment {segs[2*ih+1]}
  # is an instance of {pats[ih]}, and the
  # concatenation of all segments is {text}.
  #
  # The {nh} odd-numbered segments {segs[1],segs[3],...} are the /hits/
  # of the patterns, and the {ng = nh+1] even-numbered ones
  # {segs[0],segs[2],...} are the corresnponding /gaps/.
  #
  # For each such parsing, calls the function {eval(segs)}
  # to produce a numeric "badness" score. Returns the parsing
  # {opt_segs} with minimum score, and its score {opt_score}.
  # 
  # If there are no parsings with these properties, returns {None,+inf}.
  
  debug = False
  
  nt = len(text)  # Lengths of the text.

  nh = len(pats)        # Number of patterns, and hits.
  ns = 2*nh + 1         # Number of segments (gaps and hits).
  segs = [ None ] * ns  # Segments of partial parsing.
  opt_segs = None       # Best complete parsing seen.
  opt_score = +inf      # That parsing's score.

  def match_aux(kt, ih):
    # Assumes that {segs[0..2*ih} are defined for
    # some {ih <= nh} and cover the first {kt} characters of {text}.
    # Enumerates all complete parsings that extend that parsing, updaing
    # the optimum.
    nonlocal opt_segs, opt_score

    ind = ("." * ih) if debug else None
    if debug: err.write(f" {ind} {kt = } {ih = }\n")
    if ih == nh:
      if debug: err.write("!! {ind} =\n")
      segs[ns-1] = text[kt:]
      score = eval(segs)
      if score < opt_score:
        opt_segs = segs.copy()
        opt_score = score
      # No way to extend:
      return
    else:
      # Still need more hits:
      assert ih < nh
      if debug: err.write(f" {ind} < {kt = }\n")
      pat = pats[ih]
      rt = kt
      while rt < nt:
        tail = text[rt:]
        m = re.match(pat, tail)
        if m != None: 
          st = rt + m.end(0)
          gap = text[kt:rt]; hit = text[rt:st]
          if debug: err.write(f" {ind}  {gap = !r} {hit = !r}\n")
          segs[2*ih] = gap; segs[2*ih+1] = hit
          match_aux(st,ih+1)
          segs[2*ih] = None; segs[2*ih+1] = None
        rt += 1
    return
    # ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

  if debug: err.write(">>\n")
  match_aux(0,0)
  if debug: err.write("<<\n")
  
  if opt_segs != None:
    for sg in opt_segs: 
      if debug: err.write(f"!! {sg = !r}\n")
      assert isinstance(sg, str)

  return opt_segs, opt_score
  # ----------------------------------------------------------------------
   
def find_multi_pattern_occurrences(text, pats):
  # Given a string {text} and a list of {nh} RE patterns {pats},
  # finds non-overlappin occurrences of {pats[0..nh-1]}
  # in that sequence.  Returns a list {segs[0..ns]}
  # of the gaps and hots of those pattersn, where {ns=2nh+1}.
  
  np = len(pats)
  
  segs = []
  nt = len(text)
  tail = text; ip = 0
  while ip < np and tail != "":
    m = re.search(pats[ip], tail)
    if m == None: break
    ks = m.start(0)
    ke = m.end(0)
    segs.append(tail[0:ks])
    segs.append(tail[ks:ke])
    tail = tail[ke:]
    ip += 1
  if ip < np:
    segs = None
  else:
    segs.append(tail)
  return segs
  # -------------------------------------------------------------------------------
 
def test_match(text0, text1, pats0, pats1):

  assert len(pats0) == len(pats1)
  nh = len(pats0);
  ns = 2*nh + 1
  
  debug = False

  # Find {segs}, the gaps and hits of {pats0} in {text0}:
  segs0 = find_multi_pattern_occurrences(text0,pats0)
  
  def eval(segs1):
    assert len(segs1) == ns
    if debug:
      for ks in range(ns):
        err.write(f" {segs1[ks]}")
      err.write("\n")
    score = 0
    for ks in range(ns):
      sz0 = len(segs0[ks])
      sz1 = len(segs1[ks])
      score += (sz0-sz1)**2
    if debug:
      err.write(f"{score = }\n")
      err.write("\n")
    return score
     
  osegs, oscore = match_multi_pattern(text1, pats1, eval)
  print((osegs, oscore))
  return
  # ----------------------------------------------------------------------
  
def test_match_0():
  text0 = "...XX........XaX..."
  text1 = "...ZZ..ZaZ...ZaZ..."
  
  pats0 = ( 'Xa*X', 'Xa*X', )
  pats1 = ( 'Za*Z', 'Za*Z', )
  
  test_match(text0, text1, pats0, pats1)
  
def test_match_1():
  text0 = "acaBUMxesooninobaPAPAbabGRAmosGRAozoxSEXYzuzuzu"
  text1 = "<>=PIMBP~:;=PRP=--=PUP::==:=::PHP:==PAPP+++++"
  
  pats0 = ( 'BUM|PAPA', 'BUM|PAPA|GRA', 'GRA', 'GRA|SEXY', )
  pats1 = ( 'P[A-OQ-Z]*P', 'P[A-OQ-Z]*P', 'P[A-OQ-Z]*P', 'P[A-OQ-Z]*P', )
  
  test_match(text0, text1, pats0, pats1)

if len(sys.argv) > 1 and sys.argv[1] == "MMF.TEST":
  test_match_0()
  test_match_1()