changeset 8:3276cf6ee6df

vastly simplified onePass, printing rows working
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Wed, 11 Mar 2020 19:52:22 +0000
parents 13f600be3a1b
children 28a7b0e992cb
files nono.py
diffstat 1 files changed, 59 insertions(+), 87 deletions(-) [+]
line wrap: on
line diff
--- a/nono.py	Wed Mar 11 17:13:05 2020 +0000
+++ b/nono.py	Wed Mar 11 19:52:22 2020 +0000
@@ -14,7 +14,7 @@
 
 Red=''
 eRed=''
-RedFmt=Red+'%s'+eRed
+RedFmt=Red+'%s '+eRed
 
 def interleave(*args):
   for vals in zip(*args):
@@ -28,8 +28,8 @@
     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.initialComplete=[]
+    self.finalComplete=[]
     self.resetAllRuns()
 
   def __repr__(self):
@@ -70,14 +70,16 @@
 
   def step(self):
     scratch=[0 if c.val is None else c.val for c in self]
+    wins=0
     for k,runs in enumerate(self.allRuns):
       dprint('=====pass %s======'%k)
-      self.onepass(0,self.n,scratch,runs.copy())
-    dprint(scratch)
+      if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
+        wins+=1
+    dprint(wins, scratch)
     newSeq=False
     inSeq=False
     for i in range(self.n):
-      if scratch[i]==self.nar:
+      if scratch[i]==wins:
         # If blobby in _every_ pass, then must be a blob
         if inSeq:
           newSeq=False
@@ -100,8 +102,7 @@
      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
+    maybe=[0]*(iBound-i0)
     dprint('r: %s'%stack)
     req=sum((-r if r<0 else r) for r in stack)
     while stack and i<iBound:
@@ -110,92 +111,52 @@
       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
-      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 i>0 and self[i-1].val is True:
+      #  dprint('x1',i)
+      #  return
       if (iBound-i)<req:
         # Can't win, give up altogether
-        dprint('c0',i,iBound,req)
-        return
-      while i<iBound:
+        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
-        dprint('top',i,c,inOne,rr)
+        if c is False:
+          dprint('x3',i)
+          return False
         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
+        # and a blob already present is OK
+        rr-=1
         i+=1
-        req-=r
-        break
+      # 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:
@@ -203,6 +164,8 @@
       dprint('win:',maybe)
       for k in range(iBound):
         scratch[k]+=maybe[k]
+      return True
+    print("Shouldn't happen? - fell through",stack,i,iBound)
 
   def checkNew(self,pos):
     # New blob at pos, can we complete anything?
@@ -277,8 +240,9 @@
       i+=1
     if self[i].val is True:
       r=self.runs.pop(0)
-      self.initialComplete+=(RedFmt%r)
+      self.initialComplete.append(r)
       self.margin0+=r+1
+      self.updateHeader(r=r)
 
   def foundN(self,i):
     print('foundN called on %s at %s'%(self,i),file=sys.stderr)
@@ -293,9 +257,17 @@
     return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
             Vector.__str__(self))
 
-  def updateHeader(self,maxWidth):
-    self.maxWidth=maxWidth
-    self.fmt="%s%%s|"%(' '*(maxWidth-self.width))
+  def updateHeader(self,maxWidth=None,r=None):
+    if maxWidth is None:
+      # update
+      self.infix+=RedFmt%r
+      self.fmt="%s%s%%s|"%(self.prespace,self.infix)
+    else:
+      # init
+      self.maxWidth=maxWidth
+      self.prespace=' '*(maxWidth-self.width)
+      self.fmt="%s%%s|"%self.prespace
+      self.infix=""
 
   def newBlob(self,x,newSeq):
     self[x].setVal(True)
@@ -383,7 +355,7 @@
     return "\n".join(lines)
 
 def dprint(*args):
-  pass
+  pass #print(*args)
 
 if __name__ == '__main__':
   if len(sys.argv)>1: