view nono.py @ 58:a3aaf6c085f4 simple

pass0, initial display working with Run and Space
author Henry Thompson <ht@markup.co.uk>
date Thu, 01 Jun 2023 19:02:22 +0100
parents 057b52746850
children c22f83e049a9
line wrap: on
line source

#!/usr/bin/python3
# New version, input taken from Nonograms Outer HTML plus
#  > fgrep 'task = ' nono10.xhtml|tr ';' '\n' | fgrep task\ = | sed 's/^.*= //'| tr -d \'
#  E.g. 8/5.1/2.3/2.1/4.3/3.4/2/1.1/3/5.2/2.2/2.2/1.3.2/5.1/3.1.1/2/2.3.1/7.1/1.1.2/3.2

import sys

Red=''
eRed=''
RedFmt=Red+'%s'+eRed

def interleave(*args):
  for vals in zip(*args):
    yield from vals

class Run:
  def __init__(self,n,i,j):
    # A run of length n, starting within [i,j]
    self.n=n
    self.i=i
    self.j=j
    self.s=j-i
    self.done=False

  def __str__(self):
    return str(self.n)
    
class Space:
  def __init__(self,n,i,j):
    # A space of length 1..n, starting within [i,j]
    # Once done, length == n
    assert n>0
    self.n=n
    self.i=i
    self.j=j
    self.s=j-i
    self.done=False

  def __str__(self):
    return ''

class Vector(list):
  # reads top-to-bottom or left-to-right
  def __init__(self,n,m):
    list.__init__(self,list(range(n)))
    self.n=n # size
    self.m=m # parent NoNo
    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

  def initRuns(self,runs):
    # Set runs to alternating list of Run and Skip
    self.rn=len(runs)
    self.runs=[]
    if self.rn==0:
      # No runs means a vector of x
      for c in self:
        c.setVal(False)
    else:
      need=sum(1+runs[k] for k in range(self.rn))-1
      space=self.n-need
      pos=0
      while runs:
        self.runs.append(Run(r:=runs.pop(0),pos,pos+space))
        pos+=r
        if runs:
          self.runs.append(Space(space,pos,pos+space))
          pos+=1
    self.initDisp()

  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 myPrintSize(self):
    return sum((len(str(run)) if isinstance(run,Run) else 1) for run in self.runs)

#=========v-old-v============

  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
    :return: list of runlens separated, possibly prefixed, with skips as negative integers
    """
    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)
    
  #=============new simple============
  def pass0(self):
    for i in range(0,len(self.runs),2):
      run=self.runs[i]
      for p in range(run.i+run.s,run.i+run.n):
        self[p].setVal(True)

class Row(Vector):
  cLet='R'
  def __init__(self,n,m,pos):
    Vector.__init__(self,n,m)
    self.y=pos

  def initDisp(self):
    self.width=self.myPrintSize()

  def __str__(self):
    return ((self.fmt%(' '.join(str(r) for r in self.runs if isinstance(r,Run))))+
            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,pos):
    Vector.__init__(self,n,m)
    self.x=pos

  def initDisp(self):
    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 if isinstance(c,Run)))
      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):
    # Returns true iff old value was None
    assert v in (True, False)
    if v == self.val:
      return False
    if self.val is not None:
      eprint("Reset not allowed: %s -> %s at %s,%s"%(self.val, v, self.x,self.y),err=103)
    self.val=v
    return True

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,i) for i in range(n)]
    self.rows=rr=[Row(n,self,i) for i in range(n)]
    for x in range(n):
      for y in range(n):
        self[(x,y)]=Cell(rr[y],y,cc[x],x)
    # Need cells in place for the following
    for row,runs in zip(rr,runsPerRow):
      row.initRuns(runs)
    for col,runs in zip(cc,runsPerCol):
      col.initRuns(runs)
    self.maxCRheight=maxCRheight=max(col.height for col in cc)
    for c in cc:
      c.updateHeader(maxHeight=maxCRheight)
    maxRRwidth=max(row.width for row in rr)
    for r in rr:
      r.updateHeader(maxWidth=maxRRwidth)
    self.rowfmt="%s|%%s|"%(' '*maxRRwidth)


  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)

#=============new simple============
  def pass0(self): # do columns of empty layout
    for c in self.columns:
      c.pass0()
    for r in self.rows:
      r.pass0()

  def solve(self):
    self.pass0()
    print(self)
    return
    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

  l = f.readline().rstrip()
  vv=l.split('/')
  n=int(len(vv)/2)
  print('%sx%s puzzle'%(n,n),file=sys.stderr)
  cols=[[int(i) for i in v.split('.')] for v in vv[:n]]
  rows=[[int(i) for i in v.split('.')] for v in vv[n:]]

  solver=Nono(rows,cols)
  solver.solve()