--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/nono.py	Mon Mar 09 14:58:04 2020 +0000
@@ -0,0 +1,298 @@
+#!/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.runs=runs
+    # 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,0,
+                                    sum(1+self.runs[k] for k in range(self.rn))-1))
+    self.nar=len(self.allRuns)
+
+  def seedList(self,i,j,pos,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 pos: left margin
+    :type pos: int
+    """
+    bound=self.n-(pos+runLen)+1
+    #dprint('s',i,j,pos,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,pos+v+r,runLen-(r+1)):
+        yield [-v,r]+sub
+
+  def __repr__(self):
+    return "V@%s%s:%s"%(self.x,self.runs,list.__repr__(self))
+
+  def __str__(self):
+    return '%s|'%('|'.join(str(c) for c in self))
+
+  def step(self):
+    scratch=[0 if c.val is None else c.val for c in self]
+    for k,runs in enumerate(self.allRuns):
+      dprint('=====pass %s======'%k)
+      self.onepass(0,self.n,scratch,runs.copy())
+    dprint(scratch)
+    for i in range(self.n):
+      if scratch[i]==self.nar:
+        # If blobby in _every_ pass, then must be a blob
+        if self[i].val is None:
+          self[i].setVal(True)
+        elif self[i].val is True:
+          # already there
+          pass
+        else:
+          print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr)
+          exit(101)
+
+  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
+    j=-1 # index into run
+    maybe=[0]*iBound
+    dprint('r: %s'%stack)
+    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
+        i-=r
+        req+=r
+        r=rr=stack.pop(0)
+      # rr is run remaining -- how many we still need
+      j+=1 # index of current run in self.runs, we'll need to decorate that eventually
+      inOne=-1 # if non-neg, records the start point of a possible run
+      gapsFilled=0
+      # First, check if we can start here:  0 is OK, and n>0 iff n-1 is None or False
+      if i>0 and i<iBound:
+        while self[i-1].val:
+          i+=1
+      if (iBound-i)<req:
+        # Can't win, give up altogether
+        dprint('c0',i,iBound,req)
+        return
+      while i<iBound:
+        c=self[i].val
+        dprint('top',i,c,inOne,rr)
+        if c is None:
+          # we could add a blob here
+          dprint('c1')
+          gapsFilled+=1
+          rr-=1
+          if inOne<0:
+            dprint('c1a',i)
+            # starts here
+            inOne=i
+          # fall through to check for completion
+        else:
+          dprint('c2')
+          # c is a bool
+          if inOne<0:
+            dprint('c2a')
+            if c:
+              dprint('c2a1')
+              # a *, we can possible start something here
+              inOne=i
+              rr-=1
+              # fall through to check for completion
+            else:
+              dprint('c2a2')
+              # an x, can't start here, just move along
+              i+=1
+              continue
+          else:
+            dprint('c2b')
+            if c:
+              dprint('c2b1')
+              # a blob, extend or complete a partial
+              rr-=1
+              # fall through to check for completion
+            else:
+              # abandon a partial
+              dprint('c2b2')
+              inOne=-1
+              rr=r
+              i+=1
+              continue
+        if rr>0:
+          dprint('c3')
+          # we're not done, carry on
+          i+=1
+          continue
+        # Maybe a win?
+        # look ahead, can we stop here?
+        # NB _self_.n
+        if i+1<self.n and self[i+1].val:
+          dprint('c4')
+          # Nope
+          inOne=-1
+          rr=r
+          gapsFilled=0
+          i+=1
+          continue
+        elif gapsFilled==0:
+          dprint('c5')
+          # We must have crossed at least on gap...
+          print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s inOne:%s"%(self,i, j, rr, inOne),file=sys.stderr)
+          exit(100)
+        # Victory!
+        dprint('c6',r,inOne,i)
+        for k in range(inOne,i+1):
+          maybe[k]+=1
+        i+=1
+        req-=r
+        break
+      # 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]
+
+class Row(Vector):
+  def __init__(self,n,m,runs,pos,dprintWidth):
+    Vector.__init__(self,n,m,runs)
+    self.y=pos
+    self.dprintWidth=dprintWidth
+    self.fmt="%%%ss|"%dprintWidth
+
+  def __str__(self):
+    return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
+            Vector.__str__(self))
+
+class Column(Vector):
+  def __init__(self,n,m,runs,pos,dprintHeight):
+    Vector.__init__(self,n,m,runs)
+    self.x=pos
+    self.dprintHeight=dprintHeight
+    self.fmt="%%%ss"%self.dprintHeight
+    self.updateHeader()
+
+  def updateHeader(self):
+    header=('-'.join(str(c) for c in self.runs))
+    self.header=self.fmt%header # pad to same 'height'
+
+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:
+        dprint("Warning: x -> * at %s,%s"%(self.x,self.y))
+      elif self.val is True:
+        # No-op
+        return
+      # @@ check row/col completed
+    else:
+      if self.val is not None:
+        dprint("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,rows,cols):
+    n=self.n=len(cols)
+    if n!=len(rows):
+      print("losing r:%s x c:%s"%(len(rows),n),sys.stderr)
+      exit(1)
+    self.rc=rows
+    rowDprintWidth=max(sum(len(str(r)) for r in row)+len(row)-1 for row in rows)
+    self.rowfmt="%s|%%s"%(' '*rowDprintWidth)
+    self.cc=cols
+    # dprint col nums>9 vertically :-(
+    self.colDprintHeight=max(sum(len(str(c)) for c in col)+len(col)-1 for col in cols)
+    self.columns=cc=[Column(n,self,cols[i],i,self.colDprintHeight) for i in range(20)]
+    self.rows=rr=[Row(n,self,rows[i],i,rowDprintWidth) for i in range(20)]
+    for x in range(20):
+      for y in range(20):
+        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.colDprintHeight)]
+    lines+=[str(r) for r in self.rows]
+    return "\n".join(lines)
+
+def dprint(*args):
+  pass
+
+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)
+  print(solver)
+  for c in solver.columns:
+    c.step()
+  print()
+  print(solver)
+  for r in solver.rows:
+    r.step()
+  print()
+  print(solver)