--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/nono_17.py	Mon Jul 20 11:06:55 2020 +0100
@@ -0,0 +1,554 @@
+#!/usr/bin/python3
+# Expects e.g. ^A copy from Nonograms dprint preview cols, then blank line, then rows
+#  rows are space-separated
+#  cols are one-digit-after-another, unless some 2-digit, in which case x is separator
+# E.g.
+# 13x1x2
+# 19
+# maps to
+# 13
+# 1  1
+# 2  9
+
+import sys
+
+Red=''
+eRed=''
+RedFmt=Red+'%s'+eRed
+
+def interleave(*args):
+  for vals in zip(*args):
+    yield from vals
+
+class Vector(list):
+  # reads top-to-bottom or left-to-right
+  def __init__(self,n,m,runs):
+    list.__init__(self,list(range(n)))
+    self.n=n
+    self.m=m
+    self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False
+    self.marginN=n-1 # a run can end here, so if <n-1 then self[mN+1].val ditto
+    self.runs=self.origRuns=runs
+    self.initialComplete=[]
+    self.finalComplete=[]
+    self.resetAllRuns()
+
+  def __repr__(self):
+    return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self))
+
+  def __str__(self):
+    return '%s|'%('|'.join(str(c) for c in self))
+
+  def myPrintSize(self):
+    return sum(len(str(run)) for run in self.runs)+len(self.runs)-1
+
+  def resetAllRuns(self):
+    # compute the set of all possible layouts for runs
+    self.rn=len(self.runs)
+    rtot=sum(self.runs)
+    self.allRuns=list(self.seedList(0,0,self.margin0,self.marginN+1,
+                                    sum(1+self.runs[k] for k in range(self.rn))-1))
+    self.nar=len(self.allRuns)
+
+  def seedList(self,i,j,pos0,posN,runLen):
+    """
+    :param i: starting skip before next run
+    :type i: 0 if pos==0 else 1
+    :param j: next run number
+    :type j: int
+    :param pos0: left margin
+    :type pos0: int
+    :param posN: right margin
+    :type posN: int
+    """
+    bound=posN-(pos0+runLen)+1
+    dprint('s',i,j,pos0,posN,runLen,bound)
+    if j==self.rn:
+        yield []
+        return
+    r=self.runs[j]
+    for v in range(i,bound):
+      for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)):
+        yield [-v,r]+sub
+
+  def step(self,pos):
+    if self.runs==[]:
+      return 0
+    scratch=[0 if c.val is None else c.val for c in self]
+    wins=0
+    changed=0
+    for k,runs in enumerate(self.allRuns):
+      if (self.m.loop,self.cLet,pos,k)==(1,'R',7,5):
+        print(self.m)
+      dprint('=====pass %s.%s.%s.%s======'%(self.m.loop,self.cLet,pos,k))
+      if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
+        wins+=1
+    dprint(wins, scratch)
+    maybeSeq=None
+    inSeq=None
+    j=None
+    for i in range(self.n):
+      if scratch[i]>=wins:
+        # If blobby in _every_ pass, then must be a blob
+        if inSeq is None:
+          inSeq=i if maybeSeq is None else maybeSeq
+          dprint('s1',inSeq)
+          maybeSeq=None
+        if self[i].val is None:
+          dprint('s1a',i)
+          self.newBlob(i,True)         # Check cross-vector
+          j=i
+          changed=1
+        elif self[i].val is True:
+          pass
+        else:
+          eprint("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),err=101)
+      elif inSeq is not None:
+        if self[i].val is not True:
+          inSeq=None
+          maybeSeq=None
+          dprint('s2',i-1,j)
+          if j is not None:
+            # Only if we actually added a blob at some point
+            dpush('b_s2')
+            self.checkNew(i-1)
+            dpop('b_s2')
+      elif self[i].val is True and maybeSeq is None:
+        dprint('s3',i)
+        maybeSeq=i
+    dprint('s4',inSeq,i)
+    if inSeq is not None:
+      dpush('b_s4')
+      self.checkNew(i)
+      dpop('b_s4')
+    return changed
+
+  def onepass(self,i0,iBound,scratch,stack):
+    """note that stack is not a simple run, but one with _negative_ numbers between
+     and possibly before the positive ones, indicating obligatory skips
+     """
+    i=i0 # starting index into self/scratch/maybe
+    maybe=[0]*self.n
+    dprint('r: %s'%stack,i0,iBound)
+    req=sum((-r if r<0 else r) for r in stack)
+    while stack and i<iBound:
+      r=rr=stack.pop(0)
+      dprint('pop:',r)
+      if r<1:
+        # obligatory skip
+        # (Above init of self.allRuns is easier if we allow a 0 to be ignored
+        for k in range(i,i-r):
+          if self[k] is True:
+            # has to be False or None to skip
+            dprint('x0',k)
+            return False
+        i-=r
+        req+=r
+        r=rr=stack.pop(0)
+      # rr is run remaining -- how many we still need
+      # First, check if we can start here:  0 is OK, and n>0 iff n-1 is None or False
+      # if i>0 and self[i-1].val is True:
+      #  dprint('x1',i)
+      #  return
+      if (iBound-i)<req:
+        # Can't win, give up altogether
+        dprint('x2',i,iBound,req)
+        return False
+      j=i # start of run, if we find it
+      gapsFilled=0
+      dprint('top:',j)
+      while rr>0:
+        # guaranteed by check above that we won't run over the far end
+        c=self[i].val
+        if c is False:
+          dprint('x3',i)
+          return False
+        if c is None:
+          # we could add a blob here
+          gapsFilled+=1
+        # and a blob already present is OK
+        rr-=1
+        i+=1
+      # Maybe a win?
+      # look ahead, can we stop here?
+      if i<self.n and self[i].val is True:
+        dprint('x4',i)
+        return False
+#       elif gapsFilled==0:
+#         # We must have crossed at least one gap...
+#         print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s"%(self,i, j, rr),file=sys.stderr)
+#         raise Exception
+      # Victory!
+      dprint('c6',r,j,i)
+      for k in range(j,i):
+        maybe[k]+=1
+      req-=r
+      # on to the next run
+    # end of inner loop, did we win?
+    if (not stack) or i==iBound:
+      # yes
+      dprint('win:',maybe)
+      for k in range(iBound):
+        scratch[k]+=maybe[k]
+      return True
+    eprint("Shouldn't happen? - fell through",stack,i,iBound,err=102)
+
+  def checkX(self,pos,crosspos):
+    # New x at pos, are there others that can be xed out now?
+    # Overkill as is?
+    dprint('cx',self.cLet+str(crosspos),pos)
+    if self.runs:
+      start0=self.margin0 # 0 if self.margin0==0 else self.margin0+1
+      if self.marginal(range(start0,pos),self.runs[0]):
+        dprint('cx1a')
+      else:
+        dprint('cx1b')
+#    if len(self.runs)>1:
+      startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
+      if self.marginal(range(startN,pos,-1),self.runs[-1]):
+        dprint('cx2a')
+      else:
+        dprint('cx2b')
+
+  def checkNew(self,pos):
+    # New blob at pos, can we complete anything?
+    # Assuming @@ FTTB that it's never possible to definitively complete a
+    #  non-marginal run, which is wrong if the length is unique and it's bounded...
+    start0=self.margin0 #0 if self.margin0==0 else self.margin0+1
+    startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
+    dprint('cn',start0,pos,startN)
+    changed=False
+    # First, find our boundaries:
+    s=pos # start index of our run
+    if s>start0:
+      while s>start0 and self[s-1].val is True:
+        s-=1
+    f=pos # finish index of our run
+    if f<startN:
+      while f<startN and self[f+1].val is True:
+        f+=1
+    l=(f-s)+1 # our length
+    dprint('%s:%s,%s,%s,%s:<%s>'%(self.cLet,s,f,l,self.runs,self))
+    c=self.runs.count(l)
+    if c==0:
+      # not big enough yet
+      dprint('x0')
+      return
+    if self.runs[0]==l:
+      # is it safely left marginal, i.e. no blobs or big enough gaps before us?
+      if self.marginal(range(start0,s),l):
+        changed=True
+        dprint('n1')
+        # mark our margins
+        for i in range(start0,s): # not sure this is still needed since
+                                        # added gap-filling in self.marginal
+          if self[i].val is None:
+            self.newX(i,False)
+        if f<startN:
+          if self[f+1].val is None:
+            self.newX(f+1,True)
+        self.found0(f) # pull in the start margin at least to f+2
+      else:
+        dprint('x1a')
+    if not changed:
+      if self.runs[-1]==l:
+        # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
+        if self.marginal(range(startN,f,-1),l):
+          changed=True
+          dprint('n2')
+          # mark our margins: still needed? see above
+          for i in range(startN,f,-1):
+            if self[i].val is None:
+              self.newX(i,False)
+          if s>start0:
+            if self[s-1].val is None:
+              self.newX(s-1,True)
+          self.foundN(s) # pull in the finish margin at least to s-2
+        else:
+          dprint('x2a')
+      else:
+        dprint('x2b')
+    if changed:
+      self.resetAllRuns()
+
+  def marginal(self,rng,l):
+    dprint('m%s'%self.cLet,rng.start,rng.stop,rng.step,l)
+    g=0 # length of a gap
+    for i in rng:
+      if self[i].val is True:
+        # Shouldn't be possible?
+        dprint('mx0')
+        return False
+      if self[i].val is False:
+        if g>0:
+          # Block a too-small gap
+          dprint('m1',i-g,i)
+          for j in range(i-g,i):
+            self.newX(j,True)
+          g=0
+      else:
+        # None
+        g+=1
+        if g==l:
+          # run could fit here, so no go
+          dprint('mx1')
+          return False
+    if g>0:
+      # Block a too-small gap
+      if rng.step==1:
+        # forward
+        dprint('m2f',i-g,i)
+        for j in range(i+1-g,i+1):
+          self.newX(j,True)
+      else:
+        # backward
+        dprint('m2b',i+g,i)
+        for j in range(i+g-1,i-1,-1):
+          self.newX(j,True)
+    return True
+
+  def found0(self,i):
+    dprint('found0 called on %s at %s'%(self,i))
+    i=self.margin0
+    while self[i].val is False:
+      i+=1
+    if self[i].val is True:
+      r=self.runs.pop(0)
+      self.initialComplete.append(r)
+      self.margin0+=r+1
+      self.updateHeader(r=r,pre=True)
+
+  def foundN(self,i):
+    dprint('foundN called on %s at %s'%(self,i))
+    i=self.marginN
+    while self[i].val is False:
+      i-=1
+    if self[i].val is True:
+      r=self.runs.pop()
+      self.finalComplete=[r]+self.finalComplete
+      self.marginN-=r+1
+      self.updateHeader(r=r,pre=False)
+    
+
+class Row(Vector):
+  cLet='R'
+  def __init__(self,n,m,runs,pos):
+    Vector.__init__(self,n,m,runs)
+    self.y=pos
+    self.width=self.myPrintSize()
+
+  def __str__(self):
+    return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
+            Vector.__str__(self))
+
+  def updateHeader(self,*,maxWidth=None,r=None,pre=None):
+    if maxWidth is None:
+      # update
+      spacer=(" " if self.runs else "")
+      if pre:
+        self.infix+=(RedFmt%r)+spacer
+      else:
+        # post
+        self.suffix=spacer+RedFmt%r+self.suffix
+      self.fmt="%s%s%%s%s|"%(self.prespace,self.infix,self.suffix)
+    else:
+      # init
+      self.maxWidth=maxWidth
+      self.prespace=' '*(maxWidth-self.width)
+      self.fmt="%s%%s|"%self.prespace
+      self.infix=""
+      self.suffix=""
+
+  def newBlob(self,x,crossCheck=False):
+    self[x].setVal(True)
+    if crossCheck:
+      dpush('b_cc')
+      self[x].column.checkNew(self.y)
+      dpop('b_cc')
+
+  def newX(self,x,crossCheck=False):
+    dprint('nx %s%s@%s'%('R',self.y,x))
+    self[x].setVal(False)
+    if crossCheck:
+      dpush('x_cc')
+      self[x].column.checkX(self.y,x)
+      dpop('x_cc')
+
+class Column(Vector):
+  cLet='C'
+  def __init__(self,n,m,runs,pos):
+    Vector.__init__(self,n,m,runs)
+    self.x=pos
+    self.height=self.myPrintSize()
+
+  def updateHeader(self,*,maxHeight=None,r=None,pre=None):
+    dprint('CuH',r,pre)
+    if maxHeight is None:
+      # update
+      if pre:
+        for rc in str(r):
+          self.infix.append(RedFmt%rc)
+        if self.runs:
+          self.infix.append('-')
+      else:
+        # post
+        ins=["-"] if self.runs else []
+        for rc in str(r):
+          ins.append(RedFmt%r)
+        self.suffix=ins+self.suffix
+      dprint('CuH1: |%s|,%s,%s,%s'%(self.prespace,self.infix,self.suffix,self.runs))
+      self.header=([" "]*self.prespace)+\
+                   self.infix+\
+                   (['-'.join(str(c) for c in self.runs)] if self.runs else [])+\
+                   self.suffix
+    else:
+      # init
+      self.maxHeight=maxHeight
+      self.infix=[]
+      self.suffix=[]
+      self.prespace=maxHeight - self.height # pad to same 'height'
+      self.fmt="%s%%s"%(' '*self.prespace)
+      header=('-'.join(str(c) for c in self.runs))
+      self.header=self.fmt%header
+    dprint(self.header)
+
+  def newBlob(self,y,crossCheck=False):
+    self[y].setVal(True)
+    if crossCheck:
+      dpush('b_cc')
+      self[y].row.checkNew(self.x)
+      dpop('b_cc')
+
+  def newX(self,y,crossCheck=False):
+    dprint('nx %s%s@%s'%('C',self.x,y))
+    self[y].setVal(False)
+    if crossCheck:
+      dpush('x_cc')
+      self[y].row.checkX(self.x,y)
+      dpop('x_cc')
+
+class Cell:
+  def __init__(self,row,y,column,x):
+    # At the intersection of row and column Vectors
+    self.row=row
+    self.column=column
+    self.x=x
+    self.y=y
+    self.val=None # three valued: None(unknown), True(filled), False(empty)
+    self.row[x]=self
+    self.column[y]=self
+
+  def __repr__(self):
+    return "C@(%s,%s):%s"%(self.x,self.y,self.val)
+
+  def __str__(self):
+    return ' ' if self.val is None else ('\u25A0' if self.val else 'x')
+
+  def setVal(self,v):
+    if v is True:
+      if self.val is False:
+        wprint("Warning: x -> * at %s,%s"%(self.x,self.y))
+      elif self.val is True:
+        # No-op
+        return
+      self.val=v
+    else:
+      if self.val is not None:
+        wprint("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y))
+      self.val=v
+        
+
+class Nono(dict):
+  # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
+  def __init__(self,runsPerRow,runsPerCol):
+    global SOLVER
+    self.loop=0
+    self.dp=''
+    self.dstate=[]
+    SOLVER=self
+    n=self.n=len(runsPerCol)
+    if n!=len(runsPerRow):
+      print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr)
+      exit(1)
+    self.rc=runsPerRow
+    self.cc=runsPerCol
+    # print col nums>9 vertically :-(
+    self.columns=cc=[Column(n,self,runsPerCol[i],i) for i in range(n)]
+    self.maxCRheight=maxCRheight=max(col.height for col in cc)
+    for c in cc:
+      c.updateHeader(maxHeight=maxCRheight)
+    self.rows=rr=[Row(n,self,runsPerRow[i],i) for i in range(n)]
+    maxRRwidth=max(row.width for row in rr)
+    for r in rr:
+      r.updateHeader(maxWidth=maxRRwidth)
+    self.rowfmt="%s|%%s|"%(' '*maxRRwidth)
+    for x in range(n):
+      for y in range(n):
+        self[(x,y)]=Cell(rr[y],y,cc[x],x)
+
+  def __str__(self):
+    lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
+           for j in range(self.maxCRheight)]
+    lines+=[str(r) for r in self.rows]
+    return "\n".join(lines)
+
+  def solve(self):
+    someChanged=1
+    while someChanged>0:
+      self.loop+=1
+      someChanged=0
+      dprint("***Solve C %s***"%self.loop)
+      for c in self.columns:
+        someChanged+=c.step(c.x)
+      print(someChanged)
+      print(self)
+      dprint("***Solve R %s***"%self.loop)
+      for r in self.rows:
+        someChanged+=r.step(r.y)
+      print(someChanged)
+      print(self)
+
+def dpush(s):
+  SOLVER.dp+=' '
+  SOLVER.dstate.append(s)
+
+def dpop(s):
+  assert(SOLVER.dstate.pop()==s)
+  SOLVER.dp=SOLVER.dp[1:]
+
+def dprint(*args):
+  print(SOLVER.dp,end='')
+  print(*args)
+  sys.stdout.flush()
+
+def eprint(*args,**kw):
+  print(*args,file=sys.stderr)
+  sys.stderr.flush()
+  exit(kw['err'])
+
+def wprint(*args):
+  print(*args,file=sys.stderr)
+  sys.stderr.flush()
+
+if __name__ == '__main__':
+  if len(sys.argv)>1:
+    f=open(sys.argv[1])
+  else:
+    f=sys.stdin
+
+  cols=[]
+
+  for l in f:
+    l=l.rstrip()
+    if l=='':
+      break
+    if 'x' in l:
+      vv=[int(s) for s in l.split('x')]
+    else:
+      vv=[int(c) for c in l]
+    cols.append(vv)
+
+  rows=[[int(s) for s in l.split()] for l in f]
+
+  solver=Nono(rows,cols)
+  solver.solve()